Решения принимаются до 0 часов 12 февраля 2020 г.
==============================================
Задача Train2020. «Укрзалізниця» активно расширяет международное сообщение. Для увеличения количества маршрутов было приобретено сверхсовременные поезда класса Интерсити++. Пробная серия включала ровно один локомотив (с номером 1) и N-1 вагон с номерами от 2 до N.
После приобретения было выявлено, что особенности механизма сцепления вагонов позволяют сцеплять только те вагоны, номера которых имеют обй делитель, отличный от единицы. Исключение касается лишь локомотива - он может быть прицеплен только впереди поезда и имеет возможность сцепиться с любым вагоном.
От количества вагонов в составе зависит прибыль компании, а потому руководство просит вас о помощи - определить максимальное количество вагонов (с учетом локомотива), которые можно сочетать последовательно в подвижной состав.
Технические условия Программа Train2020 считывает с устройства стандартного ввода единственное число N ≤105 - количество полученных вагонов. Программа должна выводить ровно одно число - максимальную длину подвижного состава.
Примеры
|
Ввод |
Вывод |
Коментарии |
|
3 |
2 |
Вагоны 2 и 3 совместить нельзя, а потому подвижной состав будет или 1-2, или 1-3 |
|
6 |
5 |
Возможен вариант подвижного состава 1-2-4-6-3 |
Задача Game2020. Любимое дело колядников - делить заработанные сладости и деньги. Олесь и Миша получили кучу конфет, а кроме того денежную купюру определенного номинала. Конечно что эта купюра представляет для ребят наибольший интерес, а взрослых, которые могли бы разменять сумму поровну, нет. Поэтому старшим братом было предложено сыграть в следующую игру.
Каждому из игроков по очереди приходится выбирать некоторый непустой набор корзин, стоящих рядом, а дальше с каждой необходимо убрать как минимум по одной конфете. Такие действия игроки делают, пока у кого не останется возможности сделать ход - тогда этот игрок проигрывает и деньги достаются победителю.
Миша уже разложил конфеты по корзинам, но Олесь подозревает, что брат заранее точно знает, что сможет выиграть. Олесь, как младший брат, ходит первым и просит у вас помощи – имеет ли он некоторую выигрышную стратегию для заданного набора конфет?
Технические условия С первой строки стандартного устройства ввода программа Game2020 считывает единственное число T (1 ≤ T ≤ 10) - количество тестов. Далее, в T парах строк следуют входные данные в виде:
- В первом в паре - число N (1 ≤ N ≤ 106) - количество корзин с конфетами
- Во втором в паре - N чисел Ai (0 ≤ Ai ≤ 105) - количество конфет в корзинках
Программа должна вывести строку с ровно N символов - ответы на каждый из тестов в той же последовательности, что и во входных данных. Программа должна вывести Y, если в Михась точно имеет стратегию для победы и N в противном случае.
Примеры
|
Введення |
Виведення |
Коментар |
|
3 3 1 0 1 4 1 5 6 1 5 1 0 1 1 1 |
YNN |
В первом случае Олесь опорожнит одну из корзин, после чего Миша возьмет конфету с другой и выиграет. Во втором случае Олесь может забрать все конфеты сразу, чем обеспечит победу. В третьем случае Олесь может опорожнить две из трех корзин, идущих подряд, после чего Мише придется взять конфету из одной из оставшихся корзин, что даст победу Олесю. |
Задача Wall2020. На идеально гладкой горизонтальной поверхности неподвижно стоит куб с массой m1. Неподалеку от куба возвышается стена, плоскость которой параллельна одной из боковых граней куба. С противоположной от стены стороны с некоторой скоростью скользит в направлении стены куб с массой m2 ,. Скорость перпендикулярна к стене и боковым граням обоих кубов Все удары абсолютно упругие. Понятно, что после столкновения первый куб начнет скользить в направлении стены, после чего отразится. и, вероятно, еще раз столкнется с другим. Вам нужно определить общее количество столкновений, которые состоятся в системе.
Технические условия
Программа Wall2020 читает с устройства стандартного ввода два целых числа m1 и m2 - массы кубов (1 ≤ m1 ≤ m2 ≤ 103). Программа выводит единственное целое число - количество ударов.
|
Ввод |
Вывод |
Комментарий для тех, у кого нет времени изучать школьную физику |
|
1 10 |
10 |
Абсолютно упругий удар - взаимодействие тел без потерь ими суммарной механической энергии |
|
10 10 |
3 |
Задача Trunks. Скрудж Макдак нашел пещеру, где в один ряд стояли сундуки. На стене пещеры написано:
• С первого сундука можно взять ровно K монет;
• С каждого следующего сундука можно взять любое количество монет, но хотя бы одну;
• Нельзя брать из последующего сундука столько же монет, что и с предыдущего;
• Если из очередного (последнего на данный момент) сундука взять меньше монет, чем из предпоследнего, то со следующего нужно взять больше, чем с последнего;
• Если из последнего сундука взять больше монет, чем с предпоследнего, то со следующего нужно взять меньше, чем с последнего;
• Всего можно взять ровно N монет.
Помогите Скруджу подсчитать, сколькими способами он сможет вынести из пещеры монеты. Считайте, что сундуков, а также монет в каждом сундуке достаточно.
Технические условия. Программа Trunks читает с устройства стандартного ввода числа N и K (1≤N≤5000, 1≤K≤N) и выводит на устройство стандартного вывода остаток при деления искомого количества на 109 + 7.
Примеры
Ввод 3 3
Вывод 1
Ввод 6 2
Вывод 4
Объяснение. Для второго примера возможные способы: [2,1,2,1], [2,1,3], [2,3,1], [2,4].
Задача Kingdoms2020. Авторы сказок знают, что существуют еще царства кроме Тридевятого,и они характеризуются как (N,K) - Царства. Однако существовать (N,K) - Царство может только тогда, когда K может быть представлено в виде суммы не более чем N простых чисел.
Например, (3,9) - (Тридевятое) Царство существует, потому что 9 = 2 + 7 (еще варианты: 9 = 3 + 3 + 3 і 9 = 2 + 2 + 5). Также существует и (2,10)- (Двадесятое) Царство, так как 10 = 5 + 5. В то же время (2,27)-е (Двадвадцатьседьмое) Царство существовать не может, поскольку 27 невозможно представить в виде суммы не более чем двух простых чисел.
Найдите количество существующих (N, K)-царств при условии, что числа N и K могут изменяться в некотором диапазоне: a ≤ N ≤ b, c ≤ K ≤ d.
Технические условия. Программа Kingdoms2020 читает с устройства стандартного ввода четыре целых числа в одной строке через пробелы: a и b - нижнее и верхнее ограничение на N и целые числа c и d - нижнее и верхнее ограничение на K. Программа выводит на устройство стандартного вывода единственное число, равное количеству существующих (N, K)-царств, для которых a ≤ N ≤ b и c ≤ K ≤ d. Размер текста решения не должен быть большим 16 Кб.
Ограничения:
1. Число a от 1 до 1000000 включительно.
2. Число b от a до a + 1000 включительно.
3. Число c от 1 до 1000000 включительно.
4. Число d от c до c + 1 000 включительно.
Примеры
|
Ввод |
Вывод |
Комментарии |
|
1 1 2 10 |
4 |
У этом примере нам необходимо найти числа K, представляемые в виде суммы не более 1-го простого числа, то есть простые. На отрезке от 2 до 10 включительно есть 4 простых числа - 2, 3, 5 и 7. |
|
1 2 20 30 |
12 |
(N, K)-царства существуют:
Всего имеем 2 + 10 = 12 царств. |
|
2 4 45 64 |
58 |
|
|
1 20 469588 470425 |
15701 |
|
Дополнительная информация
Цитата из одной, очень известной, «сказки»: «Натуральное число X, большее единицы, называется простим, если оно не делится без остатка ни на какие числа, кроме 1 и X.»
Задание подготовили А.Зуев, В.Мельник, Г.Непомнящий, М.Стречень, Ю.Пасихов