Дано неориентированное дерево. Требуется посчитать количество способов ориентировать ребра в дереве из n вершин, чтобы получилось ровно m стоков. Сток – вершина из которой не выходит ни одного ребра.
В первой строке содержатся два числа n и m, число вершин дерева и требуемое количество стоков соответсвенно. В следующих n - 1 строках содержатся пары чисел ui vi – ребро дерева, соединяющее вершины с номерами ui и vi.
Выведите количество способов по модулю 109 + 7.
5 2
1 2
2 3
3 4
3 5
8
После ответа на главный вопрос жизни, вселенной и всего прочего суперкомпьютер довольно долгое время находился без работы, однако недавно ему пришлось подумать над другим вопросом. Один известный художник всегда искал метод создания "идеального" шедевра и после 42 лет раздумий, ему пришла мысль спросить это у суперкомпьютера. Так они и встретились.
В этот раз вопрос оказался намного проще и суперкомпьютер выдал следующий ответ ровно за 42 секунды:
Суперкомпьютер отказался предоставить программу для генерирования шедевров по заданной размерности картины n, поэтому это придется сделать Вам.
Единственная строка содержит одно целое положительное число n – количество строк и столбцов в получившейся после распила картине.
В первой строке выведите число n. Далее в n строках необходимо вывести по n целых чисел, соответствующим правилам формирования шедевра. Если существует несколько решений, то выведите любое из них. Если же решения не существует, то необходимо вывести -1.
5
5
12 14 11 13 15
22 24 21 23 25
7 9 6 8 10
17 19 16 18 20
2 4 1 3 5
3
-1
Известная компания по производству яхт "Лодки, лодки, лодки" решила для повышения доходов продавать свою продукцию с помощью так называемых парных аукционов. В таких аукционах участвует ровно два покупателя и торги осуществляются по несколько необычным правилам. Цена товара изначально равна 1 рубль, но повышать ее можно только домножив названную ранее стоимость на целое число от 2 до 9. Торги продолжаются до тех пор, пока аукционная цена яхты не превысит число n, заранее известное участникам торгов. Таким образом, покупатель, закончивший торги получает яхту за 1 рубль, а второй, соответственно, вынужден выплатить n рублей – стоимость яхты.
Вы, как состоятельный человек, решили поучаствовать в t парных аукционах. Соответственно, Ваши менеджеры по финансам должны определить для заданной в каждом из аукционов стоимости яхты ni, возможно ли купить ее за 1 рубль или нет, если Ваш соперник осуществляет торги оптимально. Также известно, что в каждом аукционе Вы открываете торги, т.е. делаете повышающую ставку первым.
В первой строке расположено целое положительное число t – количество парных аукционов, участником которых Вы являетесь.
В каждой из следующих t строк содержится ровно по одному целому положительному числу ni – стоимости яхты в каждом из аукционов, соответственно.
Выведите t строк, в каждой из которых содержится слово "YES" (без кавычек), если Вы сможете купить яхту за 1 рубль в данном аукционе и "NO" в противном случае.
1
42
YES
На столе есть n карточек. Для каждой карты известно два числа — сила карточки и номер серии. Вы собираете колоду:
Требуется посчитать суммарную цену в медяках по всем возможным колодам. Две колоды считаются различными, если существует карточка, которая входит в одну колоду и не входит в другую. При этом у различных карточек могут быть одинаковые сила и серия.
В первой строке задается число n — количество карточек из которых будет собираться колода. В следующих n строках задается по два целых числа si ki — сила и номер серии i-й карточки.
В единственной строке выведите суммарную цену в медяках по всем возможным колодам. Для простоты подсчета медяков ответ требуется вывести по модулю 109 + 7.
6
8 8
5 9
9 4
3 9
3 1
7 5
42
Привет! Я ярый спортивный фанат. Победа любимой спортивной команды – это всегда радостно. А если еще и сделать верную ставку у букмекеров, то не только радостно, но и прибыльно. Вот только как угадать, будет ли победным предстоящий матч? Это большой вопрос...
И вот недавно я, наконец, раскрыл тайну. Весь секрет в том, как выстроятся в шеренгу во время исполнения гимна n игроков, у которых на футболках нанесены все различные номера от 1 до n. Если |Ai - i| ≤ k для любого i от 1 до n, то матч обязательно закончится победой моих фаворитов. Число k мне перед матчем по доброте душевной готов сообщить арбитр.
Наример, при k = 1 расположение игроков (3, 4, 1, 2) приведет к поражению, а уже при k = 2, они обязательно одержат победу.
Я уже выиграл достаточно денег на ставках, так что теперь и вы можете пользоваться этим секретом. Для заданного k посчитайте количество победных перестановок игроков команды, состоящей из n человек.
В первой строке задается два целых числа n и k – количество игроков в команде и секретный параметр, помогающий определять победность перестановки игроков.
В единственной строке выведите количество победных перестановок по модулю 109 + 7.
4 2
14
Финансовые аналитики компании "WeRRich" работают над отчетностью за текущий год. В их распоряжении находится n значений колебаний курса акций компании, отсортированных по времени. Задача аналитиков заключалась в том, чтобы найти максимально благоприятный период, т.е. последовательный непустой временной интвервал, в течение которого сумма колебаний была максимальна в течение года.
К сожалению, высший менеджмент компании не устроили итоги финансового года, поэтому аналитики решили подкорректировать отчетность путем обмена двух колебаний местами во временном ряду. Казалось бы, идеальное преступление, но финансистам достаточно сложно было разработать эффективный алгоритм, чтобы его осуществить. Теперь им требуется помощь программистов, чтобы определить индексы колебаний, которые необходимо обменять и максимально возможную сумму, полученную в результате.
Первая строка содержит целое положительное число n – количество колебаний курса акций за год.
Вторая строка содержит ровно n целых чисел ai – численные значения колебаний в хронологическом порядке.
В первой строке необходимо вывести одно число – максимально возможную сумму колебаний во время наиболее благоприятного периода.
Второй строке – два целых различных числа, которые являются индексами колебаний, подлежащих обмену. Если существует несколько решений, выведите любое из них.
5
1 -2 -3 4 -5
5
4 2
Один из основателей корпорации Intel Гордон Мур 1965 заметил, что число транзисторов на кристалле интегральной схемы удваивалось каждые 24 месяца. Британские ученые решили уточнить эту закономерность. В результате длительных исследований оказалось, что число транзисторов всегда является числом, состоящим только из цифр 1 и 2. Соответственно, в самое первое поколение интегральных схем содержало только 2 транзистора, второе – 12 и т.д. Второй особенностью уточненного закона Мура является то, что число транзисторов поколения n обязательно нацело делится на 2n. Для проверки своих расчетов ученым требуется написать программу, которая бы определяла число транзисторов по уточненному закону Мура в интегральной схеме поколения n.
Единственная строка содержит одно целое положительное число n – поколение интегральных схем, для которых необходимо вычислить число транзисторов.
Необходимо вывести число транзисторов на кристалле интегральной схемы поколения n, соответствующее ограничениям задачи. Число не должно превосходить 10100000. Если существует несколько вариантов ответа, выведите любой. Если подходящего числа транизсторов нет, выведите -1.
1
2
2
2112
Современные компьютерные системы достаточно хорошо научились определять плагиат. Рассмотрим некоторый текст p, который претендует на то, чтобы быть оригинальным и текст o, который был скопирован из какого-то одного источника. Под плагиатом степени k понимается вхождение в текст p некоторых непересекающихся подстрок длиной не менее k, конкатенация которых дает текст o. Порядок конкатенации подстрок в текст o соответствует их порядку вхождения в текст p.
Поскольку плагиат из одного источника является хорошо изученной проблемой, начаты разработки программного обеспечения для определения плагиата из нескольких источников. На начальном этапе для реализации нужны примеры неоригинальных текстов. В связи с этим требуется найти минимальную длину текста, который является плагиатом степени k для заданных текстов a и b.
Первая строка содержит целое положительное число k – степень плагиата текста, минимальную длину которого надо найти.
Вторая и третья строка содержат строки a и b – оригинальные тексты, для каждого из которых искомый текст является плагиатом степени k.
Все строки из входных данных состоят из строчных букв латинского алфавита.
В единственной строке необходимо вывести минимальную длину текста, который является плагиатом степени k для оригинальных текстов a и b.
2
abaaa
babaa
6
3
abacabadabacaba
bababanana
19
Это будет простая задача. Даже очень. Мы любим генерировать различные числа, думаем и вам понравится. Вам дано целое число s. Попробуйте сгенерировать максимальное число с суммой цифр s, которое не содержит нулей, а также никакие рядом стоящие цифры не равны.
В единственной строке содержится число s.
Выведите одно число содержащее ответ на задачу.
1
1
2
2
Кто-то нарисовал невырожденный треугольник на листочке в клеточку с целочисленными координатами. Но вам не сказал где он находится. А узнать то где треугольник ну очень хочется. К счастью этот кто-то может отвечать на такой вопрос: если взять две точки с координатами (x1, y1) и (x2, y2) и провести через них направленную прямую из первой точки во вторую, то как прямая будет располагаться относительно треугольника. Ответом будет один символ, который соответствует следующим результатам:
После каждого из ваших запросов вы получите в ответ строку, состоящую из одного символа из трех возможных ('-', '+' или 'X').
Для того чтобы задать вопрос в отдельной строке выведите координаты двух точек в целых числах в формате Q x1 y1 x2 y2.
После того, как вы уверены в том что знаете координаты треугольника выведите его координаты в формате A x1 y1 x2 y2 x3 y3. Порядок координат значения не имеет.
После вывода не забывайте выводить символ новой строки и делать flush-операцию (сброс буфера). Например, fflush(stdout) в С++, System.out.flush() в Java, и flush(output) в Pascal.