Задача A1. Конфеты с десятичной точкой

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

Условие

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

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

Кроме того, для подбора размера ценника необходимо определить количество значащих цифр после десятичной точки.

Требуется написать программу, которая, получив на вход количество конфет контрольной партии B и цену партии A, рассчитает минимально возможное количество конфет в коробке C и соответствующее число цифр D.

Например если оказалось, что стоимость 6-ти конфет составляет 27 рублей, то их нужно выпускать в коробках по 1-ой конфете стоимостью 4.5 рубля — значит D = 1. Или если оказалось, что 760 конфет стоят 15 рублей, то их можно выпускать по 19 штук в коробке стоимостью 0.375 рублей — значит D = 3.

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

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

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

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

Ограничения

1 ≤ A, B ≤ 231 − 1

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

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

Задача A2. Absolutely simple

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

Условие

Вася любит уменьшать числа, но не любит отрицательных чисел. Поэтому он выбирает какое-нибудь число A1 и начинает уменьшать его на 100, а затем брать абсолютное значение результата. Иными словами, на каждом шаге он вычисляет следующее число в последовательности Ai + 1 = |Ai − 100|.

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

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

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

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

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

Ограничения

0 ≤ |A1| ≤ 109

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

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

Задача A3. K-удивительные числа

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

Условие

Переворотом числа X назовём число, в котором все цифры числа X стоят в обратном порядке. Например переворотом числа 2736 является число 6372, а числа 7800 — 87.

Назовём K-удивительным такое число, которое в сумме со своим переворотом даёт число K. Например у числа 222 имеется всего два K-удивительных числа: 111, 210, а у числа 1050 имеется девять K-удивительных чисел: 129, 228, 327, 426, 525, 624, 723, 822, 921.

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

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

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

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

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

Ограничения

1 ≤ K ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
222
2
2
1050
9
3
13
0

Задача A4. Breaking digits

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

Условие

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

  1. Каждая цифра числа A встречалась ровно один раз либо в B, любо в C.
  2. Сумма B + C была максимально возможной.

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

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

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

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

Ограничения

10 ≤ A ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
11
1
1
2
439
94
3
3
1000
100
0

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

Автор:Г. Гренкин   Ограничение времени: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

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

Автор:Г. Гренкин   Ограничение времени: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

Задача A7. Строки в книге

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:a.in   Ограничение памяти:64 Мб
Выходной файл:a.out  

Условие

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй - с (K + 1)-й по (2 × K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

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

Входной файл содержит число K — количество строк, которое печатается на странице, и число N — номер строки

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

В выходной файл выведите два числа — номер страницы, на которой будет напечатана эта строка и номер строки на странице

Ограничения

1 ≤ K ≤ 200, 1 ≤ N ≤ 20000

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

Входной файл (a.in) Выходной файл (a.out)
1
50 1
1 1
2
20 25
2 5
3
15 43
3 13

Задача A8. Поиск наибольшего числа

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

Условие

Вводится массив, состоящий из целых чисел. Найти наибольшее среди них

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

Сначала задано число N — количество элементов в массиве (1 ≤ N ≤ 35). Далее через пробел записаны N чисел — элементы массива. Массив состоит из целых чисел в диапазоне от  − 231 до 231 − 1.

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

Необходимо вывести значение наибольшего элемента в массиве.

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

Стандартный вход Стандартный выход
1
3
1 2 3
3

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

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 15

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

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

Задача B1. Настройка гитары

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

Условие

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

Первая струна настраивается по камертону. Каждая следующая струна настраивается по предыдущей, а именно:

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

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

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

i-ый символ входной строки показывает как звучит (i + 1)-ая струна относительно i-ой, а именно:

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

В выходном файле должна содержаться строка из 5 символов, описывающая действия, которые требуется произвести для настройки гитары. В i-ой позиции строке должен содержаться символ, описывающий действие над (i + 1)-ой струной:

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

Входной файл (input.txt) Выходной файл (output.txt)
1
=====
*****
2
=<=<=
*++++
3
>==<=
---??

Задача B2. Точка в углу

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

Условие

Прямоугольник со сторонами, параллельными осям координат, задан координатами противоположных вершин (x1, y1) и (x2, y2).

Будем считать, что точка (x, y) внутри прямоугольника находится в углу, если расстояние от точки до одной из вершин прямоугольника строго меньше, чем до центра прямоугольника.

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

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

Входной файл содержит целые числа x1 y1 x2 y2 x y — координаты вершин прямоугольника и точки.

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

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

Ограничения

 − 104 ≤ x1,y1,x2,y2 ≤ 104

min(x1, x2) ≤ x ≤ max(x1, x2)

min(y1, y2) ≤ y ≤ max(y1, y2)

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 200 300 400 290 210
CORNER
2
100 200 300 400 200 300
CENTER

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

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

Условие

Дана последовательность целых чисел A1, …, AN. Вычислить их сумму.

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

Во входном файле содержится число N, за которым следуют числа A1… AN.

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

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

Ограничения

0 ≤ Ai ≤ 10000, 1 ≤ N ≤ 1000.

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

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

Задача B4. ASCII в кубе

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

Условие

По данным целым числам W, H, D, W1, H1, D1 вывести ASCII-изображение параллелепипеда шириной W, высотой H и глубиной D, из которого удалён параллелепипед шириной W1, высотой H1 и глубиной D1. Удаление производится из угла, ближайшего к наблюдателю (ближний правый верхний угол). Параллелепипед состоит из кубиков размером 1x1x1. Каждый кубик выглядит так:

  +---+
 /   /|      
+---+ |      
|   | + 
|   |/ 
+---+
(используются символы '+', '-', '/', '|', соответственно ASCII 43, 45, 47, 124)

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

Входной файл содержит числа W H D W1 H1 D1

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

Выходной файл должен содержать ровно 3H + 2D + 1 строку, представляющую ASCII-изображение разности параллелепипедов. В начале первых 2D строк вместо пробелов должны стоять символы "точка" (ASCII 46).

Ограничения

1 &le; W, H, D &le; 40, 0 &le; W1 < W, 0 &le; H1 < H, 0 &le; D1 < D.

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

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

 ......+---+---+---+
 ...../   /   /   /|
 ....+---+---+---+ |
 .../   /|   |   | +
 ..+---+ |   |   |/|
 ./   /| +---+---+ |
 +---+ |/   /   /| +
 |   | +---+---+ |/|
 |   |/   /   /| + |
 +---+---+---+ |/| +
 |   |   |   | + |/ 
 |   |   |   |/| +  
 +---+---+---+ |/ 
 |   |   |   | +  
 |   |   |   |/
 +---+---+---+
  

Задача B5. Двоичный порядок float

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:2 Мб

Условие

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

Для поиска порядка необходимо использовать битовые операции.

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

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

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

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

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

Стандартный вход Стандартный выход
1
2.0
1
2
0.5
-1

Задача B6. K-й бит в числе

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

Условие

Дано целое неотрицательное число x, требуется вернуть значение k-го бита числа x, то есть k-й разряд двоичного представления числа x. Разряды нумеруются с 0 начиная с младшего. Считается что число содержит неограниченное количество лидирующих нулей.

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

Первая строка входного файла содержит два числа x, k.

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

Входной файл должен содержать одно число  — значение k-го бита числа x.

Ограничения

0 ≤ x ≤ 2 ⋅ 109

0 ≤ k ≤ 300

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

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

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

Автор:Г. Гренкин   Ограничение времени: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

Задача C2. Забор по фен-шую

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

Условие

Марфа Геннадьевна попросила внука построить новый забор вдоль огорода. Внук выполнил просьбу бабушки и построил забор из N досок, в котором доска с номером i имела высоту ai сантиметров.

Марфа Геннадьевна недавно прочитала книгу, в которой было написано, что гармоничным является забор, состоящий из чередующихся высоких и низких деревянных досок, то есть должно выполняться либо условие 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

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

Автор:Г. Гренкин   Ограничение времени: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

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

Автор:Г. Гренкин   Ограничение времени: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

Задача C5. Новые чемоданы

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

Условие

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 105, 1 ≤ K ≤ 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 5
YES
1 3
2
842 1
NO
3
98 2
YES
7 7

Задача D1. Поворот отрезка

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

Условие

Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).

Требуется найти координаты вершин отрезка A *  B *  (X * a; Y * a) и (X * b; Y * b), полученного путём поворота отрезка AB вокруг точки O (Xo; Yo) на β градусов.

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

Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β

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

Выходной файл должен содержать четыре вещественных числа X * a, Y * a, X * b, Y * b с точностью 10 − 3.

Ограничения

0 ≤ |Xa|, |Ya|, |Xb|, |Yb|, |Xo|, |Yo| ≤ 105

0 ≤ β ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  2 2  0 0  90
-1.000000000 1.000000000 -2.000000000 2.000000000
2
1 1  2 2
0 0
45
0.000000000 1.414213562 0.000000000 2.828427125
3
7 5
11 11
9 8
180
11.000000000 11.000000000 7.000000000 5.000000000

Задача D2. Булева функция

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:function.in   Ограничение памяти:64 Мб
Выходной файл:function.out  

Условие

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция f сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции f.

Если задана булева функция f и набор из N булевых значений a1, a2, …, aN, то результат цепного вычисления этой булевой функции определяется следующим образом:

Например, если изначально задано три булевых значения: a1 = 0, a2 = 1, a3 = 0, а функция f — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть, 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

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

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

Пояснения к примерам

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

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

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

Первая строка входного файла содержит одно натуральное число N

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

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

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

Ограничения

2 ≤ N ≤ 105

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

Входной файл (function.in) Выходной файл (function.out)
1
4
0110
1011
2
5
0100
11111
3
6
0000
No solution

Задача D3. НОД и НОК

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

Условие

Необходимо вычислить НОД и НОК для пары целых положительных чисел a и b.

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

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

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

Выходной файл должен содержать НОД и НОК пары чисел.

Ограничения

1 ≤ a,b ≤ 106

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

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

Problem E1. Ascending arrays

Input file:Standard input   Time limit:1 sec
Output file:Standard output   Memory limit:256 Mb

Statement

There are three strictly increasing arrays of integers A1, A2, A3 with lengths N1, N2, N3.

Your program must find the count of triples of the same numbers simultaneously occurring in each of these arrays.

Input format

First line contains N1, N2, N3.

Second line contains A11, A12, ..., A1N1

Third line contains A21, A22, ..., A2N2

Fourth line contains A31, A32, ..., A3N3

Output format

A single integer — count of triplets.

Constraints

1 ≤ N1, N2, N3 ≤ 105

0 ≤ Ai j ≤ 109

Sample tests

No. Standard input Standard output
1
5 4 3
2 3 4 5 7
1 2 3 4
2 3 4
3
2
5 4 3
2 3 4 5 7
1 2 4 7
1 3 5
0

Задача E2. Построение солдат - 1

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

Условие

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

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

Первая строка содержит число солдат N. В последующих строках содержатся N описаний каждого солдата: рост Ri и имя Si.

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

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

Ограничения

1 ≤ N ≤ 100000 0 ≤ Ri ≤ 1000000 (действительное число)
Длина имени солдата не превосходит 255 символов.

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

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

3
1.70 name1
1.75 name2
1.70 name3
    

name2
name1
name3
    

Задача E3. Спираль

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

Условие

Квадратная матрица размера n × n заполнена целыми числами от 1 до n2 следующим образом.

Например, при n = 2 и n = 3 матрица принимает вид:

4 3        9 8 7
1 2        2 1 6
           3 4 5

Требуется по данному размеру матрицы n и номеру r вывести r-ю строку матрицы.

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

Входной файл содержит натуральные числа n r.

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

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

Ограничения

1 ≤ r ≤ n ≤ 105

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

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

Задача E4. Гражданская оборона

Автор:Восьмая всероссийская командная олимпиада школьников по программированию   Ограничение времени:2 сек
Входной файл:shelter.in   Ограничение памяти:256 Мб
Выходной файл:shelter.out  

Условие

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

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

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

Первая строка входного файла содержит число n — количество селений. Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения.

Третья строка входного файла содержит число m — количество бомбоубежищ. Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища.

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

Выведите в выходной файл n чисел — для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n, m ≤ 100000

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

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

Входной файл (shelter.in) Выходной файл (shelter.out)
1
4
1 2 6 10
2
7 3
2 2 1 1

Задача G1. Максимум в скользящем окне

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

Условие

Пусть задан массив из n целых чисел. По этому массиву будут ходить два указателя l и r. Изначально оба они указывают на первый элемент массива. Оба указателя могут двигаться только вправо, на одну позицию за раз. При этом указатель l никогда не оказывается правее указателя r, и ни один из них не выходит за пределы массива. Вам нужно после каждого перемещения указателя определить максимум всех элементов от указателя l вправо до указателя r (включая позиции, на которые указывают l и r).

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

Первая строка входного файла содержит целое число n - размер массива. Во второй строке содержится строке n целых чисел ai - сам массив.

В третьей строке указано число m — количество перемещений. В четвертой строке — m символов 'L' или 'R', разделенных пробелами. 'L' означает, что нужно сдвинуть l вправо, 'R' — что нужно сдвинуть r вправо.

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

В выходной файл выведите в одну строку ровно m чисел, где i-е число — максимальное значение на отрезке от l до r после выполнения i-й операции.

Ограничения

1 ≤ n ≤ 105

|ai| ≤ 109

0 ≤ m ≤ 2n − 2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4
-3 -2 -1 0
6
RRRLLL
-2 -1 0 0 0 0
2
10
1 4 2 3 5 8 6 7 9 10
12
RRLRRRLLLRLL
4 4 4 4 5 8 8 8 8 8 8 6

Задача P1. Мёд и справедливость

Автор:Кленин А. С.   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит ai микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

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

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

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

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

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ ai ≤ 105

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

Стандартный вход Стандартный выход
1
3
1 1 2
1 2 3
2
2
2 5
-1

Задача P2. Гипершашки

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:1 сек
Входной файл:game.in   Ограничение памяти:256 Мб
Выходной файл:game.out  

Условие

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал A баллов, второй — B, а третий C, то говорят, что игра закончилась со счетом A:B:C.

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

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из N карточек, на которых написаны числа x1, x2, …, xN. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

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

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

Первая строка входного файла содержит два целых числа: N и K. Вторая строка входного файла содержит N целых чисел x1, x2, …, xN.

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

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

Ограничения

3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109

Пояснение к примеру

В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в k = 2 раза.

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только каких-либо из подзадач 1 и 3.

Подзадача 1 (15 баллов)

3 ≤ N ≤ 100 000; K = 1; 1 ≤ xi ≤ 100 000

Подзадача 2 (23 балла)

3 ≤ N ≤ 100; 1 ≤ K ≤ 100; 1 ≤ xi ≤ 100

Подзадача 3 (30 баллов)

3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109; все xi различны

Подзадача 4 (32 балла)

3 ≤ N ≤ 100 000; 1 ≤ K ≤ 109; 1 ≤ xi ≤ 109

Получение информации о результатах окончательной проверки

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

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

Входной файл (game.in) Выходной файл (game.out)
1
5 2
1 1 2 2 3
9

Задача P3. Чемпионат по боксу

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

Условие

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

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

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

Первая строка входного файла содержит два целых числа N, M. Далее N пар чисел pi, сi  — описание боксёров из команды Пахома. Далее N пар чисел pi, сi  — описание команды соперников.

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ M ≤ 300, 1 ≤ сi ≤ M; 1 ≤ pi ≤ 109.

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения
NM
1201 ≤ N ≤ 201 ≤ M ≤ 2
2201 ≤ N ≤ 10001 ≤ M ≤ 2
3201 ≤ N ≤ 1061 ≤ M ≤ 2
4201 ≤ N ≤ 1061 ≤ M ≤ 50
5201 ≤ N ≤ 1061 ≤ M ≤ 300

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
1 1
2 1 
3 1
4 1
5 1
6 1
-9
2
4 2
60 1
100 2
110 2
120 2
200 1
50 2
40 2
30 2
12
3
3 3
5 1
10 2
15 3
6 1
11 2
16 3
-1

Задача R1. Домой на электричках

Автор:X командный чемпионат Санкт-Петербурга по программированию - V Открытая Кировская командная олимпиада   Ограничение времени:2 сек
Входной файл:a.in   Ограничение памяти:8 Мб
Выходной файл:a.out  

Условие

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

Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.

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

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

Во входном файле записаны сначала числа N и E. Затем записано число M, обозначающее число рейсов электричек. Далее идет описание M рейсов электрички. Описание каждого рейса электрички начинается с числа Ki — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.

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

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

Ограничения

2 ≤ E ≤ N ≤ 1000, 1 ≤ M ≤ 100, 2 ≤ Ki ≤ N.

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

Входной файл (a.in) Выходной файл (a.out)
1
5 3
4
2 1 5 2 10
2 2 10 4 15
4 5 0 4 17 3 20 2 35
3 1 2 3 40 4 45
20

Задача R2. 0 - a, 1 - ab

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

Условие

Дана строка s, состоящая из N символов 0 или 1, а также строка t, состоящая из M символов a или b,

Над строкой s разрешено производить следующие действия:

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

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

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

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

Третья строка входного файла содержит строку t.

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

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

Ограничения

1 ≤ N, M ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3
101
bab
Y
2
4 3
1001
bab
N

Задача R3. Почтовый индекс

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

Условие

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

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

Линии, образующие стороны квадрата, Тимофей называет прямыми, а диагонали квадрата - наклонными. Например, в цифре 9 четыре прямых и одна наклонная линия.

Сегодня Тимофей должен написать письмо-приглашение своему другу, с которым он познакомился в международном лагере юных программистов, да вот беда - Тимофей совсем забыл его почтовый индекс. Все, что он помнит, так это количество прямых и наклонных линий в его индексе, и то, что он является наименьшим натуральным числом из всех подходящих. Помогите Тимофею! Учтите, что длина индекса в других странах может быть произвольной (а не 6, как в России), а также то, что никакой индекс не может начинаться с нуля.

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

В единственной строке через пробел записаны два неотрицательных целых числа a и b — количества прямых и наклонных линий в индексе.

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

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

Ограничения

0 ≤ a ≤ 103

0 ≤ b ≤ 102

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

Стандартный вход Стандартный выход
1
10 1
28
2
5 4
Wrong
3
23 5
100236

2.029s 0.012s 83