Задача 2. НОД и числа Фибоначчи ≡

Условие

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

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

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

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

Ограничения

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

1 2

1

Задача 3. Забор в парке ≡

Условие

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

Программа должна, получив на входе число вершин многоугольника N и их целочисленные координаты (x₁, y₁), …, (x_N, y_N), определить количество точек с целочисленными координатами, лежащих на границе этого многоугольника.

Стороны многоугольника не самопересекаются.

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

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

Ограничения

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

3
0 0 2 0 0 2

6

Problem 4. Bucket sort (исправленная) ≡

Statement

Input file format

Output file format

Constraints

Sample tests

4
KVN
ACM
FSB
GGG

ACM
FSB
GGG
KVN

Задача 5. Количество инверсий последовательнсти ≡

Условие

Пара элементов (A_i, A_j) последовательности A_N называется инверсией, если A_i > A_j и i < j.

Напишите программу, которая по заданной последовательности A_N посчитает количество инверсий.

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

В первой строке входного файла содержится число N — количество элементов последовательности

Последующие N целых чисел задают саму последовательность

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

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

Ограничения

2 ≤ N ≤ 10⁵

0 ≤ A_i ≤ 10⁹

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

7 1 2 5 9 13 16 20

0

9
1 1 2 3 8 6 1 9 9

5

Задача 6. В лесу родилась ёлочка ≡

Условие

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

Хорошие, толстые, густые ёлки стоят на рынке 5000 руб., а ёлки похуже, тонкие, менее густые стоят 2000 руб.

На всё про всё у ребят есть ровно T минут. Хорошие ёлки растут подальше, и рубить их дольше. Ёлки похуже растут поближе, и рубить их быстрее. На то, чтобы дойти до i-й ёлки, срубить её и вернуться домой, нужно затратить t_i минут.

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

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

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

Далее следует число M — количество ёлок похуже. За ним следуют M целых чисел t_i.

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

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

Ограничения

1 ≤ N, M ≤ 1000

1 ≤ T ≤ 10000

1 ≤ t_i ≤ 10000

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

250
1
240
2
120 100

5000

250
1
240
3
60 80 70

6000

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

Условие

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

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

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

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

Ограничения

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

1 2

1

6 9

2

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

Условие

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

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

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

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

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

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

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

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

Ограничения

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

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

12 0

12 0

23 59

0 1

22 25

1 35

Задача B. Сложение массива чисел ≡

Условие

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

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

Ограничения

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

3
1 2 3

6

Задача C. Массив наоборот ≡

Условие

Во входном файле дан массив целых чисел a₁, a₂, ..., a_N. Требуется вывести этот массив в обратном порядке.

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

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

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

Выходной файл должен содержать N чисел — массив a_i, записанный в обратном порядке.

Ограничения

1 ≤ N ≤ 100000

 − 10⁹ ≤ a_i ≤ 10⁹

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

4
1 2 3 4

4 3 2 1

6
9 1 3 -2 3 5

5 3 -2 3 1 9

Задача D. Количество каждой цифры ≡

Условие

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

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

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

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

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

Выходной файл должен содержать 10 чисел — количество цифр 1, количество цифр 2, и т.д., количество цифр 9, количество цифр 0.

Ограничения

1 ≤ N ≤ 1000000

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

4
1 2 1 0

2 1 0 0 0 0 0 0 0 1

7
9 1 3 2 3 2 7

1 2 2 0 0 0 1 0 1 0

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

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

4
1 2 1 0

0 1
1 2
2 1

7
9 1 3 2 3 -2 7

-2 1
1 1
2 1
3 2
7 1
9 1

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

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

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

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

6 14 12

Задача G. Инкубатор Бабы Яги ≡

Условие

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

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

Сотрудники института собрали статистические данные. В течение нескольких дней они записывали количество ног у появившейся курицы.

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1000

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

12
3 1 1 1 2 1 3 2 2 5 6 2

1 3 6 0 0 0

10
3 6 3 6 2 3 2 6 3 2

0 2 3 0 0 4

Задача H. Системы счисления ≡

Условие

Дано число в системе счисления по основанию P. Требуется перевести его в систему счисления по основанию Q.

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

Первая строка входного файла содержит целые числа P и Q. Следующая строка содержит строку, представляющую собой запись числа в системе счисления по основанию P. Для записи числа используются цифры 0, 1, ..., 9, а также заглавные латинские буквы A, B, C, ..., X, Y, Z.

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

Выходной файл должен содержать представление того же числа в системе счисления по основанию Q. Формат тот же, что во входном файле.

Ограничения

2 ≤ P, Q ≤ 36

Число находится в пределах от 0 до 10⁹.

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

10 2
5

101

16 10
FF

255

2 3
110

20

36 10
1Z

71

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100

1 ≤ a₁ < a₂ < …  < a_N ≤ 1000

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

3
1 7 8

GOOD

5
1 7 9 12 17

BAD

Задача J. Золотые яйца ≡

Условие

В некотором царстве, некотором государстве жила-была Марфа Геннадьевна. И была у Марфы Геннадьевны курочка, которая, кроме обычных яиц, иногда несла золотые яйца.

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

У Марфы Геннадьевны есть волшебный компьютер, который может выполнить любую программу. Чего нет у Марфы Геннадьевны — так это волшебного программиста, который мог бы написать любую программу.

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

В государстве, в котором живёт Марфа Геннадьевна, для летоисчисления используются 12 месяцев, в каждом месяце ровно 30 дней. Полнолуние происходит каждые 29 дней: 1 января, 30 января, 29 февраля и т.д.

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

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

Далее следуют даты появления золотых яиц — пары целых чисел: день и месяц.

Во входном файле не может быть двух одинаковых дат.

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

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

Ограничения

1 ≤ N ≤ 100

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

3
2 1
1 1
29 2

2

2
28 3
29 3

1

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

Условие

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

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

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

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

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

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

Ограничения

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

2

1 2
2 1
2 1
1 2

Задача L. Вынутый разворот ≡

Условие

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

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

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

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

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

• 0 — если такой брошюры не существует
• Число страниц в брошюры — в противном случае

Ограничения

1 ≤ A, B ≤ 10⁶

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

3 14

16

9 1

0

Задача M. Короткий текст и немного слов ≡

Условие

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

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

Ограничения

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

Longlongstring
2
short
string

0 1

Задача N. Три буквы ≡

Условие

Дана текстовая строка, состоящая из заглавных латинских букв. Требуется найти подстроку из трёх букв, которая встречается в данной строке чаще всего. Например, в строке DEFDEFABCABCZABCDEFDEF чаще всего (4 раза) встречается подстрока DEF.

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

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

Ограничения

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

DEFDEFABCABCZABCDEFDEF

4

Задача O. Дифтонги ≡

Условие

Слова марсианского языка состоят из малых латинских букв. Буквы a, e, i, o, u, y считаются гласными, остальные — согласными.

Дифтонгом называется пара подряд идущих гласных букв, окружённых либо согласными буквами, либо границами слова. Например, в слове preemptio имеется два дифтонга, а в слове aaa — ни одного.

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

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

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

Ограничения

1 ≤ N ≤ 100

Слова содержат от 1 до 255 символов.

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

3
e
ee
eee

ee

3
aabbee
cyydyyy
xiixiixiii

aabbee
xiixiixiii

Задача P. Подсчёт слов ≡

Условие

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

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

Ограничения

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

This       is  a  test	

4

Qqqqqqqqqq

1

Задача Q. Определить век по году ≡

Условие

Когда Андрей учился в начальной школе, его учили определять, к какому веку относится заданный год. Теперь Андрей хорошо знает, что, например, 2001 год относится к XXI веку, а 2000 год — к XX веку.

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

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

Поэтому Андрей очень просит участников Весеннего турнира-2013 написать компьютерную программу, принимающую на вход номер года в десятичной системе счисления и выводящую номер века, к которому относится этот год, в римской системе счисления.

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

Входной файл содержит целое число Y — номер года.

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

Требуется вывести в выходной файл номер века, к которому относится год Y, в римской системе счисления, используя заглавные буквы латинского алфавита I, V, X.

Ограничения

1 ≤ Y ≤ 3000.

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

2001

XXI

2000

XX

658

VII

2703

XXVIII

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

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

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

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

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

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

frog
or

.ro.

frog
oro

.r..

frog
fffrrroooog

fr.g

frog
golf

f.og

frog
gorf

frog

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N, M ≤ 1000, 0 ≤ a_i < b_i ≤ 10000, 0 ≤ c_i < d_i ≤ 10000

b_i < a_i + 1, i = 1, …, N − 1

d_i < c_i + 1, i = 1, …, M − 1

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

3
0 3
5 9
12 14
3
1 4
5 11
13 15

3
1 3
5 9
13 14

2
0 4
7 10
2
5 7
10 13

0

Problem T. Square sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Problem U. Lin-log sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 4 3 10 3 1

1 3 3 4 10

Problem V. Bucket sort ≡

Statement

Input file format

Output file format

Constraints

Sample tests

4
KVN
ACM
FSB
GGG

ACM
FSB
GGG
KVN

Задача W. Сортировка подсчетом ≡

Условие

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

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

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

Ограничения

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

4
2 1
3 2 
2 3
3 4

1 3 2 4

Задача X. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

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

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

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

Входной файл содержит три целых числа: W, H, N

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

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

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

2 3 10

9

Задача Y. Возведение в степень ≡

Условие

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

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

Ограничения

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

3 5

243

10 20

100000000000000000000