Задачи олимпиады "Пробный тур командной олимпиады"
Задача A. Нумеролог
(Время: 1 сек. Память: 16 Мб)
Чтобы предсказать судьбу человека, нумеролог берет время жизни человека в секундах, затем складывает все цифры этого числа. Если полученное число состоит более чем из одной цифры, операция повторяется, пока в числе не останется одна цифра. Затем по полученной цифре и числу операций, необходимых для преобразования числа в цифру нумеролог предсказывает судьбу человека. Нумеролог плохо умеет считать, а числа, с которыми он работает, могут быть очень большими. Напишите программу, которая бы делала все расчеты за него.
Входные данные
Входной файл INPUT.TXT содержит число N – время жизни человека в секундах (1 ≤ N ≤ 101000).
Выходные данные
В выходной файл OUTPUT.TXT выведите два числа через пробел: полученную цифру из числа N и число преобразований.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1
1 0
2
10
1 1
3
99
9 2
Задача B. Игра в числа
(Время: 1 сек. Память: 16 Мб)
Игра в числа ведётся на одномерном массиве целых положительных чисел. Перед началом, жеребьёвкой определяется, кто будет ходить первым (первый игрок), а кто – вторым (второй игрок). Процесс игры состоит в том, что игроки по очереди (сначала первый игрок, затем второй, следом опять первый и так далее) вычёркивают числа из массива. Вычеркнуть можно только число, находящееся в конце или начале оставшегося массива. При этом всегда вычёркивается максимальное число из этих двух. Если первое и последнее числа массива равны, то вычёркивается первое. Игра продолжается до того момента, пока не будут вычеркнуты все числа. Каждое вычеркнутое число идёт в актив тому игроку, который его вычеркнул. После окончания игры каждый игрок суммирует вычеркнутые им числа. Победителем объявляется тот, кто наберет больше очков.
Некоторые игроки поняли, что результат не зависит от стратегии игры, и решили попросить Вас написать программу для получения результата.
Входные данные
В первой строке входного файла INPUT.TXT находится одно целое число N – количество чисел в массиве (1 ≤ N ≤ 104). Во второй строке находятся N целых положительных чисел из диапазона [1, 32000], разделённых пробелом.
Выходные данные
В выходной файл OUTPUT.TXT выведите два числа, разделенные двоеточием. Первое число – количество очков, набираемых первым игроком при игре на этом массиве, второе число – для второго.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
5 4 4 1 5 4
9:9
2
1 1234
1234:0
Задача C. Фермер
(Время: 2 сек. Память: 64 Мб)
Фермер решил на своем квадратном участке земли вспахать пашню квадратной формы максимальной площади, т.к. он посчитал, что именно квадратная форма пашни наиболее удобна для обработки. Но на его участке присутствуют деревья и хозяйственные постройки, которые он никуда не хочет переносить, а так же иные места, не пригодные для пашни. Для удобства он составил квадратную карту местности N×N в форме матрицы и пометил нулями непригодные для пашни зоны, в остальные зоны он поставил единицу.
Необходимо помочь фермеру определить максимальную площадь пашни.
Входные данные
В первой строке входного файла INPUT.TXT записано единственное натуральное число N (1 ≤ N ≤ 1000) – длина стороны квадратного участка фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) нулей и единиц, описывающих ферму.
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь пашни.
Представьте себе пчелиные соты – поле из шестиугольных клеток со стороной N. В верхней левой клетке A находится пчелка. За один ход она может переползти на клетку вниз, на клетку вниз-вправо или на клетку вверх-вправо (вверх и влево пчелка не ползает).
Требуется написать программу, которая найдет количество способов, которыми пчелка может доползти из клетки A в противоположную клетку B.
Входные данные
Входной файл INPUT.TXT содержит единственное число N – размеры шестиугольного поля (2 ≤ N ≤ 12).
Выходные данные
Выходной файл OUTPUT.TXT должен содержать единственное целое число – количество способов.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
2
11
2
3
291
Задача E. Неглухой телефон
(Время: 1 сек. Память: 16 Мб)
Возможно, что Вы когда то играли в игру «Глухой телефон», либо слышали о ней. В этой игре участникам приходится передавать информацию друг другу различными способами: словесно, образно, бывает даже приходится писать левой рукой текст, который другой участник команды должен будет прочитать. Так же известно, что практически никогда передаваемая информация не доходит до конечного адресата. Обозначим за Fi(x) функцию, которая преобразует текст передаваемой информации x в ту, которую получит участник i+1 от участника i. Тогда последний n-й участник получит данные y, которые будут выражаться следующей формулой:
y = Fn-1(Fn-2(…F2(F1(x))))
Но Вам необходимо исключить какие-либо внешние факторы, которые могут исказить исходную информацию и Вы должны реализовать программу «неглухой телефон», которая сможет безошибочно доставлять исходные данные, т.е. в нашем случае функция Fi(x) = x для всех i от 1 до n-1.
Входные данные
В единственной строке входного файла INPUT.TXT записано натуральное число от 1 до 100.
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести в точности то же число, которое задано во входном файле.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
5
5
Задача F. Сортировка времени
(Время: 1 сек. Память: 16 Мб)
Требуется выполнить сортировку временных моментов, заданных в часах, минутах и секундах.
Входные данные
Во входном файле INPUT.TXT в первой строке записано число N (1 ≤ N ≤ 100), а в последующих N строках N моментов времени. Каждый момент времени задается 3 целыми числами - часы (от 0 до 23), минуты (от 0 до 59) и секунды (от 0 до 59).
Выходные данные
В выходной файл OUTPUT.TXT выведите моменты времени, упорядоченные в порядке неубывания без ведущих нулей.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
4
10 20 30
7 30 00
23 59 59
13 30 30
7 30 0
10 20 30
13 30 30
23 59 59
Задача G. НОК
(Время: 1 сек. Память: 16 Мб)
Требуется написать программу, определяющую наименьшее общее кратное (НОК) чисел a и b.
Входные данные
В единственной строке входного файла INPUT.TXT записаны два натуральных числа А и В через пробел, не превышающих 46340.
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно целое число — НОК чисел А и В.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
36 27
108
2
39 65
195
Задача H. Компьютерная игра
(Время: 1 сек. Память: 16 Мб)
Вы можете вспомнить хоть одного своего знакомого до двадцатилетнего возраста, который в детстве не играл в компьютерные игры? Если да, то может быть вы и сами не знакомы с этим развлечением? Впрочем, трудностей при решении этой задачи это создать не должно.
Во многих старых играх с двумерной графикой можно столкнуться с подобной ситуацией. Какой-нибудь герой прыгает по платформам (или островкам), которые висят в воздухе. Он должен перебраться от одного края экрана до другого. При этом при прыжке с одной платформы на соседнюю, у героя уходит |y2-y1| единиц энергии, где y1 и y2 – высоты, на которых расположены эти платформы. Кроме того, у героя есть суперприем, который позволяет перескочить через платформу, но на это затрачивается 3*|y3-y1| единиц энергии. Конечно же, энергию следует расходовать максимально экономно.
Предположим, что вам известны координаты всех платформ в порядке от левого края до правого. Сможете ли вы найти, какое минимальное количество энергии потребуется герою, чтобы добраться с первой платформы до последней?
Входные данные
В первой строке входного файла INPUT.TXT записано количество платформ n (1 ≤ n ≤ 30000). Вторая строка содержит n натуральных чисел, не превосходящих 30000 – высоты, на которых располагаются платформы.
Выходные данные
В выходной файл OUTPUT.TXT запишите единственное число – минимальное количество энергии, которую должен потратить игрок на преодоление платформ (конечно же в предположении, что cheat-коды использовать нельзя).
