Темы --> Информатика --> Алгоритмы --> Арифметические алгоритмы --> Системы счисления --> Двоичная система счисления
---> 3 задач <---
Источники --> Личные олимпиады
    Олимпиады сайта(17 задач)
    Школьная личная олимпиада ФМШ №2007 г. Москвы(7 задач)
    Золотая середина (Новосибирск)(10 задач)
    Нижегородская олимпиада школьников(42 задач)
    Московская олимпиада школьников(168 задач)
    Индивидуальная олимпиада по информатике и программированию (ИОИП)(22 задач)
    Открытая олимпиада школьников(173 задач)
    Украинские олимпиады(61 задач)
    Республиканская олимпиада школьников (Беларусь)(6 задач)
    Жаутыковские олимпиады(8 задач)
    Всероссийская олимпиада школьников(304 задач)
    Международные олимпиады(32 задач)
    Central European Olympiad in Informatics (4 задач)
    Интернет-олимпиады(2 задач)
    COCI(36 задач)
    Турнир Архимеда(36 задач)
    Baltic Olympiad in Informatics(10 задач)
Страница: 1 Отображать по:
#1282
Тапкодёр
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Ассоциация Тапкодер организует Всемирное парное соревнование сильнейших программистов. К участию в соревновании допущены первые 2k зарегистрировавшихся участников, которым присвоены номера от 1 до 2k.

Соревнование будет проходить по олимпийской системе. В первом туре первый участник встречается со вторым, третий с четвертым и так далее. В каждой паре победителем становится участник, первым решивший предложенную задачу, при этом ничьих не бывает. Все победители очередного тура и только они являются участниками следующего тура. В каждом туре пары составляются из участников в порядке возрастания присвоенных им номеров. Соревнование продолжается до тех пор, пока не останется один победитель.

Организаторам стало известно, что некоторые пары участников заранее договорились о результате встречи между собой, если такая встреча состоится. Для всех остальных встреч, кроме n договорных, возможен любой исход.

Некоторые m участников соревнования представили свои резюме в ассоциацию Тапкодер с целью поступления на работу. Организаторов интересует, до какого тура может дойти каждый из претендентов при наиболее благоприятном для него стечении обстоятельств. При этом для каждого участника в отдельности считается, что все недоговорные встречи, в том числе те, в которых он не участвует, закончатся так, как ему выгодно, а все состоявшиеся договорные встречи закончатся в соответствии с имеющимися договоренностями.

Требуется написать программу, которая для каждого из претендентов определяет максимальный номер тура, в котором он может участвовать.

Входные данные

В первой строке заданы три целых числа k (1 ≤ k ≤ 60), n (0 ≤ n ≤ 100 000) и m (1 ≤ m ≤ 100 000). В следующих n строках описаны n пар участников, которые договорились между собой о том, что первый из двух участников пары выиграет встречу, если она состоится. Гарантируется, что каждая пара участников присутствует во входных данных не более одного раза, при этом, если задана пара x y, то пары y x быть не может, кроме того, x ≠ y. В последней строке перечислены номера участников, желающих работать в Тапкодере, в порядке возрастания их номеров. Все номера претендентов на работу различны.

Выходные данные

Выходные данные должны содержать m целых чисел — максимальные номера туров, до которых могут дойти соответствующие претенденты на работу. Туры нумеруются от 1 до k.

Комментарии к примерам тестов.

1. У каждого из участников есть возможность выйти в финал, так как договорных матчей нет.

2. Если четвертый участник выиграет у третьего, то договорная встреча первого и третьего не состоится, что благоприятно для первого.

3. Первому участнику благоприятно во втором туре играть с третьим, а не с четвертым, в свою очередь, четвертый может выиграть у третьего и также выйти в финал.

Система оценки

Тесты к этой задаче состоят из четырех групп, баллы начисляются только при прохождении всех тестов группы и всех тестов предыдущих групп.

0. Тесты 1–10. k <= 5. Эта группа оценивается в 30 баллов.

1. Тесты 11–14. k <= 20. Эта группа оценивается в 20 баллов.

2. Тесты 15–18. k <= 30. Эта группа оценивается в 20 баллов.

3. Тесты 19–23. Дополнительные ограничения отсутствуют. Эта группа оценивается в 30 баллов.

Примеры
Входные данные
2 0 3
1 3 4
Выходные данные
2 2 2
Входные данные
3 1 1
3 1
1
Выходные данные
3
Входные данные
3 3 4
1 2
1 3
4 1
1 2 3 4
Выходные данные
3 1 2 3
#1339
Цифры и числа
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Как много открытий можно сделать, исследуя числа и составляющие их цифры!

Петя очень любит арифметику, и кроме домашних заданий он постоянно придумывает дополнительные задачи. Однажды он стал прибавлять к натуральным числам сумму составляющих их цифр. Петя обнаружил, что некоторые числа, например 20, не могут быть получены из других чисел в результате такого действия. Эти числа ему не понравились, и он назвал их некрасивыми.

Позже, когда Петя начал изучать информатику, те же исследования он стал проводить с натуральными числами в двоичной системе счисления. Например, двоичное число 1110­2 (в десятичной системе — 14) можно получить из числа 11002 (в десятичной системе — 12), прибавив к последнему сумму его цифр:

11002 + 102 = 11102.

Петя решил исследовать множество двоичных некрасивых чисел. Первые пять некрасивых чисел он нашел без труда: 1 = 12, 4 = 1002, 6 = 1102, 13 = 11012, 15 = 11112. Продолжить работу он собирается с помощью компьютера.

Требуется написать программу, которая определяет количество двоичных некрасивых чисел, не превосходящих заданного числа n.

Входные данные

В первой строке входного файла содержится число n, записанное в десятичной системе счисления (1 ≤ n ≤ 1018).

Выходные данные

В единственной строке выходного файла должно содержаться единственное число — количество двоичных некрасивых чисел, не превосходящих n.

Примечание

Решения, корректно работающие при n ≤ 106, будут оцениваться из 40 баллов.

Примеры
Входные данные
17
Выходные данные
5
Входные данные
18
Выходные данные
6
#111521
Тестирование программы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

Вчера у Васи был счастливый день: он наконец дописал программу всей своей жизни! И, недолго думая, он тут же запустил ее на Самом Главном Тесте.

Программа Васи очень сложная, и потому работает она долго. Поэтому Вася пошел спать, а наутро, сегодня, обнаружил, что программа, вместо того, чтобы посчитать нужный Ответ, вылетела с непонятной ошибкой.

Вася понял, что напрасно он не тестировал программу. Ведь Самый Главный Тест очень сложный — в нем есть \(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
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест