Задача 1. В ожидании Нового года

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

31 декабря. Марфа Геннадьевна и Глафира Сергеевна уже приготовили новогодний ужин, и теперь они с нетерпением ждут Нового года.

Каждые 5-10 минут они смотрят на часы и вычисляют, сколько часов и минут осталось до Нового года. При этом на вычисление у них уходит много времени.

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

Число секунд в текущем времени принять равным 0.

Формат входного файла

Входной файл содержит текущее время — часы и минуты.

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

Требуется вывести в выходной файл, сколько времени осталось до Нового года — часы и минуты.

Ограничения

Часы от 0 до 23. Минуты от 0 до 59.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
12 0
12 0
2
23 59
0 1
3
22 25
1 35

Задача 2. Куб со спицами

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Возьмём N3 одинаковых кубиков. Раскрасим кубики в N цветов так, чтобы в каждый цвет было раскрашено ровно N2 кубиков. Сложим из всех кубиков один большой куб. Начнём протыкать этот куб спицами параллельно его рёбрам. Любая спица пройдёт сквозь ровно N кубиков.

Требуется сложить куб так, чтобы любая спица проходила сквозь кубики всех N цветов.

Формат входного файла

Во входном файле содержится единственное натуральное число N.

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

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

Ограничения

1 ≤ N ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
1 2
2 1
2 1
1 2

Задача 3. Отгадай слово

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Хрюша и Степашка играют в игру "Отгадай слово". Правила игры просты. Хрюша придумывает слово, состоящее из букв латинского алфавита, придумывает загадку и загадывает её Степашке. Задача Степашки — отгадать слово.

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

Ход Степашки заключается в том, что Степашка называет любую букву латинского алфавита.

  1. Если такая буква есть в слове и все такие буквы закрыты, то все они открываются.
  2. Если такая буква есть в слове и все такие буквы открыты, то все они закрываются.
  3. Если такой буквы нет в слове, то никакие буквы не открываются и не закрываются.

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

Формат входного файла

Входной файл содержит ровно две строки.

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

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

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

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

Если i-я буква открыта, то i-й символ выходной строки должен совпадать с i-м символом первой строки входного файла.

Если же буква закрыта, то соответствующий символ выходной строки должен быть '.' (точка).

Ограничения

Количество букв в слове от 1 до 15.

Количество ходов Степашки от 1 до 20.

Входные данные таковы, что если в ходе игры Степашка отгадал все буквы слова, то игра заканчивается и Степашка больше не называет буквы (входной файл на этом заканчивается).

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
frog
or
.ro.
2
frog
oro
.r..
3
frog
fffrrroooog
fr.g
4
frog
golf
f.og
5
frog
gorf
frog

Задача 4. Кепка

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Если положить α  = 0, то поверхность K будет описываться формулами в последней строке, где нужно принять z равным 0.

Вот пример кепки при R = 10, L = 20.

Ваша задача — найти площадь поверхности кепки, видимой сверху.

Формат входного файла

Входной файл содержит целые числа R L.

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

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

Ограничения

1 ≤ R ≤ L ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
10 20
785.39816340
2
10 10
628.31853072

Задача 5. В пределе

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Здесь вы можете нарисовать звездочку.

Пусть числа R, r фиксированы. Площадь фигуры, ограниченной звездой с n лучами, обозначим через Sn. Положим S = limn ↦ ∞Sn.

Формат входного файла

Входной файл содержит вещественные числа R r.

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

Выходной файл должен содержать число S с точностью не менее 3 знаков после десятичной точки.

Ограничения

0 < r ≤ R ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 0.4
1.25664

Задача 6. Двоичные последовательности

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Здравствуй, юный падаван!

Прошу тебя вывести все двоичные последовательности длины N.

Реши задачу двумя способами:

Да пребудет с тобой произведение массы на ускорение!

Формат входного файла

Входной файл содержит единственное целое число N.

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

Требуется вывести в выходной файл все двоичные строки длины N в лексикографическом порядке, по одному в каждой строке.

Ограничения

1 ≤ N ≤ 15

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
00
01
10
11

Задача 7. Принтер - 2

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Аполлинарий Матвеевич недавно купил новый принтер и решил распечатать на нём одну главу из своей любимой книги по микроэлектронике.

Входной и выходной лотки принтера горизонтальные. Принтер работает так: стопка бумаги загружается во входной лоток, принтер берёт по очереди листы от верхнего до нижнего и печатает на них страницы от последней до первой. Принтер печатает на той стороне листа, которая находится сверху во входном лотке, и в выходном лотке эта сторона листа тоже будет сверху. Таким образом, если положить в лоток 3 чистых листа бумаги и распечатать страницы с 1-й по 3-ю, то в выходном лотке страницы будут в таком порядке: 1, 2, 3.

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

Возможные дефекты:

  1. При перелистывании распечатки может оказаться, что страницы расположены в неправильном порядке: 2, 1, 4, 3, ... вместо 1, 2, 3, 4, из-за чего приходится переворачивать каждый лист.
  2. Первый лист может оказаться пустым с одной стороны, и Аполлинарий Матвеевич хочет, чтобы пустота была только на последнем листе.

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

Коды инструкций:

Формат входного файла

Входной файл содержит целые числа a b.

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

Выходной файл должен содержать последовательность инструкций, разделённых пробелами.

Ограничения

1 ≤ a ≤ b ≤ 1000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1
1 -1 100
2
1 10
2 -1 3 -2 1 -1 100

Задача A. Марфа Геннадьевна ест яйца

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

У Марфы Геннадьевны есть любимая курица, которую она назвала Марфой. В определённые дни Марфа давала по яйцу, и Марфа Геннадьевна в тот же день съедала его. Марфа Геннадьевна записывала, в какие дни Марфа давала яйцо.

Однажды Марфа Геннадьевна где-то прочитала, что рекомендуется съедать не более двух яиц в неделю. Марфа Геннадьевна заинтересовалась, нарушала ли она хоть раз это правило, то есть найдётся ли промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

Напишите программу, принимающую на вход список номеров дней, в которые Марфа Геннадьевна съедала яйца, и определяющую, съедала ли она хоть раз более двух яиц в неделю.

Формат входного файла

Входной файл содержит целое число N.

Далее следуют N целых чисел ai — номера дней, в которые Марфа Геннадьевна съедала яйцо.

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

Требуется вывести в выходной файл слово GOOD, если Марфа Геннадьевна съедала не более двух яиц в неделю, и слово BAD, если найдётся хотя бы один промежуток из семи подряд идущих дней, в который она съедала более двух яиц.

Ограничения

1 ≤ N ≤ 100

1 ≤ a1 < a2 < … aN ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 7 8
GOOD
2
5
1 7 9 12 17
BAD

Задача B. Многократное суммирование

Автор:Г. Гренкин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Дан массив целых чисел a1, a2, ..., aN и дано M команд типа "найти сумму чисел ai для i от l до r".

Требуется написать программу, выполняющую данные команды.

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел ai.

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел lj rj.

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

Выходной файл должен содержать M целых чисел — результаты выполнения команд.

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ ai ≤ 1000

1 ≤ lj ≤ rj ≤ N

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
1 2 3 4 5
3
1 3
2 5
3 5
6 14 12

Задача C. Количество каждого числа

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Вася записал в файл input.txt N чисел. Когда Петя открыл этот файл, он решил посчитать, сколько раз в файле записано каждое число.

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

Заметим, что это позволяет выполнить сортировку массива чисел по возрастанию при помощи простого подсчёта.

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел ai.

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

Выходной файл должен содержать пары чисел: число из входного файла и количество раз, сколько оно встретилось в файле.

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ ai ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
1 2 1 0
0 1
1 2
2 1
2
7
9 1 3 2 3 -2 7
-2 1
1 1
2 1
3 2
7 1
9 1

Задача D. Деревья

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Даны значения высот N деревьев аллеи. Требуется найти два дерева, сумма высот которых максимальна и при этом расстояние между ними не меньше d. Расстояние — это разница порядковых номеров деревьев.

Формат входного файла

Входной файл содержит целые числа N d, за которым следуют N целых чисел ai — высоты деревьев.

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

Требуется вывести в выходной файл единственное целое число — максимальную сумму высот деревьев, расстояние между которыми не меньше d.

Ограничения

2 ≤ N ≤ 100000.

1 ≤ d ≤ N − 1.

1 ≤ ai ≤ 109.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7 4
3 4 5 6 7 1 2
10
2
5 3
1 2 3 4 1
5

Задача E. Марфа Геннадьевна и документы

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

У Марфы Геннадьевны есть папка с файлами (не компьютерная, а обычная), в которую она складывает свои документы. Марфа Геннадьевна пронумеровала свои документы от 1 до N и уже привыкла к тому, что у неё в первом файле лежит первый документ, во втором файле — второй и т.д.

Однажды к Марфе Геннадьевне пришёл в гости внук и стал рассматривать её документы. Разумеется, после этого документы оказались не на своих местах.

Теперь Марфа Геннадьевна хочет переложить документы в правильном порядке так, чтобы минимизировать количество выкладываний и вкладываний документов. Также требуется, чтобы при перекладываниях каждый раз вне папки находилось не более двух документов (чтобы не потерять документы).

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

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел ai, где число ai означает, что в i-м файле лежит документ с номером ai.

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

Выходной файл должен содержать целое число K — количество выкладываний и вкладываний документов.

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

Ограничения

1 ≤ N ≤ 105, 1 ≤ ai ≤ N. Все числа ai различны.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 3 2
4
-3 2
-2 3
3 3
2 2
2
4
1 4 2 3
6
-4 2
-3 4
4 4
-2 3
3 3
2 2
3
3
1 2 3
0

Задача F. Арифметическая прогрессия

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

Формат входного файла

Входной файл содержит целое число N — количество чисел, за которым следуют N целых чисел ai.

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

Выходной файл должен содержать целое число M — количество чисел, которые останутся после вычёркивания (при этом количество вычеркнутых чисел должно быть минимальным).

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ ai ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
7
1 3 4 2 7 8 10
4
1 3 5 7

Задача G. Перевод длинных чисел

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:4 Мб
Выходной файл:output.txt  

Условие

Дано неотрицательное целое число a, записанное в системе счисления по основанию p. Требуется перевести это число в систему счисления по основанию q. Для представления цифр больше 9 используются заглавные латинские буквы (A — 10, B — 11, …, Z — 35).

Формат входного файла

Первая строка содержит числа p q. Вторая строка содержит строку, представляющую число (a)p.

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

Выходной файл должен содержать единственную строку, представляющую (a)q без незначащих нулей в начале.

Ограничения

2 ≤ p, q ≤ 36, длина входной строки не превышает 1000 символов.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 10
10010
18
2
31 17
AF2J5
6DG3BE

Задача H. НОД и числа Фибоначчи (исправленная)

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

k-тым числом Фибоначчи называется k-тый член последовательности Fk = Fk − 1 + Fk − 2 , F0 = 0 , F1 = 1

Формат входного файла

Во входном файле находятся два числа n и k

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

В выходном файле должно содержаться единственное число — наибольший общий делитель Fn и Fk.

Ограничения

1 ≤ n, k ≤ 200

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 2
1
2
6 9
2

Problem I. Digitalization

Input file:input.txt   Time limit:2 sec
Output file:output.txt   Memory limit:64 Mb

Statement

Define the function rm sum_of_digits(a) 〈 a ∈ N0〉   = ki = 0ai where {ai} is the representation of a in the numeral system with radix 10.

Define the function:

rm digitalization(a) 〈 a ∈ N0〉   = {
  bf if  rm sum_of_digits(a) ∈ 0..9  {
   bf return  rm sum_of_digits(a)
  }
  bf else  {
   bf return  rm digitalization(rm sum_of_digits(a))
  }
}

Your problem is to find rm digitalization(n!) for given n.

Input file format

n

Output file format

rm digitalization(n!)

Constraints

1 ≤ n ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
2
2
3
6

Задача J. Митинг

Автор:Виртуальная реальность   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Чем больше число, тем выше уровень мастерства персонажа в соответствующей области.

Считается, что, i-й персонаж является кандидатом на должность председателя в том и только том случае, когда для него не найдётся такого j-того персонажа, что одновременно mj > mi, pj > pi, tj > ti.

Напишите программу, составляющую список кандидатов на роль председателя.

Формат входного файла

Входной файл содержит натуральное число n  — количество персонажей. Далее следует n троек натуральных чисел mi pi ti.

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

Требуется вывести в выходной файл номера отобранных персонажей в порядке возрастания.

Ограничения

1 ≤ n ≤ 105

1 ≤ mi, pi, ti ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
4
2 3 4
1 1 3
2 1 8
3 2 10
1 4

Задача K. Две пешки и слон

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

Формат входного файла

Входной файл содержит числа x1 y1 x2 y2 — координаты первой и второй пешек.

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

Если задача имеет решение, то выходной файл должен содержать два числа — координаты слона. Если решений несколько, вывести любое из них. Если задача не имеет решения, вывести единственное число 0.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 6 7 5
0
2
3 4 5 6
4 5
3
4 5 5 6
0

Задача L. WK

Автор:Виртуальная реальность   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В рамках социального проекта ЦПД в кампусе ДВФУ была организована социальная сеть WK, чтобы студенты могли обмениваться через неё учебными материалами и решать все насущные вопросы.

У каждого пользователя этой сети есть список контактов. Однажды в сеть WK поступил вброс о том, что студентам стали снижать оценки за лайки не(у)годным преподавателям.

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

Итак, однажды утром админ группы "Учеба каждый день, какой ужас" переслал всем своим контактам этот мем. Вечером его контакты получили мем.

Затем информация распространялась по сети WK следующим образом.

  1. Сообщения отправляются только утром, а получаются только вечером.
  2. Если пользователь B получил информацию от пользователя A, то утром следующего дня пользователь B разошлёт эту информацию всем своим контактам, от которых он не получал эту информацию и которым он не отправлял эту информацию.

Социальная сеть WK устроена таким образом, что если пользователь B находится в списке контактов пользователя A, то и пользователь A находится в списке контактов пользователя B. Никакой пользователь не может находиться в своём же списке контактов.

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

Формат входного файла

Первая строка входного файла содержит целое число N — количество пользователей социальной сети WK.

Далее для каждого пользователя во входном файле записана следующая информация. Сначала идёт целое число ki — количество пользователей в списке контактов пользователя i, за которым следуют ki различных целых чисел от 1 до N — номера пользователей из списка контактов i-го пользователя.

Админ группы "Учеба каждый день, какой ужас", он же админ группы "Стримы от Малявина" — это пользователь с номером 1.

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

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

Ограничения

1 ≤ N ≤ 100.

0 ≤ ki < N.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
2  2 3
1  1
1  1
0 1 1
2
3
2  2 3
2  3 1
2  1 2
0 2 2
3
6
1  2
3  1 3 4
2  5 2
2  2 5
2  4 3
0
0 1 1 1 2 0

Задача M. Лабиринт

Автор:Общеизвестная   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

Лабиринт задан как двумерный массив символов '.' и '#', означающих пустое пространство и стену соответственно. В любой не занятой стеной клетке может находиться Искатель. Ему разрешено перемещаться по клеткам лабиринта в четырех направлениях: вверх, вниз, влево и вправо. Покидать лабиринт через внешнюю границу запрещено, ибо за его пределами находится сплошная стена. Требуется написать программу, которая по заданному лабиринту определяет существует ли путь от входа к выходу.

Формат входного файла

Первая строка входного файла содержит числа N и M - количества строк и столбцов в описании лабиринта соответственно. В следующих N строках содержатся по M символов из множества '.' (пустое пространство) , '#' (стена), 'S' (вход), 'F' (выход). В описании лабиринта присутствует ровно один символ 'S' и ровно один 'F'.

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

Выведите в выходной файл текстовую строку 'YES', если существует путь от входа к выходу и 'NO' в противном случае.

Ограничения

1 ≤ N,M ≤ 1000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
S#.
.#F
...
YES
2
3 3
S#.
.#F
#..
NO

Задача N. Лабиринт

Автор:Кленин А.   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

Формат входного файла

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

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

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

1 ≤ N ≤ 1500, левый верхний угол лабиринта всегда свободен.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2
.#
..
2
2
2
.#
#.
-1

Задача O. Марфа Геннадьевна и angry birds

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Недавно Марфа Геннадьевна увидела у внука на компьютере игру Angry birds и тоже захотела сыграть в такую игру. Она взяла кур, свиней и решила стрелять курами в свиней из рогатки. Марфа Геннадьевна задумалась: может, не стоит мучить бедных животных и сделать то же самое не с животными, а с математической моделью?

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

Тело имеет массу m кг, начальная скорость равна v0 м/с и направлена под углом α градусов к горизонту. Ускорение свободного падения принять равным g = 9.8 м/с2. Сила сопротивления воздуха равна .

Требуется определить время и дальность полёта курицы.

Формат входного файла

Входной файл содержит вещественные числа m v0α k.

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

Требуется вывести в выходной файл вещественные числа T L — время и дальность полёта соответственно с как минимум 2-мя точными знаками после запятой.

Ограничения

0.1 ≤ m ≤ 10

0.1 ≤ v0 ≤ 20

1 ≤ α ≤ 90

0 ≤ k ≤ 10

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 10 45 0
1.443 10.204
2
1 10 45 1
1.206 4.955

Задача P. Косточки для собак

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Сколько существует способов распределить косточки между собаками, чтобы каждая собака получила хотя бы одну кость?

Например, если собак 2, а косточек 4, то существует 2 способа: либо младшей 1 кость, а старшей 3, либо младшей и старшей по 2 кости.

Формат входного файла

Входной файл содержит целые числа N M.

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

Требуется вывести в выходной файл единственное целое число — искомое число способов.

Ограничения

1 ≤ N ≤ M ≤ 50.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 4
2
2
3 6
3

Задача Q. Барабанная почта

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Когда-то давно члены одного африканского племени, жившие в разных деревнях, использовали для передачи информации звуковую почту. Чтобы передать сообщение, отправитель бил в барабан в промежутки времени ai ≤ t ≤ bi, а получатель слушал и рассказывал жителям своей деревни. Сила звука зависит от погоды — например, во время дождя и грозы звук барабана практически не слышен.

Однажды у племени поменялся вождь, и необходимо было оповестить об этом всех жителей племени. Но, как назло, погода в этот день была очень неустойчивая — то дождь, то туман, то ветер, то солнце. Поэтому звуки барабана можно было слышать только в промежутки времени ci ≤ t ≤ di.

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

Формат входного файла

Входной файл содержит целое число N — количество промежутков [ai, bi]. Далее следуют N пар целых чисел ai bi. Далее во входном файле содержится целое число M — количество промежутков [ci, di], — за которым следуют M пар целых чисел ci di.

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

Выходной файл должен содержать целое число K — количество промежутков [ei, fi] — и K пар целых чисел ei fi.

Должны выполняться неравенства: fi < ei + 1, i = 1, …, K − 1.

Промежутки нулевой длины выводить не нужно.

Ограничения

1 ≤ N, M ≤ 1000, 0 ≤ ai < bi ≤ 10000, 0 ≤ ci < di ≤ 10000

bi < ai + 1, i = 1, …, N − 1

di < ci + 1, i = 1, …, M − 1

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3
0 3
5 9
12 14
3
1 4
5 11
13 15
3
1 3
5 9
13 14
2
2
0 4
7 10
2
5 7
10 13
0

Задача R. Сколько лепестков?

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Здесь можно узнать, любит ли тебя он/она. Введи ваши дни рождения, скрипт нарисует цветок, и тебе только останется сосчитать лепестки.

Примечание. Вопросы по всем задачам турнира вы можете задавать здесь.

Формат входного файла

Входной файл содержит 4 целых числа: день и месяц (М) и день и месяц (Ж).

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

Выходной файл должен содержать единственное целое число — количество лепестков.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  15 5
7

Задача S. Числовые ребусы

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Ребус выглядит следующим образом. В нём записаны два слагаемых и результат их сложения, при этом некоторые цифры заменены на буквы. Требуется заменить буквы на цифры так, чтобы одинаковым буквам соответствовали одинаковые цифры, а разным буквам — разные цифры.

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

Во 2-м примере должно быть написано 2014 + ГОД = СОЧИ, но из-за того, что русские буквы в примерах не отображаются, они были заменены на другие буквы.

Формат входного файла

Входной файл содержит 3 строки, представляющие собой числа, в которых некоторые цифры заменены на не цифровые символы с ASCII-кодом больше 32.

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

Выходной файл должен содержать все возможные ответы на ребус в произвольном порядке, по одному в каждых 3-х строках, ответы нужно разделять пустыми строками.

Выводить следует те ответы, в которых нет незначащих нулей в начале чисел.

Ограничения

Количество символов в каждом числе во входном файле не превосходит 9.

Общее количество не цифровых символов во всех числах находится в пределах от 1 до 6.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
drama
drama
teatr
18969
18969
37938
2
2014
AOB
CODE
2014
789
2803

2014
891
2905

2014
893
2907

2014
896
2910
3
OXOXO
AXAXA
AXAXAX
90909
10101
101010
4
2A14
AAB
AODE
2214
221
2435

2214
225
2439

Задача T. Робот, налево!

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В Центре робототехники изобрели робота, который ходит только налево. На вопрос "зачем?" он затрудняется ответить.

Робот занимает одну клеточку и действует по следующему алгоритму.

  1. Развернуться влево.
  2. Если следующая клеточка не была посещена ранее, то пойти прямо (1). Иначе развернуться вправо и пойти прямо (2).

За шаг вида (1) робот получает 1 очко, за шаг вида (2) — 0 очков. Сколько очков получит робот, сделав N шагов?

Формат входного файла

Входной файл содержит целое число N.

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

Выходной файл должен содержать число очков.

Ограничения

1 ≤ N ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
1
2
3
3
3
15
7

Задача U. Новогодний код

Автор:Дед Мороз   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Деду Морозу из Нью-Васюков пишут не стихи, а проги. Дед Мороз любит, когда код программы похож на его бороду, то есть длины строк кода {ai}Ni = 1 удовлетворяют условию

a1 < a2 > a3 < a4 > …    ∧   a1 > a2 < a3 > a4 < ….

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

Напишите программу, которая по указанным длинам строк кода ai определяет новый набор длин bi, в котором:

  1. ai ≤ bi,
  2. либо b1 < b2 > b3 < b4 > …, либо b1 > b2 < b3 > b4 < …
  3. сумма bi минимальна.

Формат входного файла

Входной файл содержит целое число N за которым следует N чисел ai — длины строк.

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

Входной файл должен содержать N целых чисел bi — новые длины строк. Если существует несколько решений, выведите любое из них.

Ограничения

1 ≤ N ≤ 100; 1 ≤ ai ≤ 100

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
1
20
20
2
4
11 10 11 15
11 12 11 15

Задача V. Бутылка на всех

Автор:А. Шавлюгин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

Формат входного файла

Входной файл содержит целые числа N M, за которыми следуют N чисел ai — жажда i-го ученика.

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

Выходной файл должен содержать одно число —– минимально возможную суммарную жажду.

Ограничения

1 ≤ N, M ≤ 105

0 ≤ ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
9 30
0
2
4 3
0 101 5 12
7

Задача W. Посейдон

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

На этапе автоматизации технического обслуживания прачечной создатели сервиса управления расписанием стирки "Посейдон" (poseidon.dvfu.ru) столкнулись с алгоритмической проблемой.

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

Сервис "Посейдон+" (для персонала) должен вывести алгоритм перемещения поломанной машинки в заданное место с координатами (N, M), на котором машинка не стоит.

Задача разработчиков системы "Посейдон+" — реализовать алгоритм, который найдет оптимальный способ такого перемещения. "Оптимальный" — значит за минимальное число элементарных операций. Элементарная операция — это перемещение любой стиральной машины на свободное место, соседнее с ней по горизонтали или вертикали.

Формат входного файла

N, M ∈ N.

Способ представления стандартный.

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

x ∈ N0 — решение задачи оптимизации — минимальное количество перемещений (указания персоналу выводить не нужно).

Способ представления стандартный.

Ограничения

2 ≤ N, M ≤ 106

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2
5
2
5 3
23
3
3 7
35

Задача X. Годы летят

Автор:Г. Гренкин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В пожилом возрасте Марфа Геннадьевна совершила прыжок с парашютом. Как говорится, годы летят...

Когда Марфа Геннадьевна уже приземлилась, она как опытный физик и математик решила вычислить, сколько времени она летела до раскрытия парашюта. Для простоты Марфа Геннадьевна приняла силу сопротивления воздуха пропорциональной скорости: . После несложных вычислений Марфа Геннадьевна получила формулу, выражающую зависимость высоты от времени:

Здесь , где e = 2.71828... — постоянная Эйлера, H — начальная высота, g = 9.8 м/с2 — ускорение свободного падения, m — масса Марфы Геннадьевны. Марфа Геннадьевна пренебрегла начальной горизонтальной скоростью за счет движения самолета и приняла начальную вертикальную скорость равной 0.

Требуется определить, через какое время Марфа Геннадьевна достигла высоты h * , на которой она раскрыла парашют.

Формат входного файла

Входной файл содержит вещественные числа H h *  m k.

H и h *  заданы в км, m в кг, k в кг/с.

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

Требуется вывести в выходной файл единственное вещественное число — время до раскрытия парашюта в секундах по меньшей мере с 3-мя точными знаками после запятой.

Ограничения

2 ≤ H ≤ 100, 1 ≤ h * ≤ H.

50 ≤ m ≤ 150.

0.1 ≤ k ≤ 10.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1.5 85 1
18.1178
2
20 12 92 0.5
41.9407

4.332s 0.026s 97