Задача 1 “Количество чисел, не делящихся на 2, 3 или 5” (20 баллов)
Задано натуральное число N.
Требуется написать программу, которая находит количество натуральных чисел, не превышающих N и не делящихся ни на одно из чисел 2, 3, 5.
Технические требования:
Входной файл: INPUT.TXT.
Выходной файл: OUTPUT.TXT.
Ограничение времени: 3 секунды на тест.
Формат входных данных:
Файл INPUT.TXT состоит из одной строки, в которой содержится число N (1PdNPd1000000000).
Формат выходных данных:
В выходной файл OUTPUT.TXT вывести найденное число.
Пример файла входных данных:
10
Пример файла выходных данных (для приведенного выше входного файла):
2
—————————————————————————————————————————–
Задача 2 “Уравнение x!a=b” (20 баллов)
Операция ! действует с целыми положительными числами побитово, т.е. надо представить числа в двоичном виде и для каждой пары бит с одинаковыми номерами выполнить действие по следующим правилам: 0!0=0, 1!0=1, 0!1=1, 1!1=0.
Требуется написать программу, которая по заданным a и b решит уравнение x!a=b.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит два целых положительных числа, записанных через пробел. Числа не превышают значения 32767
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно найденное число.
Пример файла входных данных:
1 1
Пример файла выходных данных (для приведенного выше входного файла):
0
—————————————————————————————————————————–
Задача 3 “Слон” (20 баллов)
На шахматной доске 8*8 клеток стоит слон (фигура, которая ходит по
диагонали).
Требуется написать программу, которая определит сможет ли слон дойти до заданной клетки (x, y). Если сможет, то указать за какое наименьшее количество ходов. Если количество ходов больше одного, то указать через какие промежуточные клетки он должен пройти. Если таких маршрутов несколько, то указать любой из них.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит четыре числа m, n, x, y. (m, n) – координаты клетки, на котором находится слон, (x, y) – координаты клетки, на которую надо попасть. Числа m, n, x, y задаются в диапазоне от 1 до 8 и записываются через пробел.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать в первой строке k – минимальное количество ходов, а далее в k-1 строках по 2 числа через пробел – координаты посещенных клеток. Если слон не может попасть на заданную клетку, то вывести 0.
Пример файла входных данных:
1 1 3 1
Пример файла выходных данных (для приведенного выше входного файла):
2
2 2
—————————————————————————————————————————–
Задача 4 “Короткая последовательность” (20 баллов)
Дано целое число n, 0<n<32768. Рассмотрим последовательность Sv(1)Sv(2)Sv(3)…Sv(k)…, где каждая группа цифр Sv(k) состоит из записанных одно за другим чисел от 1 до k. Например, первые 84 цифры последовательности выглядят так:
112123123412345123456123456712345678123456789123456789101234567891011123456789101112.
Требуется написать программу, которая определит какая цифра находится на n-ой позиции в построенной последовательности.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 3 секунды на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит одно число n.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одну цифру, которая стоит на n-ой позиции в последовательности.
Пример файла входных данных:
20
Пример файла выходных данных (для приведенного выше входного файла):
5
—————————————————————————————————————————–
Задача 5 “Разложение факториала на простые множители” (20 баллов)
Факториалом числа N называется произведение 1*2*3*:*N.
Требуется написать программу, которая найдет разложение факториала
заданного числа на простые множители.
Технические требования:
Входной файл: INPUT.TXT,
Выходной файл: OUTPUT.TXT,
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит число N (2PdNPd32767).
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать в каждой строке пару чисел – простое число и количество его вхождений в разложение факториала на простые множители. Числа разделить пробелом. Простые числа должны идти в порядке возрастания их значений.
—————————————————————————————————————————–
Задача 6 “Количество делящихся на три”
Рассмотрим последовательность 1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789. 12345678910, 1234567891011, :.
Требуется написать программу, которая определит количество из N первых элементов этой последовательности, делящихся на три.
Технические требования:
Входной файл: INPUT.TXT,
Выходной файл: OUTPUT.TXT,
Ограничение по времени тестирования: по 2 секунды на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит одно число N – количество элементов последовательности (1PdNPd2^(31)-1).
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать одно найденное число.
—————————————————————————————————————————–
Задача 7 “Последовательность Кеане”
Бесконечная последовательность битов, предложенная Кеане, равна
001001110001001110110110001: и формируется следующим алгоритмом: вначале записывается 0, потом 001, далее 001001110, то есть, для получения следующего члена, предыдущий записывается дважды, а справа приписывается его отрицание. Элементы этого ряда являются начальными подпоследовательностями Кеане.
Требуется написать программу, которая по заданному n определит n-й бит этой последовательности.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит число n (nPd10^(200)).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденный бит.
—————————————————————————————————————————–
Задача 8 “Однонаправленная задача коммивояжера”
Задана матрица размером m*n из целых чисел. Путь начинается в любой строке первого столбца и состоит из последовательности шагов, обрывающихся в столбце n. Каждый шаг состоит в переходе из столбца i в столбец i+1 в соседнюю (по горизонтали или диагонали) ячейку. Весом пути называется сумма целых чисел, записанных в каждой из n посещенных ячеек.
Требуется написать программу, которая вычисляет путь с минимальным весом с левого края матрицы до правого.
Технические требования:
Входной файл: INPUT.TXT,
Выходной файл: OUTPUT.TXT,
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит в первой строке количество строк и столбцов матрицы, которые обозначаются m и n соответственно. Далее следует m строк по n чисел в каждой. Числа отделяются друг от друга пробелами. Число строк не превышает 10, столбцов – 100. Вес любого пути не будет превышать целого числа, для хранения которого потребуется больше 30
бит.
Формат выходных данных:
Выходной текстовый файл OUTPUT.TXT должен содержать две строки. Первая строка задает путь минимальной стоимости, а вторая – соответственно стоимость этого пути. Путь состоит из последовательности n целых чисел (разделенных одним или более пробелами), задающих номера строк, из которых состоит путь минимальной стоимости. Если путей минимальной стоимости больше одного, то должен быть выведен лексикографически минимальный путь.
—————————————————————————————————————————–
Задача 9 “Подарки” (20 баллов)
Приближался Новый год и отец купил своим детям по подарку. Оказалось, что в них разное количество конфет. Тогда отец купил еще конфет и стал их раскладывать по подаркам следующим образом: брал подарок с наименьшим количеством конфет и добавлял в него одну конфету.
Требуется написать программу, которая найдет наименьшее количество конфет, оказавшихся в одном из подарков после завершения их раскладывания.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит в первой строке N – количество детей и M – количество купленных конфет. Числа записаны через пробел, 1PdNPd10000, 1PdMPd1000000. Далее в N строках записаны числа в диапазоне от 1 до 30000 – количество конфет в подарках.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать одно найденное число.
—————————————————————————————————————————–
Задача 10 “Ферзя в угол” (20 баллов)
Рассмотрим бесконечную вправо и вверх шахматную доску, на которой стоит ферзь. Двое по очереди двигают этого ферзя. Разрешается двигать ферзя только вниз, влево или по диагонали вниз влево. Цель игры – задвинуть ферзя в угол, то есть клетку с координатами (1, 1). На рисунке показаны разрешенные движения ферзя.
7 Ф
6 a^
5 a^
4 Ф
3 a0
2 a0
1 Ф ss Ф
1 2 3 4 5 6
Требуется написать программу, которая найдет номер игрока, который выиграет при правильной игре.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 5 секунд на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит координаты ферзя перед первым ходом – два числа m и n, записанные через пробел (1Pdm, nPd250).
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденный номер игрока.
—————————————————————————————————————————–
Задача 11 “Сообщение” (20 баллов)
Из пункта А в пункт Б с помощью двух курьеров было отправлено сообщение, состоящее из символов 0 и 1. Каждый из курьеров шутки ради проделал несколько раз следующее преобразование сообщения: любую часть, содержащую две единицы, записал в обратном порядке (перевернул). Например, в сообщении 11010100 курьер мог перевернуть подстроку, составленную из символов со 2 по 5 позиции, и тогда получалось сообщение 10101100. Получив два сообщения в пункте Б решили проверить их эквивалентность, т.е. можно ли получить одно из другого с помощью описанных преобразований.
Требуется написать программу, которая определяет эквивалентность сообщений и, если сообщения эквивалентны, находит способ (достаточно только один) преобразования одного сообщения в другое.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: 3 секунды на один тест.
Формат входных данных:
Входной файл состоит из двух строк – полученных сообщений. Их длина не превышает 100 символов.
Формат выходных данных:
Если сообщения не эквивалентны, то выходной файл должен содержать только строку . Если сообщения эквивалентны, то в первую строку выходного файла нужно вывести слово , в последующие последовательность преобразований
первого сообщения во второе. Каждое преобразование записывается в отдельной строке в виде пары чисел i, j (разделенных пробелом), означающей, что переворачивается подстрока, составленная из символов с номерами i, i+1, …., j.
—————————————————————————————————————————–
Задача 12 “Игра в монеты” (20 баллов)
Гриша и Дима играют в следующую игру: они разложили однокопеечные монетки в стопки (в разных стопках может быть различное количество монет), а стопки расположили на столе перед собой в ряд слева направо. Затем Гриша и Дима по очереди делают ходы. На каждом ходе один из игроков берет слева несколько стопок, не меньше одной, но и не больше, чем перед этим взял его соперник. Первый игрок своим первым ходом берет не более K стопок. Игра заканчивается, когда стопок не остается.
Требуется написать программу, позволяющую вычислить, какое максимальное число монет может получить первый участник после окончания игры, если второй – тоже старается ходить так, чтобы получить как можно больше монет.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: 2 секунды на каждый тест
Формат входных данных:
Входной файл INPUT.TXT состоит из одной строки, в которой записаны: число стопок N (1PdNPd180), за ним идут N чисел, задающих количество монет в стопках слева направо (количество монет в стопке – не менее 1 и не более 20000), а затем число K, ограничивающее количество стопок, которые первый игрок может взять на первом ходе (1PdKPd80). Все числа в строке разделены
пробелом.
Формат выходных данных:
В выходной файл OUTPUT.TXT необходимо вывести одно число – максимальное количество монет, которое заведомо может получить первый игрок, как бы ни играл второй.
—————————————————————————————————————————–
Задача 13 “Расшифровка” (20 баллов)
Компания по защите интеллектуальной собственности решила повысить уровень защищенности своих операционных систем путем шифрования всех сообщений, передаваемых внутри ее локальных сетей. Любое допустимое в компании сообщение представляет собой строку S = sv(1)sv(2):sv(n), состоящую исключительно из букв латинского алфавита. Шифрование сообщения осуществляется в K фаз. На каждой фазе строка S заменяется строкой, в которой сначала располагаются все буквы строки S, стоящие на позициях с номерами, являющимися простыми числами (первый блок), а затем – все остальные буквы (второй блок). Напомним, что число называется простым, если оно – натуральное и имеет ровно два натуральных делителя. Относительный порядок букв в каждом из двух блоков остается неизменным. Например, строка S =ABCDEFGH на первой фазе шифруется в строку S = BCEGADFH. Если осуществляется вторая фаза шифрования, то строка S примет вид S = CEAFBGDH. После передачи зашифрованного сообщения по сети оно должно быть дешифровано, чтобы получатель смог прочитать исходную запись.
Требуется написать программу, осуществляющую дешифрование заданной строки, являющейся результатом шифрования строки S после K фаз.
Технические требования:
Имя входного файла: INPUT.TXT
Имя выходного файла: OUTPUT.TXT
Ограничение по времени тестирования: по 1 секунде на один тест
Формат входных данных:
В первой строке входного файла INPUT.TXT содержится натуральное число K (1 <= K <= 100), вторая строка содержит сообщение S после K фаз шифрования, состоящее из n (1 <= n <= 255) прописных букв латинского алфавита. Регистр букв в процессе шифрования остается неизменным.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать только одну дешифрованную строку S.
—————————————————————————————————————————–
Задача 14 “Шифровка” (20 баллов)
Алиса и Боб решили шифровать свою переписку и начали обсуждать шифр.
Алиса: Предлагаю следующий простой шифр. Буква ‘A’ будет записываться как
1, ‘B’ – 2, и так далее до ‘Z’ – 26.
Боб: Это глупый шифр. Если я пошлю тебе слово ‘BEAN’ (боб), оно будет закодировано как 25114. Но это сообщение можно расшифровать несколькими способами.
Алиса: Ты прав, но другие слова бессмысленны. Кроме ‘BEAN’ получаются слова ‘BEAAD’, ‘YAAD’, ‘YAN’, ‘YKD’ и ‘BEKD’. Я думаю, что можно догадаться о корректной расшифровке.
Боб: Ладно, это был слишком простой пример. А если я пошлю сообщение из 500 цифр или больше, как ты найдешь среди миллиардов возможных расшифровок единственно правильную?
Алиса: Так много? Не может быть…
Требуется написать программу, которая подсчитывает число возможных расшифровок некоторого сообщения, закодированного шифром Алисы.
Технические требования:
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Ограничение по времени тестирования: по 2 секунды на один тест.
Формат входных данных:
Входной текстовый файл INPUT.TXT содержит строку с шифровкой. Шифровка корректна, не начинаются с цифры 0 и может содержать до 1000 цифр.
Формат выходных данных:
Выходной файл OUTPUT.TXT должен содержать найденное число возможных расшифровок. Гарантируется, что число расшифровок меньше 2^(31).
—————————————————————————————————————————–
Задача 15 “Корпорация” (20 баллов)
Структура некоторой корпорации такова, что каждый служащий, кроме служащих нижнего звена, является непосредственным начальником не менее чем одного другого служащего (возможно, служащего нижнего звена). Во главе компании стоит Президент, которому подчиняются либо непосредственно, либо по должностной иерархии все остальные служащие. Каждый служащий (разумеется, кроме Президента) имеет одного непосредственного начальника. Все служащие в этой структуре имеют индивидуальные номера от 1 до N (2 <= N <= 10000). Пример описания такой структуры приведен на рисунке, где сотрудник с номером 3 является Президентом и непосредственным начальником сотрудников с номерами 1 и 4, а сотрудник с номером 4 является непосредственным начальником сотрудника с номером 2. Структура корпорации является корпоративной тайной и строго охраняется. По итогам года Президент компании, довольный работой всех служащих нижнего звена, решил направить в адрес каждого их них благодарственное письмо. Передача писем этим служащим осуществлялась через их непосредственных начальников с использованием сайта корпорации. В результате этого каждый служащий нижнего звена получил благодарственное письмо от Президента компании, но на сайте оказался доступным перечень всех путей следования писем от Президента до каждого служащего нижнего звена.
Требуется написать программу, которая по сведениям, доступным на сайте, восстанавливает структуру корпорации.
—————————————————————————————————————————–
Задача 16 “Перестановки” (20 баллов)
Саша и Федя играют в интересную игру. У них есть n кубиков, на которых написаны различные числа от 1 до n. Ребята нарисовали на бумаге n клеточек в ряд и играют по следующим правилам:
Сначала первый игрок выставляет некоторые кубики на клеточки, затем второй игрок выставляет на свободные клетки оставшиеся кубики. после этого первый игрок делает следующие действия: он смотрит, какое число написано на последнем кубике (пусть это число a) и после этого переставляет последние a кубиков в обратном порядке. Эти действия первый игрок повторяет до тех пор, пока последним не станет кубик с номером 1.
Например, пусть у ребят пять кубиков. Если первый игрок поставил второй и третий кубики на третье и пятое места: <..3.2>, то второй игрок может расставить оставшиеся кубики так: <41352>. В этом случае первому игроку потребуется сделать пять действий: <41325>, <52314>, <54132>, <54123>, <54321>, после чего игра закончится.
Сейчас первым ходил Саша. Требуется написать программу, которая поможет Феде расставить кубики так, чтобы Саша сделал максимально возможное количество действий.
—————————————————————————————————————————–
Задача 17 “Магическая математика” (20 баллов)
В связи с новейшими исследованиями в области нетрадиционных наук в школе Хогварц появился новый предмет – магическая математика. На нем юных магов начали учить, как использовать математические знания для колдовства. Один из видов колдовства заключался в следующем. Есть некая магическая прямоугольная таблица чисел. Колдун должен уметь очень быстро вычислять сумму чисел в любом прямоугольнике внутри этой таблицы и называть ее вслух. Эта задача оказалась для учеников не такой уж простой, и “злобные” учителя начали мучить юных магов огромными домашними заданиями. Чтобы облегчить себе жизнь, юные маги обратились за помощью к учащимся информационного лицея, которые обещали решить эту задачу с использованием современных информационных технологий.
Требуется оказать шефскую помощь ученикам школы Хогварца – написать программу, которая выполняет требуемые вычисления для любой заданной магической прямоугольной таблицы чисел.
—————————————————————————————————————————–
Задача 18 “Числа Смита” (20 баллов)
Просматривая свою телефонную книжку в 1982 году, математик Альберт Вилански обратил внимание, что телефонный номер его родственника Г. Смита обладает следующим забавным свойством: сумма цифр этого номера была равна сумме цифр разложения этого номера на простые множители. Проверим это. Номер телефона Смита был 493-77-75. Это число раскладывается на простые множители следующим образом: 4 937 775=3(5(5(65 837. Сумма цифр телефонного номера равна 4+9+3+7+7+7+5=42, и сумма цифр его разложения на простые множители равна 3+5+5+6+8+3+7=42. Вилански назвал такой тип чисел по имени своего родственника: числа Смита. Так как этим свойством обладают все простые числа, Вилански не включил их в определение. Примерами других чисел Смита являются 6036 и 9985.
Требуется написать программу, которая по заданному числу n найдет
наименьшее из больших n чисел Смита.
—————————————————————————————————————————–
Задача 19 “Счастливые номера” (20 баллов)
Номер из N цифр называется счастливым, если между его цифрами можно расставить знаки ‘+’ и ‘-‘ так, что полученное выражение будет равно 0. Не ставить никакого знака между цифрами нельзя. Лидирующие нули в номере допускаются. В записи номера можно использовать цифры, большие или равные 0 и меньшие P.
Требуется написать программу, которая сосчитает S – количество счастливых номеров из N цифр.
—————————————————————————————————————————–
