Берляндское многоборье

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Скоро в Берляндии пройдут спортивные соревнования по многоборью. Правила этих состязаний таковы. Сначала участники проплывают некоторое расстояние, затем их ждет K этапов скачек на лошадях. На старте каждого из этих этапов стоит N лошадей (по числу участников). Каждая лошадь имеет некоторую характеристику S_j (назовем ее скакучестью). Чем больше скакучесть, тем быстрее лошадь преодолевает дистанцию. Каждый участник характеризуется тремя параметрами: навык пловца W_i, навык наездника R_i и сила P_i. Тот участник, кто приходит на старт очередного этапа (являющийся одновременно финишем предыдущего) раньше, выбирает себе для прохождения следующего этапа лошадь с наибольшей скакучестью из тех, что по-прежнему находятся на старте. Каждая лошадь принимает участие ровно в одном этапе. Если два участника приходят одновременно, лучшая лошадь в итоге достается тому, чья сила больше (у всех спортсменов разная сила). Время преодоления этапа i -м участником на лошади номер j равно 2*10⁷- R_i - S_j, а вплавь равно 2*10⁷- W_i. После старта соревнования (начало заплыва) между этапами не возникает никаких пауз, лошадей участники берут или меняют мгновенно.
Каким-то непостижимым образом мальчику Пете стали известны все характеристики участников. К тому же он выяснил, что жюри подбирает лошадей таким образом, что на этапе i (1 ≤ i ≤ K) скакучесть j -й (1 ≤ j ≤ N) лошади вычисляется так:

f(i, j) = 3 * A[i]² + 5 * A[i] * B[j] + 2 * B[j]²,

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

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

В первой строке входного файла содержатся два натуральных числа N и K (1 ≤ N ≤ 10³; 1 ≤ K ≤ 10³). Далее следует N строк, каждая из которых содержит три натуральных числа - W_i, R_i, и P_i (1 ≤ W_i, R_i, P_i ≤ 10⁶). Затем идет строка, задающая массив A, состоящая из K натуральных чисел, не превосходящих 10³. Далее следует строка, задающая массив B в аналогичном формате. В массиве B находится N натуральных чисел, не превосходящих 10³.

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

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

Пример

Ввод

Пример 1
4 2
2 5 3
3 1 4
3 4 1
2 2 2
2 3
4 5 6 7

Вывод

Пример 1
2 3 1 4

Последовательность ЕКГ

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Известный любитель диковинных математических фактов Петя недавно узнал об одной интересной последовательности и сразу же углубился в ее изучение. Последовательность строится следующим образом: ее первый член A ₁ = 1, второй член A ₂ = 2, а в качестве каждого следующего члена A _i берется наименьшее натуральное число k, которое:

· еще не встречалось в последовательности;

· имеет общий делитель, отличный от 1, с A_{i -1}.

Следуя этому правилу, Петя установил, что первые 10 членов последовательности - это 1,2,4,6,3,9,12,8,10,5. Петя хочет узнать много больше членов последовательности, однако его желания никак не сопоставимы с его вычислительными возможностями. А вот с вашими - сопоставимы. Напишите программу, которая находит N -оe число в последовательности.

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

В первой строке входного файла записано натуральное число N (1 ≤ N ≤ 600000).

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

В первой строке выходного файла выведите N -й член последовательности. Гарантируется, что при данных ограничениях A_N не превосходит 1000000.

Пример

Ввод

Пример 1
7

Вывод

Пример 1
12

Индексы

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

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

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

В первой строке входного файла записано две различные цифры А и B (0 ≤ A, B ≤ 9).

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

Выведите "YES", если исправление возможно, или "NO" в противном случае. (Слова выводите заглавными буквами)

Пример

Ввод

Пример 1
1 2

Вывод

Пример 1
NO

Затмение

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

Известный астроном Петя заметил, что солнечное затмение в Берляндии происходит во все "неубывающие" года. Петя называет год "неубывающим", если цифры его номера идут в неубывающем порядке. Например, 1256 год является "неубывающим", и в этот год произошло солнечное затмение. А в 1354 году затмения не было. Петю заинтересовал вопрос, сколько солнечных затмений произошло с 1 по N -ый год.

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

В первой строке входного файла содержится одно натуральное число N (1 ≤ N ≤ 10⁷).

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

Выведите единственное число - количество солнечных затмений в заданный период.

Пример

Ввод

Пример 1
1

Пример 2
100

Пример 3
10000000

Вывод

Пример 1
1

Пример 2
54

Пример 3
11439

Рынок

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

В Берляндии наступило лето, и наконец-то в продаже появились знаменитые берляндские арбузы. В одно прекрасное утро на рынок пришли N продавцов и M покупателей. У каждого продавца был ровно один арбуз, и каждый покупатель тоже хотел купить ровно один арбуз. Каждый продавец объявил минимальную цену, по которой он согласен продать свой арбуз, а каждый покупатель назвал максимальную цену, по которой он согласен купить арбуз. Начался шум и галдеж. Чтобы исправить ситуацию, для назначения единой цены на арбузы был срочно вызван директор рынка Берлан Берладзе. В его интересах было назначить такую единую цену, чтобы суммарная стоимость всех проданных по этой цене арбузов была максимальной. Поскольку он не силен в математике, он попросил вас найти такую цену. Помогите ему.

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

В первой строке входного файла содержится одно натуральное число N (1 ≤ N ≤ 100000) - количество продавцов. Во второй строке содержатся N чисел - для каждого продавца минимальная допустимая цена на его арбуз. В третьей строке содержится число M (1 ≤ M ≤ 100000) - количество покупателей. В четвертой строке входного файла содержатся M чисел - для каждого покупателя максимальная цена, за которую он согласен купить арбуз. Все стоимости - натуральные числа, не превосходящие 10000.

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

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

Пример

Ввод

Пример 1
3
1 3 2
3
2 2 2

Вывод

Пример 2
2

Урок физкультуры

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 65536 KB.

ввод: input.txt
вывод: output.txt

 

В одной из берляндских школ случилось несчастье: преподаватель физкультуры подхватил простуду во время утренней зарядки. После некоторых обсуждений педсовет принял решение, что первый, и единственный, раз урок физкультуры будет проводить учитель математики Глеб Антонович, которому все равно, кому, где и когда рассказывать о математике.
Придя в спортзал, Глеб Антонович заметил, что пол покрыт единичными квадратами в виде шахматной доски размера N x M. Не особенно задумываясь о порядке упражнений, он предложил начать с разминки. Для этого нужно было выстроиться в несколько рядов, причем, так как Глеб Антонович любит во всем порядок, то каждый ученик должен стоять в центре какого-либо единичного квадрата (не более одного человека в квадрате). Ученикам не нравился дискомфорт, поэтому в любом квадрате 2x2 не должно было быть более двух человек. Но из-за ограниченности пространства в каждом квадрате 2x2 не могло стоять меньше двух ребят.
Вдруг Глеба Антоновича заинтересовало, сколько существует способов расставить учеников вышеуказанным образом, если ребят считать неразличимыми. Ваша задача посчитать это число способов.

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

В первой строке входного файла содержится два натуральных числа N и M (2 ≤ N, M ≤ 1000).

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

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

Пример

Ввод

Пример 1
2 2

Вывод

Пример 1
6

Директивы include

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

Многие языки содержат специальную директиву, которая вставляет содержимое одного файла внутрь другого. Часто такие директивы называются include. В этой задаче вам предстоит реализовать функциональность простейшего препроцессора, обрабатывающего эту инструкцию. Вам задан набор текстовых файлов. Строка файла вида "#include <имя-файла>" должна быть заменена на содержимое соответствующего файла (имя файла в директиве может быть как абсолютным так и относительным; относительный путь всегда начинается с имени файла или директории или спецпоследовательности ".."). В этой строке могут быть любые незначащие пробелы, не разрывающие элементы include и имя-файла. Если файла с именем имя-файла не существует, то эта строка должна быть просто вырезана из текста файла.

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

Входной файл состоит из последовательности описаний файлов. Каждое описание начинается со строки, содержащей путь до файла в формате файловых систем Windows. Путь задан абсолютно и не содержит пробелов и символов "\" идущих подряд. В качестве элемента пути может быть использована спецпоследовательность "..", которая обозначает переход в родительскую директорию. Другие спецпоследовательности не используются. Имя любой директории и файла состоит из латинских букв, цифр и символа ".". Сравнение имен файлов следует проводить без учета регистра. Далее идет содержимое файла. Последовательность вида "^Z" обозначает конец файла. Эта последовательность всегда записана на отдельной строке, то есть каждая строка файла, включая последнюю, завершается переводом строки. Входной файл содержит не менее одного описания. Размер файла не превосходит 40KB. Длина каждой строки файла не превосходит 1000 символов. Все имена файлов в тесте (включая те, что встречаются в директивах include) - это корректные абсолютные или относительные пути.

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

Выведите содержимое первого файла после обработки препроцессором. Гарантируется, что размер вывода не превзойдет 400KБ. Если обработка директив приводит к циклическому процессу - выведите строку "Too long file".

Пример(ы)

input.txt	output.txt
c:\files\first.txt #define MAX_N 1024 #include <second.txt> last line ^Z c:\FILES\..\files\second.txt included file #include <..\files\third.txt> ^Z c:\FILES\THIRD.txt included file ^Z	#define MAX_N 1024 included file included file last line

 

input.txt	output.txt
C:\files\first.txt #define MAX_N 1024 #include <second.txt> last line ^Z c:\FILES\second.txt included file #include <..\files\..\files\second.txt> ^Z c:\FILES\THIRD.txt included file ^Z	Too long file

 

input.txt	output.txt
c:\1\a.txt #include "begin of a" #include <c:\2\b.txt> #include end of a ^Z c:\2\..\2\b.txt begin of b #include <c.txt> end of b: #include <c.txt> ^Z C:\2\C.TXT oops ^Z	#include "begin of a" begin of b oops end of b: #include <c.txt> #include end of a

501. Простецкие числа

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

Число называется простецким, если его можно разбить на две части длиной не менее d цифр (каждая часть не может начинаться с 0) таких, что они обе являются простыми числами. Напомним, что простые числа - это такие натуральные числа, которые имеют ровно два различных делителя. Задана пара чисел d и n. Выведите наименьшее простецкое число не меньшее n.

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

Входной файл состоит из одного или более набора входных данных. Каждый набор записан в отдельной строке, содержащей пару натуральных чисел d и n, разделенных пробелом (1 ≤ d ≤ 5; 1 ≤ n ≤ 2*10⁹). Количество наборов входных данных в тесте не превосходит 5.

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

Для каждого набора выведите искомое число на отдельной строке. Гарантируется, что ответ для любого набора не превзойдет 2*10⁹.

Пример(ы)

input.txt	output.txt
1 20 1 22	22 22

 

input.txt	output.txt
2 1 2 1234	1111 1311

Уголки

ограничение времени на тест: 4 секунды
ограничение памяти на тест: 64 мегабайта

ввод: input.txt
вывод: output.txt

32 битный компилятор: [X]

 

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

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

Входной файл содержит одно или более изображение. В первой строке описания изображения записаны два натуральных числа n, m (1 ≤ n ≤ 50; 1 ≤ m ≤ 50). Далее содержится n строк, каждая по m символов. Символ '.' соответствует пикселю белого цвета, а символ '*' - черного. Количество изображений в файле не превосходит 50.

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

Для каждого изображения выведите количество уголков на картинке в отдельной строке.

Пример(ы)

input.txt	output.txt
9 14 .............. ........****.. .*.........*.. .*.........*.. .*.........*.. .****....***.. .....***....*. .....*........ .....*........ 8 8 *******. *......* *.****.* *.*....* *...*..* *...*..* *......* .*******	2 3