--->
36 задач
<---
Источники
Вчера у Васи был счастливый день: он наконец дописал программу всей своей жизни! И, недолго думая, он тут же запустил ее на Самом Главном Тесте.
Программа Васи очень сложная, и потому работает она долго. Поэтому Вася пошел спать, а наутро, сегодня, обнаружил, что программа, вместо того, чтобы посчитать нужный Ответ, вылетела с непонятной ошибкой.
Вася понял, что напрасно он не тестировал программу. Ведь Самый Главный Тест очень сложный — в нем есть \(N\) отдельных подзадач, и каждую из них надо решить. Конечно, надо было бы начать тестирование с меньшего количества подзадач, но ведь Вася — очень умный программист! И он абсолютно уверен, что его программа корректно решила все подзадачи, кроме какой-то одной. Вот только Вася не знает, какой именно.
Вася может изменять Самый Главный Тест, отключая в нем те или иные подзадачи. Он надеется, что, если среди отключенных будет та подзадача, на которой его программа не работает, то получившийся тест его программа спокойно пройдет. Но вот проблема: программа работает долго, а подзадач много, и потому, если отключать задачи по одной, то придется очень долго искать нужную. А Вася очень хочет узнать, где ошибка, уже завтра!
К счастью, у Васи в распоряжении есть много компьютеров. Он может на некоторых из них запустить свою программу на каком-то тесте (т.е. на Самом Главном Тесте с некоторыми отключенными подзадачами), а назавтра посмотреть, какие программы завершились успешно, а какие нет, — и по результатам понять, какая подзадача создавала проблемы. Помогите Васе подобрать тесты для каждого из компьютеров, т.е. объясните ему, какие подзадачи в каком тесте он должен отключить, так, чтобы назавтра, узнав результаты работы программы на этих тестах, он смог бы уверенно определить, с какой подзадачей у него возникают проблемы (естественно, считая, что такая подзадача только одна, ведь Вася — очень умный программист!)
Учтите, что Васе не хочется делать лишнюю работу по запуску программ и определению их результата, поэтому он хочет минимизировать количество запусков (т.е. фактически количество компьютеров, ведь его программа настолько сложная, что на одном компьютере можно запустить только один экземпляр программы).
В первой и единственной строке входного файла находится одно целое число \(N\) — количество подзадач в Самом Главном Тесте (\(1 \le N \le 10^5\)).
В первой строке выходного файла выведите минимальное необходимое количество компьютеров \(M\). В последующих \(M\) строках выведите информацию о том, на каком тесте надо запускать программу на каком компьютере. А именно, в \(i\)-ую из них выведите последовательность чисел \(k_i\), \(b_{i1}\), \(b_{i2}\), ...., \(b_{ik_i}\), где \(k_i\) — количество подзадач, которые надо отключить в тесте, на котором будет работать программа на \(i\)-ом компьютере, а \(b_{ij}\) (\(1 \le j \le k_i\), \(1 \le b_{ij} \le N\)) — номера подзадач, которые надо отключать. Числа \(b_{ij}\) должны быть различны для каждого фиксированного \(i\).
Подзадачи нумеруются от 1 до \(N\).
В пределах одной строки подзадачи можете выводить в любом порядке. Если есть несколько оптимальных решений, выведите любое.
В примере:
5
3 3 1 3 5 3 1 2 5 4 1 2 3 4
Числа Фибоначчи - элементы числовой последовательности, в которой каждое последующее число равно сумме двух предыдущих чисел. Более формально, последовательность чисел Фибоначчи {Fn} задается линейным рекуррентным соотношением:
Рассмотрим систему счисления с двумя цифрами 0 и 1, в которой, в отличие от двоичной системы весами являются не степени двойки 1,2,4,8,16,..., а числа Фибоначчи 1,2,3,5,8,13,.... В этой системе счисления каждое положительное целое число единственным образом представляется в виде строки нулей и единиц, которая начинается с 1 и в которой нет двух единиц, стоящих рядом.
Даны две строки, представляющие натуральные числа A и B. Найти строку, представляющую число A+B.
Даны две строки, представляющие A и B, состоящие из нулей и единиц. Длина каждой из строк не превышает 104.
Выведите строку, представляющую число A + B. Обратите внимание, что она должна начинаться с единицы.
10101
100
100010
Исходные строки '10101' и '100' представляют числа 8 + 3 + 1 = 12 и 3. Ответом является строка '100010', представляющая строку 13 + 2 = 15 = 12 + 3.
Дано одно натуральное число n (1 ≤ n ≤ 105)
Выведите число 2n
10
1024
Написать рекурсивную программу перевода целых чисел, не превосходящих 109, из десятичной системы счисления в P-ичную (1 ≤ P ≤ 36)
В первой строке вводится значение P, во второй строке — число, которое надо перевести.
Цифры, участвующие в записи числа в P-ичной системе счисления, соответствующие десятичным числам 10, 11, ..., P - 1, заменять на заглавные латинские буквы А, В, С, ... . Вывод осуществлять следующим образом: сначала выводится число в десятичной системе счисления(введённое), за ним система счисления, в которой оно записано, в круглых скобках, затем ставится знак "=" и аналогично выводится результат работы Вашей программы — число в P-ичной системе счисления. Весь вывод осуществляется без пробелов.
3 123
123(10)=11120(3)
Рассмотрим компьютерную сеть с настроенной TCP/IP маршрутизацией. Будем рассматривать некоторую ее модификацию. А именно в этой сети находить N подсетей. Каждая подсеть характеризуется своей маской. Маска подсети представляет собой 4 однобайтных числа, разделенных точкой. Причем для масок выполнено следующее свойство: если представить маску в двоичном виде, то сначала она будет содержать k единиц, а потом q нулей, причем k + q = 32 . Например 255.255.255.0 — маска подсети, а 192.168.0.1 — нет.
Поясним, как получается двоичное представление IP-адреса. Для этого числа, составляющие IP-адрес, представляются в двоичной системе счисления (при этом каждое из них дополняется ведущими нулями до длины 8 цифр), после чего удаляются точки. Получившееся 32-битное число и есть двоичное представление IP-адреса. Например, для адреса 192.168.0.1 этот процесс выглядит так: 192.168.0.1 -> 11000000.10101000.00000000.00000001 -> 11000000101010000000000000000001. Таким образом, двоичным представлением IP-адреса 192.168.0.1 является 11000000101010000000000000000001.
Будем говорить, что два компьютера с IP 1 и IP 2 лежат в подсети, если IP 1 & Mask = IP 2 & Mask , где Mask — маска этой подсети, а & — операция побитового логического "и". IP компьютера представляет так же 4 однобайтных числа, разделенных точкой.
Вам даны M пар IP-адресов компьютеров. Для каждой из них Вам надо определить, в скольких подсетях из заданных они лежат.
В первой строке входного файла записано число N — количество подсетей. В следующий N строках перечислены маски этих подсетей. В N + 2 строке находится число M (0 ≤ M ≤ 100000) . В следующих M строках записаны пары IP-адресов, разделенных пробелом.
Все заданные маски подсетей различны.
Для каждой пары IP-адресов в отдельной строке выходного файла выведите количество подсетей, в которых лежат оба компьютера.
2 255.255.255.255 255.255.255.0 3 192.168.31.1 192.168.31.2 192.168.31.3 192.168.31.4 192.168.31.1 192.167.31.2
1 1 0