Минимальная стоимость проезда

Попытка к бегству

Время на тест - 3 секунды.

Идентификатор для autotest: ol001

Узник пытается бежать из замка, который состоит из MN квадратных комнат, расположенных в виде прямоугольника M×N. Между любыми двумя соседними комнатами есть дверь , однако некоторые комнаты закрыты и попасть в них нельзя. В начале узник находится в угловой комнате и для спасения ему надо попасть в противоположную угловую комнату. Времени у него немного, всего он может побывать не более, чем в M+N-1 комнате, включая начальную и конечную комнату на своем пути, то есть с каждым переходом в соседнюю комнату расстояние до выхода из замка должно уменьшаться. От вас требуется найти количество различных маршрутов, ведущих к спасению.

Формат входных данных

Первая строчка входных данных содержит натуральные числа M и N, не превосходящих 1000. Далее идет план замка в виде M строчек из N символов в каждой. Один символ соответствует одной комнате: если символ равен 1, то в комнату можно попасть, если он равен 0, то комната закрыта. Первоначальное положение узника – левый нижний угол (первый символ последней строки), выход находится в правом верхнем углу (последний символ первой строки, оба этих символа равны 1).

Формат выходных данных

Программа должна напечатать количество маршрутов, ведущих узника к выходу и проходящих через M+N-1 комнату, или слово impossible, если таких маршрутов не существует.

Входные данные подобраны таким образом, что искомое число маршрутов не превосходит 2.000.000.000.

Пример

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

3 5 11111 10101 11111

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

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

3 5 11101 10101 10111

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

impossible

Покер

Время на тест: 1 секунда.

Известное казино хочет поправить свое пошатнувшееся финансовое положение, установив новую модель игровых автоматов "Покер" улучшенного дизайна. Игроку в покер необходимо собрать 5 карт таким образом, чтобы среди них было максимальное количество совпадающих (лучшая комбинация – все пять карт совпадает, а худшая – все различны). К сожалению, главный программист казино недавно неожиданно разбогател, уволился и уехал на Багамы. Без него казино не может решить, как по выпавшему набору карт определить размер выигрыша клиента. Помогите казино справиться с этой задачей.

Формат входный данных

Программа получает на вход 5 целых положительных чисел x₁, x₂, x₃, x₄, x₅, не превосходящих 10⁹.

Формат выходных данных

Программа должны вывести на экран одну из следующих строк:

poker

если все 5 чисел равны

four of a kind

если ровно 4 числа равны между собой

full house

если три из пяти чисел равны между собой и два оставшихся числа равны

three of a kind

если ровно три числа равны

two pairs

если есть две пары равных чисел

one pair

если только два числа равны

all different

если все числа различны

БУДЬТЕ ВНИМАТЕЛЬНЫ ПРИ ВЫВОДЕ СТРОК, НЕ ОШИБИТЕСЬ В НАПИСАНИИ!

Пример

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

7 3 7 7 3

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

full house

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

1000 999 998 997 996

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

all different

Банкомат

Время на тест - 30 секунд.

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

Формат входных данных

Первая строка входных данных содержит натуральное число n, 0<n<=100. Вторая строка входных данных содержит n различных натуральных чисел x₁, x₂, ..., x_n, не превосходящих 1.000.000. Третья строчка содержит натуральное число S, не превосходящее 5.000.000.

Формат выходных данных

Программа должна найти представление числа S в виде суммы слагаемых из множества {x_i}, содержащее минимальное число слагаемых и вывести это представление на экран (в виде последовательности чисел, разделенных пробелами). Если таких представлений существует несколько, то программа должна вывести любое (одно) из них. Если такое представление не существует, то программа должна вывести слово impossible.

Пример

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

5 1 3 7 12 32 40

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

1 7 32

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

5 10 50 100 500 1000 99

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

impossible

Расписание

Время на тест - 5 секунд.

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

Формат входных данных

Первая строка входных данных содержит целое число n, 0<n<=10000. Далее идет n строк, каждая из которых содержит два целых числа s_i и t_i, 0<=s_i<t_i<=30000. Каждая строка соответствует одной заявке с номером i (1<=i<=n), s_i является временем начала заявки, t_i – временем ее окончания.

Программа должна найти подмножество множества {1, 2, ..., n}, содержащее наибольшее число элементов, такое, что для любых двух элементов i и j из найденного подмножества верно одно из двух неравенств: t_i<=s_j

или t_j<=s_i. Указанные неравенства означают, что заявки с номерами i и j не пересекаются, то есть одна из них заканчивается не позднее, чем начинается другая. При этом время окончания одной удовлетворенной заявки может совпадать со временем начала другой заявки (один министр на трибуне меняется на другого министра).

Формат выходных данных

Программа должна вывести номера удовлетворенных заявок в произвольном порядке, разделяя их пробелами. Заявки нумеруются, начиная с 1.

Пример

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

3 1 3 2 4 3 5

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

1 3

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

5 2 6 1 3 1 4 4 5 5 6

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

2 4 5

Игра в 8

Время на тест - 1 секунда.

Всем хорошо известна "Игра в 15", представляющая собой 15 квадратных фишек, пронумерованных числами от 1 до 15. Фишки уложены в квадрат со стороной в 4 стороны фишки, одна позиция для фишки свободна. Если обозначить свободную позицию за *, то головоломка состоит в том, чтобы получить из произвольной начальной позиции позицию следующего вида:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 *

Единственной разрешенной операцией является обмен * с одной из соседних по ребру фишек. Операции будем кодировать буквами:

поменять * с фишкой, которая стоит справа от *

поменять * с фишкой, которая стоит слева от *

поменять * с фишкой, которая стоит сверху от *

поменять * с фишкой, которая стоит снизу от *

Например, решением головоломки

1 2 3 4 5 6 7 8 9 10 12 * 13 14 11 15

является последовательность ldr.

Не все возможные произвольные расположения фишек можно привести к требуемому виду, например, если в требуемой позиции поменять местами две фишки, то получить из такой позиции требуемую используя только описанные операции становится невозможно.

От вас требуется решить более простую головоломку "Игра в 8", в которой требуется расположить 8 фишек в виде:

1 2 3 4 5 6 7 8 *

Формат входных данных

На вход программе подается описание исходной позиции в виде строки, в которой перечислены номера фишек, разделенные пробелами в квадрате слева направо сверху вниз. Вместо свободной фишки напечатана *.

Например, позиция

1 2 3 * 4 6 7 5 8

задается строкой

1 2 3 * 4 6 7 5 8

Формат выходных данных

На выход программа должна вывести одну строку, состоящцю из букв l, r, u, d, содержащую последовательность операций, разрешающую данную головоломку, в которой одна буква соответствует перемещению одной фишки (см. выше правило кодирования операций). Если же головоломка неразрешима, то требуется вывести одно слово unsolvable.

Пример

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

2 3 4 1 5 * 7 6 8

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

ullddrurdllurdruldr

Рациональные дроби

Время на тест - 1 секунда.

Даны две положительные рациональные дроби: a/b и c/d. Найдите их сумму и запишите ответ в виде несократимой дроби.

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

На вход программа получает числа a, b, c и d. Все числа являются положительными и не превосходят 10000.

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

Программа должна вывести два целых положительных числа x и у таких, что дробь x/y — несократима и x/y=a/b+c/d.

Пример входных данных

1 3 2 12

Пример выходных данных

1 2

Ферзя в угол

В левом нижнем углу доски M×N стоит ферзь. Двое игроков по очереди ходят ферзем, перемещая его на любое число клеток по вертикали вверх, по горизонтали вправо, или по диагонали вправо-вверх. Выигрывает тот, кто поставит ферзя в правый верхний угол доски. Определите, какой из игроков имеет выигрышную стратегию.

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

На вход программе подается два положительных числа M и N, не превосходящих 1000.

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

Программа должна вывести номер игрока (1 или 2), который имеет выигрышную стратегию.

Пример входных данных

3 4

Пример выходных данных

Морской бой

На прямоугольном поле для игры в морской бой размером M×N

расположено несколько прямоугольных кораблей. Корабли не соприкасаются друг с другом. Ваша задача — определить всевозможные типы кораблей на поле и число кораблей каждого типа. Два корабля относятся к одному типу, если их размеры совпадают (корабли, которые могут быть получены друг из друга поворотом, также относятся к одному типу).

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

Первая строка входных данных содержит два положительных числа M и N, не превосходящих 1000, задающие размеры поля. Далее идет M строк, каждая из которых состоит из N символов. Символ `1' означает, что соответствующая клетка поля занята кораблем, символ `0' — что свободна. Пробелов в строке нет.

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

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

Пример входных данных

6 10 0111000011 0000011011 0100011000 0101011011 0100000000 0001111011

Пример выходных данных

1 1 1 2 1 2 2 2 2 3 1 2 3 2 1 4 1 1

Цифры Фибоначчи

по мотивам задачи №2 районного тура IX городской олимпиады школьников Санкт-Петербурга по информатике, 1994 г.

Время на тест — 10 секунд.

Все числа Фибоначчи выписали подряд:

1 1 2 3 5 8 13 21 34 55 ...

По данному числу N найдите в этом ряду N-ю цифру.

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

Единственное натуральное число N<10⁶.

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

Цифра с номером N в этом ряду.

Пример входных данных

Пример выходных данных

Распознаватель образов

По мотивам задачи №2 I командного турнира Санкт-Петербурга по программированию, 1993 г.

Время на тест: 1 секунда.

На экране размером 10×10 точек изображена одна из букв C, O, L, I, T, X. Вам необходимо распознать изображенную букву.

Определения букв:

Заполненный прямоугольник.

Заполненный прямоугольник с прямоугольным вырезом внутри, границы вырезов не лежат на сторонах внешнего прямоугольника.

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

Два прямоугольника лежащих друг на друге, левые границы которых совпадают, а правая граница нижнего прямоугольника лежит правее правой границы нижнего прямоугольника.

Два прямоугольника лежащих друг на друге, левая граница верхнего прямоугольника левее нижнего, правая граница верхнего прямоугольника правее нижнего.

Любая другая конфигурация.

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

На вход программе подается 10 строк из 10 символов "0" или "1".

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

Одна из букв I, O, C, L, T, X.

Примеры букв

O L C I T X 0000000000 0111000000 0000000000 0000000000 0011111111 000001110 0111111100 0111000000 0111111100 0000000000 0011111111 000000100 0111111100 0111000000 0111111100 0111111000 0000001110 000000100 0111111100 0111000000 0111000000 0111111000 0000001110 000000000 0110111100 0111000000 0111000000 0111111000 0000001110 000000000 0111111100 0111000000 0111000000 0000000000 0000001110 001110000 0111111100 0111000000 0111000000 0000000000 0000001110 001000000 0111111100 0111000000 0111111100 0000000000 0000000000 001110000 0111111100 0111000000 0000000000 0000000000 0000000000 000000000

Номера страниц

Задача 2 районного тура XV городской олимпиады школьников Санкт-Петербурга по информатике, 1999 г.

Время на тест — 1 секунда.

В последнем издании британской энциклопедии N страниц, на каждой странице стоит ее номер. Сумасшедший наборщик подсчитал, что для набора всех номеров страниц понадобилось M литер. Ваша задача по данному числу литер M, 1≤M≤10⁹, определить число страниц N. Число M таково, что ему соответствует некоторое число N. На вход программе подается число M, программа должна вывести число N.

Пример входных данных

Пример выходных данных

Шестеренки

Задача B районного тура X городской олимпиады школьников Санкт-Петербурга по информатике, 1995 г.

Время на тест — 10 секунд.

На плоскости расположена система из N одинаковых шестеренок, которая приводится в движение вращением шестеренки 1 по часовой стрелке (`clockwise'). Требуется определить направление вращения каждой шестеренки системы, либо установить, что систему заклинит.

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

Первая строка входных данных содержит число шестеренок N, 1<N≤1000.

Вторая строка содержит число M. Далее идет M строк, каждая из которых содержит два различных числа i и j, означающих, что шестеренки с номерами i и j сцеплены. При этом каждая шестеренка сцеплена не более, чем с 6 другими шестеренками. Также гарантируется, что все шестеренки соединены с первой через несколько других шестеренок (то есть в незаклиненной системе будут вращаться все шестеренки).

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

Программа должна вывести на экран N строк. Строка с номером i должна содержать слово `clockwise', если шестеренка i вращается по часовой стрелке или слова `counter-clockwise' в противном случае. Если систему заклинит, то программа не должна выводить ничего.

Пример входных данных

5 5 1 2 2 3 5 3 2 4 4 5

Пример выходных данных

clockwise counter-clockwise clockwise clockwise counter-clockwise

Примечание

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

13 "Ну, погоди!" на катке

Задача G XI городской олимпиады школьников Санкт-Петербурга по информатике, 1996 год

Время на тест — 1 секунда.

Заяц стоит в центре большого катка и поет свою любимую песенку в игрушечный микрофон. От микрофона тянется достаточно длинный шнур, конец которого находится в руках у Волка. Волк хочет незаметно замотать Зайца этим шнуром. Для этого он катается вокруг Зайца на коньках и постепенно его заматывает. Траектория Волка — ломаная линия. При перемещении Волка микрофонный шнур всегда натянут (как будто он эластичный).

Напишите программу, которая по заданной траектории Волка определяет на сколько полных оборотов Волк замотал Зайца. Учтите, что Волк во время движения может не только заматывать Зайца, но и разматывать, а также что заматывать Зайца можно в двух различных направлениях.

Заяц первоначально находится в точке (0,0), Волк — в точке (1,0). Координаты представляются вещественными числами. Гарантируется, что траектория Волка не проходит через начало координат (местоположение Зайца).

Формат входных данных

Первая строка входных данных содержит число N≤1000, задающее число звеньев в ломаной траектории Волка. Далее идет N строк, i-я строка содержит 2 действительных числа x_i и y_i, задающие координаты i+1-й вершины траектории.

Формат выходных данных

Программа должна вывести единственное число — количество полных оборотов.

Пример входных данных

3 -3 3 -1 -1 2 1

Пример выходных данных

Математический кружок

По мотивам задачи B VIII командного чемпионата школьников Санкт-Петербурга по программированию, 2000 год

Время на тест — 10 секунд.

На математический кружок пришли школьники, которые были разбиты на N групп. В i-й группе оказалось X_i школьников. В школе есть M аудиторий, в j-ю аудиторию можно посадить не более, чем Y_j школьников.

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

Формат входных данных

Первая строка входных данных содержит числа N и M, 1<N<M<1000. На второй строчке расположено N чисел X_1, ..., X_N, на третьей строчке расположено M чисел Y_1, ..., Y_M. Числа X_i, Y_j — натуральные, не превосходящие 1000.

Формат выходных данных

В первой строчке программа должна вывести количество групп, которые удастся рассадить по аудиториям. На второй строчке необходимо вывести распределение групп по аудиториям — N чисел, i-е число должно соответствовать номеру аудитории, в которой должна заниматься i-я группа. Нумерация как аудиторий, так и групп ведется с 1. Если i-я группа осталась без аудитории, то i-е число должно быть равно 0. Если допустимых решений несколько, то требуется вывести одно (произвольное) из них.

Пример входных данных

3 4 5 3 4 2 4 2 5

Пример выходных данных

2 0 2 4

15 Нули на конце n!

Время на тест: 1 секунда.

Оценка: 30 баллов.

Срок сдачи: четверг, 6 мая, 16.00.

По данному числу n определите, каким количеством нулей заканчивается десятичная запись числа n! .

Формат входных данных

Программа получает на вход единственное натуральное число n, 1<=n<=10⁹ и должна вывести единственное натуральное число.

Пример

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

100

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

Рифмы

Время на тест: 1 секунда.

Оценка: 50 баллов. Если программа проходит только тесты (все или часть из них) с ответом “0”, то она получает 0 баллов.

Срок сдачи: четверг, 6 мая, 16.00.

Дан текст (набор слов). Найдите в нем два слова с наилучшей рифмой. Наилучшей будем считать рифму, когда у пары слов совпадает наибольшее число букв с конца.

Формат входных данных

Первая строчка входных данных содержит натуральное число n, 2<=n<=10000. Затем идет n различных строк, каждая из которых содержит одно слово (слова могут состоять из латинских и русских букв в кодировке KOI-8, заглавные и строчные буквы считаются различными).

Формат выходных данных

Программа должна вывести в одной строчке число последних совпадающих букв в наилучшей рифме, затем (через пробел) два слова, образующих эту рифму. Если существует несколько наилучших рифм, то программа должна вывести только одну (любую) пару из них. Если никакие два слова входного текста не рифмуются между собой, программа должна вывести одно число 0.

Примеры

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

2 олимпиада программирование

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

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

8 зеленый том ученый кругом направо заводит налево говорит

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

4 зеленый ученый

Странная математика

Время на тест: 1 секунда.

Оценка: 40 баллов.

Срок сдачи: четверг, 13 мая, 16.00.

В связи с реформой образования в тридесятом царстве был введен новый предмет, на котором изучаются различные альтернативные науки. Одной из таких наук является странная математика. Ее основное отличие от обычной математики в том, что числа в ней упорядочены не по возрастанию, а лексикографически, то есть как в словаре (сначала по первой цифре, затем, при равной первой цифре – по второй, и так далее). Кроме того, рассматривается не бесконечное множество натуральных чисел, а лишь первые n чисел. Так, например, если n=11, то числа в странной математике оказываются упорядочены следующим образом: 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9.

Помогите ученикам в изучении этой науки – напишите программу, которая по заданному n находит место заданного числа k в порядке, определенном в странной математике. Например, если n=11 и k=2, программа должна выдать в качестве ответа 4.

Формат входных данных

Первая строка входный данных содержит натуральное число n, 1<=n<=10^9. Вторая строка входных данных содержит натуральное число k, 1<=k<=n.

Формат выходных данных

Программа должна вывести единственное натуральное число – номер числа k среди первых n натуральных чисел в лексикографическом порядке.

Пример

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

11 2

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

Восстановление скобок

Время на тест: 1 секунда.

Оценка: 60 баллов. Если программа проходит только тесты (все или часть из них) с ответом “0”, то она получает 0 баллов.

Срок сдачи: четверг, 13 мая, 16.00.

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

Определение: правильное скобочное выражение состоит из круглых скобок. Пустая последовательность является правильным скобочным выражением. Если A – правильное скобочное выражение, то (A) – правильное скобочное выражение. Если A и B – правильные скобочные выражения, то AB – правильное скобочное выражение. Например, последовательность "(())()" является правильным скобочным выражением, а последовательность "())(()" – нет.

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

Формат входных данных

На вход программа получает строку, состоящую из круглых скобок и знаков вопроса. Длина строки не превышает 1000 символов.

Формат выходных данных

Программа должна вывести единственное целое число – количество способов, которым можно в данной строке заменить знаки вопроса на скобки так, чтобы получилось правильное скобочное выражение. Входные данные подобраны так, что это число не превышает 10^9.

Пример

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

????(?

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

Микрофоны

Время на тест: 1 секунда.

Оценка: 50 баллов.

Срок сдачи: четверг, 20 мая, 16.00.

Зал Большого театра столь велик, что артистам при выступлении необходимо иметь радиомикрофоны.

В начале и конце спектакля все артисты находятся за кулисами. Артисты выходят на сцену и покидают сцену через правую или левую кулису, при этом артист берет с собой один микрофон. Уйдя со сцены, артист оставляет микрофон за той кулисой, через которую он ушел.

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

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

Формат входных данных

Первая строка входный данных содержит натуральное число n, 1<=n<10000. Далее идет n строк – инструкции для артистов. Каждая строка состоит из двух чисел и двух букв. Первое число – время выхода артиста от начала спектакля в секундах, второе число – время ухода артиста со сцены. Потом идет одна из двух букв "l" или "r" в зависимости от того, через какую кулису (левую или правую) приходит артист и еще одна буква, указывающая через какую кулису уходит артист. Например, строка "300 500 l r" означает, что актер выходит на сцену в момент времении 300 через левую кулису и уходит со сцены в момент 500 через правую кулису.

Времена приходов и уходов – целые неотрицательные числа, не превосходящие 10000. Строки во входном файле могут идти в произвольном порядке, не обязательно упорядоченные по времени. Если в один и тот же момент один артист уходит за кулису, а другой выходит из-за этой же кулисы, то он может передать ему микрофон в этот момент.

Формат выходных данных

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

Пример

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

3 0 100 l r 50 150 l l 100 200 r l

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

2 0

Испорченная сумма

Время на тест: 1 секунда.

Оценка: 70 баллов. Если программа проходит только тесты (все или часть из них) с ответом "impossible", то она получает 0 баллов.

Срок сдачи: четверг, 13 мая, 16.00.

Во время контрольной работы по математике Вася попросил отличника Петю подсказать ему решение задачи, и тот прошептал ему подсказку, представляющую собой арифметическое выражение вида A+B=C, где A, B, C – натуральные числа. При этом Вася не расслышал все цифры чисел, поэтому некоторые цифры этого выражения остались Васе неизвестны. Помогите Васе восстановить это арифметическое выражение.

Формат входных данных

Входные данные представляют собой текстовую строку вида A+B=C, где A, B, C – последовательности, состоящие из цифр и знаков вопроса. Длина входной строки не превосходит 1000 символов.

Формат выходных данных

Программа должна вывести решение – верное равенство, получаемое из исходного уравнения заменой знаков вопроса на цифры. Если таких решений несколько – программа должна вывести одно (любое) из них. Если решений нет, программа должна напечатать строку "impossible".

Примеры

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

?0?+?01=1??

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

009+101=110

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

2+?=1

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

impossible

Разминирование

Задача 1 Московской командной олимпиады по программированию, 2002 год

Время на тест - 1 секунда.

Решил как-то Иванушка-дурачок навестить Змея Горыныча. Пришел он к замку, а перед воротами минное поле раскинулось. Причем поле не простое, а волшебное – мины расположены в узлах регулярной решетки. Однако, была у Иванушки лягушка-сапер, работающая по следующему алгоритму. Лягушка прыгает с мины на мину, разряжая ту, на которой сидит. Если она видит, что перед ней нет мины, или мина перед ней разряжена, она поворачивается на 90 градусов вправо. Если вокруг лягушки не остается заряженных мин, то она останавливается. Перед тем как запускать свою лягушку, решил Иванушка определить где она остановится. Для этого он ввел систему координат, причем ось x оказалась направлена вправо, а ось y – вверх. Потом он обнаружил, что мины оказались расположены в точках с координатами (i, j), причем 1<i<N;1<=i<=N, 1<j<M;1<=j<=M, а лягушка изначально находится в точке (1,1) и смотрит по оси y. Требуется определить координаты точки, в которой остановится лягушка.

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

Программа получает на вход два натуральных числа N и M, не превосходящие 10⁶.

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

Программа должна вывести два натуральных числа – координаты точки, где остановится лягушка.

Пример входных данных

3 4

Пример выходных данных

2 3

Забавная игра

Задача D заочного тура Московской олимпиады по программированию, 2003

Время на тест - 1 секунда.

Легендарный учитель математики Юрий Петрович придумал забавную игру с числами. А именно, взяв произвольное целое число, он переводит его в двоичную систему счисления, получая некоторую последовательность из нулей и единиц, начинающуюся с единицы (Например, десятичное число 19 в двоичной системе запишется как 10011). Затем учитель начинает сдвигать цифры полученного двоичного числа по циклу (так, что последняя цифра становится первой, а все остальные сдвигаются на одну позицию вправо), выписывая образующиеся при этом последовательности из нулей и единиц в столбик – он подметил, что независимо от выбора исходного числа получающиеся последовательности начинают с некоторого момента повторяться. И, наконец, Юрий Петрович отыскивает максимальное из выписанных чисел и переводит его обратно в десятичную систему счисления, считая это число результатом проделанных манипуляций. Так, для числа 19 список последовательностей будет таким:

10011

11001

11100

01110

00111

10011

и результатом игры, следовательно, окажется число 28 (11100₂). Поскольку придуманная игра с числами все больше занимает воображение учителя, отвлекая тем самым его от работы с ну очень одаренными школьниками, вас просят написать программу, которая бы помогла Юрию Петровичу получать результат игры без утомительных ручных вычислений.

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

Программа получает на вход единственное натуральное число, не превосходящее 10^{9Выходные данные}

Программа должна вывести единственное натуральное число – результат игры.

Марсоход

По мотивам одной из задач Московской студенческой командной олимпиады

Время на тест - 1 секунда.

Марсоход передвигается по поверхности Марса в поисках следов жизни и передает на Землю сигналы о своем перемещении. Вам необходимо определить местоположение марсохода в момент прекращения передачи.

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

На вход программа получает не более 1000 строк, содержащих одну из следующих команд:

FORWARD N

Передвинуться вперед на N единиц длины. N — натуральное число, не превосходящее 1000. Одна единица длины равна 1/4 длины экватора Марса, Марс считается правильным шаром.

RIGHT

Повернуться вправо на 90 градусов.

LEFT

Повернуться влево на 90 градусов.

После чего идет команда STOP, указывающая на завершение входных данных.

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

Марсоход завершит свой путь в одной из 6 точек. Программа должна вывести номер этой точки в соответствии со списком:

0 Исходная точка

1 Точка, в которую попадет марсоход после выполнения команды FORWARD 1

2 Точка, в которую попадет марсоход после выполнения команды FORWARD 2

3 Точка, в которую попадет марсоход после выполнения команды FORWARD 3

4 Точка, в которую попадет марсоход после выполнения команд RIGHT, FORWARD 1

5 Точка, в которую попадет марсоход после выполнения команд LEFT, FORWARD 1

Пример входных данных

FORWARD 1

LEFT

FORWARD 2

STOP

Пример выходных данных

Троллейбусы

Время на тест - 3 секунды.

Троллейбусы одного маршрута проходят через остановку каждые k (1<=k<500) минут. Известны времена прихода пассажиров на эту остановку. Если пассажир приходит на остановку в момент прихода троллейбуса, то он успевает уехать на нем.

Напишите программу, которая бы определяла, во сколько должен пройти первый троллейбус (это время от 0 до k-1), чтобы:

1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально.

2) Максимальное из времен ожидания троллейбуса было минимально.

Формат входных данных

Во входном потоке записано сначала число k, затем – число N (0<=N<100000). Затем идет N чисел, задающих времена прихода пассажиров на остановку. Каждое из этих чисел – целое от 0 до 100000.

Формат выходных данных

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

Пример входных данных

100 5

0 210 99 551 99

Пример выходных данных

25 Нули на конце на конце n!-2

Задача 3 Московской городской олимпиады по программированию, 2003 год

Время на тест - 3 секунды.

По данным числам n и k определите, на сколько нулей заканчивается запись числа n! в k-ичной системе исчисления.

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

На вход программа получает числа n, 1<=n<=10₉

и k, 2<=k<=5000. Оба числа записаны в десятичной системе счисления.

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

В выходной файл вывести количество нулей, которыми в k-ричной системе счисления заканчивается число n!. Ответ вывести в десятичной системе счисления.

Пример

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

10000 10 2499

10000 2 9995

123456789 4800 15432096

27110307 4107 376531

Минимальная стоимость проезда

Время на тест - 10 секунд.

На прямой ветке железной дороги расположено несколько станций. Задана стоимость проезда между любыми двумя станциями. Необходимо определить наименьшую стоимость проезда между двумя самыми крайними станциями. Двигаться по железной дороги можно только в одном направлении.

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

Первая строка входных данных содержит натуральное число N<=1000. Всего на дороге расположена N+1 станция, пронумерованные от 0 до N. Далее идет N(N+1)/2 строк, задающих стоимости проезда между станциями: сначала стоимость проезда от станции 0 до станций 1, 2, 3, ..., N, затем от станции 1 до станций 2, 3, ..., N, и последняя строка – стоимость проезда между станциями N-1 и N. Все стоимости проезда – натуральные числа, не превосходящие 1000.

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

Программа должна вывести единственное число – минимальную цену, за которую можно проехать от станции с номером 0, до станции с номером N с возможными пересадками. Передвигаться можно только от станции с меньшим номером до станции с большим номером.

Пример входных данных

Всего 4 города, оптимальный маршрут проходит через станции 0, 2 и 3.

Пример выходных данных

Кратчайший путь коня

Время на тест – 1 секунда.

Идентификатор для autotest – ol027.

Найдите кратчайший путь коня между двумя заданными клетками на шахматной доске.

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

Программа получает на вход координаты начальной и конечной клетки. Каждая координата состоит из латинской буквы a-h и цифры 1-8, написанных слитно.

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

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

Пример входных данных

Пример выходных данных

Дата добавления: 2021-02-10; просмотров: 422; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 Следующая ⇒

Мы поможем в написании ваших работ!