1.
2. Цепочка остатков (10)
Вундеркинд Матюша освоил операцию остатка от деления. Она ему понравилась, и Матюша совершенно замучил маму, требуя всё новых и новых примеров. Мама придумала игру: она предлагает сыну 2 натуральных числа, K и L. Матюша находит остаток от деления K на L и затем использует этот остаток в качестве нового значения L, и т. д. пока не получит остаток 0. Например, получив значения K=37 и L=13, Матюша находил остаток 4 раза и L принимала значения 11,4, 1, 0. Мама задумалась: нельзя ли подобрать такие K и L, чтобы их хватило надолго?
Найдите наименьшее натуральное К, для которого можно подобрать такое L, что Матюша сможет найти остаток от деления не меньше N раз. В качестве ответа – значения K и L через пробел.
Что вывела ваша программа при N=10?
3. Следы попрыгунчиков (15)
Попрыгунчики перемещаются прыжками одинаковой длины (у разных попрыгунчиков эта длина может быть разной, но каждый попрыгунчик имеет свою длину прыжка, выражаемую натуральным числом, не превосходящим 1000).
Представьте, что по заснеженной тропинке пропрыгали несколько попрыгунчиков. На тропинке остались следы, причём иногда следы нескольких попрыгунчиков совпадают. Вам надо определить наименьшее возможное количество попрыгунчиков, наследивших на дорожке.
Входные данные программы: L<=1000 – длина дорожки, K – количество следов на ней, далее К натуральных чисел, идущих в порядке возрастания – координаты следов (предполагается, что все попрыгунчики начинали движение с точки 0, её координата не включается во входные данные).
Что выведет программа при входных данных из этого файла (в первой строке L и K через пробел)?
4. Башенкостроение (10)
Змей Горыныч играет в кубики (с кем не бывает…). Каждая из его трёх голов возводит башенки, ставя кубики из коробки один на другой. Коробка у каждой головы своя. В каждой коробке кубики одинакового размера, а вот в разных коробках размеры кубиков могут быть и разными. Количество кубиков в каждой коробке бесконечно.
Играют так: сначала все три головы поставили на пол по кубику. А далее действовали так: голова, у которой была самая низкая башенка, доставала из своей коробки кубик и ставила на свою башенку. Если у двух голов башенки были одинаковые, и при этом ниже, чем третья башенка, они ставили свои кубики одновременно. Процесс должен был завершиться, когда все три башенки будут иметь одинаковую высоту.
Разработайте программу, которая получает на вход 3 натуральных числа, не превосходящих 10000, - размеры кубиков в каждой из коробок, - и выводит одно число – количество кубиков, которые будут задействованы в игре к тому моменту, когда игра закончится. Если при заданных значениях игра бесконечна, программа должна вывести -1.
Что выведет программа, если в качестве входных данных ввести 2, 271781, 224234?
5. Дели/25)
Для теста на курсе АИШ «Прикладная математика» потребовались числа с большим количеством делителей (для задач на подсчёт количества делителей числа). Вот, к примеру, у числа 48 есть 10 делителей: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48. Но нам бы побольше число, чтобы, к примеру, сотенку делителей…
Найдите, пожалуйста, наименьшее натуральное число, у которого ровно 100 делителей.
Ну, а теперь, пожалуйста, найдите наименьшее натуральное число, у которого ровно 960 делителей.
Гарантируется, что при всех тестовых значениях ответ в пределах 32разрядного целого существует.
6. Эдакая вот фунцайка (15)
Имеется функция от двух натуральных аргументов, причём первый из них не больше 9, а второй не больше 15. Вот несколько её значений. F(7, 1)=7; f(5, 2)=60; f(1, 9)=123456789; f(8,3)=984; f(2,8)=24691356. Разработайте программу, которая по значениям двух аргументов вычисляет значение функции. Чему равно значение f(9, 15)?
7. Козлик (15)
Вы когда-нибудь вышивали? Гладью, например, или крестиком? Ну ничего. Вот один из самых простых декоративных швов – «козлик».
На ткани нарисованы две линии. В начале левой иголка проходит с внутренней стороны ткани на внешнюю, нитка закрепляется. Далее делается стежок по наружной стороне к верхней линии – на М мм правее точки, расположенной над началом стежка. Затем делается с изнаночной стороны стежок влево на N мм. Потом – к нижней линии и на M правее, потом под нижней на N влево и т. д. На рисунке «козлик» с параметрами M=2 и N=1.
В зависимости от значений M и N получаются разные узоры. Если где-либо по лицевой или изнаночной стороне проходит более одной нитки – это неправильный козлик. разработайте программу, которая получает на вход значения M и N и определяет, является ли козлик с такими параметрами правильным (1 – правильный козлик, 0 – неправильный).
Вот несколько пар значений M и N: (37512, 25008), (12345, 8240), (2,2), (11470, 7646), (777, 666)
Какие из них дают неправильные «козлики»? Ответ введите в виде строки из 0 и 1 (1 – «козлик» хороший, 0 – неправильный).
8. Игры моли (25)
На склад фирмы «Эковрик», выпускающей экологически чистые коврики, проникла моль. Оценив количество и качество продукции, моль решила не просто тупо жрать коврики, а совместить этот процесс с интеллектуальной игрой. Две моли выбирают коврик (все коврики представляют собой правильные многоугольники с чётным числом углов, но число сторон и размер у них разные), и по очереди выгрызают в нём круглые дырочки. Диаметр дырочки – 5 мм, по правилам расстояние между любыми двумя дырочками на ковре не может быть меньше 10 мм. Проигрывает та моль, которая не может сделать очередной укус.
Итак, вы – моль (ну, бывает…). Перед вами и соперником коврик, представляющий собой правильный N-угольник (2<N<360, 360 mod N = 0) с длиной стороны М мм (100<=M<1000). Вам принадлежит право первого хода. Напишите программу для определения выигрышной стратегии по N и M.
Если у вас в данной ситуации есть выигрышная стратегия – определите полярные координаты точки первого выкуса. Если выигрышной стратегии нет – программа должна вывести -1 -1. Если существует множество решений (что естественно в силу того, что коврик при повороте на 360/N градусов отображается сам в себя) – выбираем решение с наименьшим значением азимута.
Про полярные координаты напомним: любая точка на плоскости определяется двумя полярными координатами: радиальной и угловой. Радиальная координата (на картинке это р) соответствует расстоянию от точки до начала координат. Угловая координата также называется полярным углом или азимутом (на картинке ф), равна углу, на который нужно повернуть против часовой стрелки полярную ось для того, чтобы попасть в эту точку.
Гарантируется, что при всех тестовых значениях решения будут целочисленными.
Что вывела ваша программа при N=72, M=120?
Если хотите получить полный балл за это задание, опишите в комментариях в тексте программы идею выигрышной стратегии или доказательство её отсутствия.
9. Очередь в Сбербанк (20)
Сбербанк. Кто бывал – знает: подходит клиент, получает талончик на обслуживание, ждёт вызова к окошку. Умная система сама организует очередь, отправляя к освободившемуся окошку следующего по очереди клиента. Если свободны сразу несколько окошек – клиент идёт к тому, номер которого меньше.
Руководство Сбербанка решило оценивать работу отделений с учётом времени, которое клиент провёл в очереди. Но вот проблема: система фиксирует момент прихода клиента (в минутах с начала открытия банка) и длительность его обслуживания в минутах, а вот момент начала этого обслуживания нигде не фиксируется.
Разработайте программу, определяющую количество клиентов в течении рабочего дня, которые провели в очереди больше М минут.
Входные данные:
W – количество окошек (оно неизменно весь день, 1<=W<=50)
M – предельное время ожидания в минутах
K – количество клиентов (0<=K<=50000)
Для каждого из клиентов – Pi, Di, 1<=i<=K, момент прихода клиента и длительность его обслуживания. 0<=Pi<=M, Pi<=Pi+1, 0<Di<100, все числа целые.
Что выведет программа при данных из этого файла? В первой строке значения W, M и K, далее K пар чисел, значения P и D для каждого клиента.
10. Сувенирные кружки (25)
У Закалякиных – семейный бизнес. Они закупают оптом белые кружки, а потом, по заказу клиентов, наносят на них двухслойный рисунок. Первый слой рисунка наносит Матрёна Закалякина, это занимает несколько минут в зависимости от сложности рисунка. Потом кружка сохнет не менее одной минуты, затем Терентий Закалякин наносит второй слой (тоже несколько минут). Ещё минимум минуту кружка сохнет. Последнюю операцию – упаковку кружки, - осуществляет сын Матрёны и Терентия, менеджер семейной фирмы Дональд Терентьевич Закалякин. Этот процесс занимает ровно минуту.
Итак, к началу рабочего дня семью Закалякиных ожидает Z заказов. Для каждой из заказанных кружек известны время нанесения рисунка Матрёной Mi и время нанесения рисунка Терентием (Ti) в минутах.
Определите на основе этих данных, через сколько минут после начала рабочего дня закончит свою работу по упаковке последней кружки Дональд, учитывая, что именно Дональд определяет, в какой последовательности запускать кружки в работу. Последовательность росписи кружек для Матрёны и Терентия одинакова.
Входные данные (при вводе данных из файла): в первой строке натуральное число z<=100, затем z строк, содержащих пары чисел mi и ti, разделённых пробелом, это натуральные числа, не превосходящие 1000.
Что выведет ваша программа при входных данных из этого файла?
11. Драконы (20)
– Трудно быть Доблестным Рыцарем! – думал Доблестный Рыцарь. - Надо ежемесячно убивать по дракону, иначе горожане усомнятся в твоей доблести и прогонят. При этом по правилам каждый следующий дракон должен быть круче предыдущего: у него должно быть больше голов и длиннее хвост. А тут всего-то в округе драконов не больше тысячи… правда, нет драконов с одинаковым числом голов, и нет с одинаковой длиной хвоста.
Сколько месяцев суждено Доблестному Рыцарю сохранять это звание, если рыцарь не только доблестный, но и умный, а описание имеющихся в наличии драконов – вот в этом файле? Число в первой строке – количество драконов N<=1000, далее следуют N строк, в которых по 2 натуральных числа, разделённых пробелом – число голов и длина хвоста, оба числа не больше 10000.
12. Земфира (10)
Поскольку в отсутствии горячей воды Земфира набивает СМС замороженными пальцами, телефон её настроен так. При выборе функции ввода СМС на экране прокручивается алфавит (латинский, ессно) с частотой 1 буква в секунду. Нажатие ОК вписывает текущую букву в сообщение, алфавит крутится дальше, дойдя до конца, идёт снова с начала. Пробелами и знаками препинания Земфира пренебрегает. Таким образом, на ввод сообщения АВ у З. уходит 2 сек, а на ВА - 27 сек.
Сколько времени потратит З. на ввод сообщения YESTERDAYALLMYTROUBLESSEEMEDSOFARAWAYNOWITLOOKSASTHOUGHTHEYREHERETOSTAYOHIBELIEVEINYESTERDAY? Сообщение - входное значение, строка.
13. Факелоносцы (15)
Государство Забейна принимает Олимпиаду. По территории страны проходит эстафета олимпийского огня. Состав факелоносцев утверждён, их N, N<100, каждый из них бежит по 1 км и преодолевает его за Мi минут (i=1..N, Mi<=10, целые).
Неприятность состоит в том, что факелы производства Забейнского металлического завода через 10 минут 1 секунду после зажигания тухнут. Поэтому их заменяют другими. Замену удобнее производить в момент передачи эстафеты, не допуская при этом потухания факела.
Каким минимальным количеством факелов удастся обойтись, если можно расставлять факелоносцев по дистанции в любом порядке?
Исходные данные - в этом файле: в первой строке количество факелоносцев N, во второй N чисел через пробел - значения Mi. Что выведет программа?
14. 13ичная система (30)
В 13чной системе счисления есть, как известно, цифры от 0 до 1, а также А, В, С. Отчисленный за «хвосты» бывший студент КИТ Егор от нечего делать играет с 13-ичными числами. Ему годятся не все числа – а только те, которые заканчиваются буквой и не имеют в своём составе нулей или последовательностей из нескольких нулей, расположенных между двумя буквами. Егор трактует входящие в число последовательности цифр как десятичные числа и заменяет число и следующую за ним букву на соответствующее количество экземпляров этой буквы. Например, число А12СС2В в записи Егора будет выглядеть как АСССССССССССССВВ.
Однако обратная расшифровка для многих чисел оказалась неоднозначной: к примеру, приведённое выше число могло быть и А13С1ВВ, и 1А5С8С2В, и вообще оно могло быть именно тем, что написано…
Разработайте программу, которая, получая на вход АВС-последовательность (бывшее число, переведённое в 13ичную систему), будет вычислять количество его возможных расшифровок. Гарантируется, что ни одно из предложенных тестовых значений не даст результат, выходящий за пределы длинного целого без знака. Длина входной строки – не более 64 символов.
Сколько расшифровок у последовательности CACABBBBBBAAAAAAAABBBBBBBBBBBBBBBBBBBBAAAAAAA?
