Короткая последовательность цифр

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

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

 

Дано целое положительное число N. В записи бесконечной последовательности групп цифр S1S2...Sk... найти цифру, находящуюся в позиции с номером N. Каждая группа вида Sk состоит из последовательности натуральных чисел от 1 до k, выписанных подряд.
Например, первые восемьдесят цифр последовательности имеют вид: 11212312341234512345612345671234567812345678912345678910123456789101112345678910

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

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

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

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

Пример

Ввод

20

Вывод

5

Черно-белый король

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

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

 

На шахматной доске NхN осталось три фигуры. Черный король, белый и черно-белый. Для нас черно-белый король непривычная фигура, так как он невидимый. Черный и белый король решили заключить договор и объединиться против черно-белого (они его не видят, но знают, что он где-то рядом, на доске). Для того, что бы реализовать задуманное им необходимо встретиться, что значит оказаться на соседних клетках (в общем случае у каждой клетки 8 соседей). Черно-белый король хочет им помешать. Для этого он должен перехватить одного из королей до того, как они встретятся, то есть атаковать его (пойти на клетку противника). Если противник сходит на клетку черно-белого короля ничего страшного не произойдет (никто никого не <убьет>). Ваша задача узнать, есть ли у него шансы на победу. Учтите, что черным и белым королем была выработана стратегия, в соответствии с которой, они выбрали один из кратчайших путей. Помните, что они не видят черно-белого короля. У черно-белого короля тоже есть стратегия: он всегда передвигается так, что любой отрезок его пути нельзя улучшить по длине (скажем зигзагами он ходить не может).
В случае положительного ответа (то есть при ненулевой вероятности победы черно-белого короля) найдите наименьшее число ходов, необходимымых для вероятной победы. Иначе выведите наименьшее суммарное количество ходов белого и черного короля необходимых для встречи. Помните порядок ходов: белый король, черный, черно-белый. Любой король ходит на одну из 8 соседних клеток.
Замечание: длиной пути короля здесь называем сделанное количество ходов.

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

В первой строке записано число N (2<=N<=10^6). Во второй строке пара чисел P1, Q1 (0<P1,Q1<N+1) - координаты черного короля, в третьей записаны P2, Q2 (0<P2,Q2<N+1) - координаты белого короля. В четвертой строке парой чисел P3, Q3 (0<P3,Q3<N+1) задана позиция черно-белого короля. Все позиции различны.

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

Выведите в первой строке <YES> если ответ положителен и <NO> в противном случае. Во второй строке выведите число, количественный ответ поставленной задачи

Пример

Ввод

Test #1
5
1 1
5 3
2 3

Test #2
5
1 1
5 3
2 4

Вывод

Test #1
YES
1

Test #2
NO
3

Одна научная загадка

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

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

 

На необитаемом острове живет племя из N (1<=N<=100) аборигенов. С целью восстановления хода великого исторического события на этот остров прибыло M (1<=M<=100) сыновей Кука. Требуется определить, смогут ли аборигены "поделить" между собой всех сыновей Кука, так чтобы каждому досталось одинаковое количество людей.

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

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

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

Выведите "Party is coming", если описанное деление возможно и "It is a boring day" в противном случае.

Пример

Ввод

7 21

Вывод

Party is coming

Слияние чисел

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

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

 

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

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

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

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

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

Пример

Ввод

20
4181

Вывод

421810

Всеберляндская олимпиада

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

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

 

В первой традиционной Всеберляндской олимпиаде по информатике приняло участие N человек, набравших A1, A2,...,AN баллов соответственно. Участники, набравшие одинаковое число баллов, должны получить одинаковые дипломы. То есть если M - наибольшее из чисел A1, A2,...,AN, то все участники набравшие по M баллов получают диплом первой степени. Ваша задача узнать сколько баллов необходимо набрать, чтобы получить дипломы первой, второй и третьей степени соответственно.

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

В первой строке входного файла содержится натуральное число N (3<=N<=100). Во второй строке содержатся неотрицательные целые числа A1, A2,...,AN (0<=Ak<=200, k=1..N), разделённые пробелами. Известно, что среди этих чисел существует по крайней мере три различных.

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

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

Пример

Ввод

5
115 169 200 145 113

Вывод

200 169 145

Монеты

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

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

 

В стране Берляндии находятся в обращении K различных видов монет, достоинством V1<V2<...<VK. Известно, что V2 делится нацело на V1, V3 на V2,..., VK делится нацело на VK-1. Это значит, что в обращении могут быть монеты достоинством, например, в 1, 2, 6 и 30 бурлей, но не в 1, 2 и 5 бурлей (поскольку 5 не делится на 2). Монеты в Берляндии имеют одну особенность - они все совершенно одинаковые по размеру. Требуется узнать наибольшую возможную сумму денег, которую гарантированно вы можете набрать, если у вас имеется в кармане ровно N монет, и вам не известно каких они достоинств. Не исключено, что в вашем кармане есть монеты одинакового номинала.

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

Входной файл из двух строк. В первой строке находится единственное натуральное число N (1<=N<=100) - количество монет в Вашем кармане. Во второй строке находится число K (1<=K<=20) - количество различных номиналов монет, находящихся в обращении, и далее через пробел K натуральных чисел V1, V2,.., VK - достоинства этих монет, удовлетворяющие соотношению 0<V1<V2<...<VK<1001.

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

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

Пример

Ввод

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

Пример #2
5
3 1 2 6

Вывод

Пример #1
2

Пример #2
0

126. "БерНефть и сыновья"

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

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

 

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

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

В первой строке входного файла записано натуральное число N (1<=N<=600). Далее в N строках следуют описания местоположений нефтяных вышек. Вышка описывается парой чисел - своими координатами в некоторой декартовой системе координат. Все координаты - целые числа, по модулю не превосходящие 10^4.

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

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

Пример

Ввод

4
1 1
3 4
4 4
7 7

Вывод

3

127. "Не будет жизни вам пока..."

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

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

 

В Берляндии снова президентские выборы. В рамках предвыборной кампании "Не будет жизни вам пока..." основного кандидата было решено опубликовать Гороскоп Страны на период президентства в случае победы нашего кандидата.
В связи с этим было решено прибегнуть к услугам знаменитейшего астролога Павла Глобуса. Его задача - узнать количество несчастливых лет в период правления Нового Президента. После бессонных ночей непрерывных вычислений, Павел Глобус понял, что год несчастливый тогда и только тогда, когда в десятичной записи его порядкового номера встречается цифра "3". Знаменитейший астролог совершенно не умеет работать с компьютером. Помогите ему вычислить количество несчастливых лет с года N по M включительно.

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

В первой строке входного файла записаны два натуральных числа N и M (1<=N<=M<=10^9) через пробел.

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

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

Пример

Ввод

37 45

Вывод

4

Пояснение

Пояснение к примеру: несчастливые годы - 37, 38, 39 и 43.

Ограбление века

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

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

 

Четверо грабителей в течение K дней похищали по N алмазов из Национального Берляндского Алмазного Фонда. Скупщик краденного по прозвищу Жмот оценил алмазы в A11, A12,...,A1N бурля соответственно в первый день, в A21, A22,...,A2N бурля во второй и т.д. вплоть до K-ого дня, когда он оценил алмазы в AK1, AK2,...,AKN бурля соответственно. Однако, так как это были честные грабители, то они хотели делить алмазы ежедневно так, чтобы каждому из четверых грабителей доставалось драгоценностей на равную сумму. Ваша задача для каждого дня узнать, возможно ли распределить алмазы с соблюдением принципа "честности" грабителей.

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

В первой строке входного файла записаны два натуральных числа K и N (1<=K<=100, 1<=N<=11) через пробел. Далее следует K строк, в каждой из которых содержится по N чисел, причем в строке с номером P (из этих K строк) Q-ое по порядку число есть APQ. Числа в строках разделены пробелами. Все оценочные стоимости - натуральные целые числа, меньшие 10^5.

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

Выведите К строк. В строке с номером P запишите "YES", если в P-ый день возможно распределить алмазы с соблюдением принципа "честности" и "NO" в противном случае.

Пример

Ввод

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

Вывод

NO
YES
YES

Mr. Битл

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

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

 

Сад имеет форму прямоугольной таблицы NxM клеток. В левой верхней клетке (1,1) живет жук по имени Mr. Битл. Он решил навестить свою кузину, которая живет в правой нижней клетке (N,M). Жук умеет передвигаться по полю только вправо, влево и вниз. На каждой клетке поля растет от 0 до 9 (включительно) цветов, кроме того, некоторые клетки "добрые" садоводы обработали ядом, смертельным для жуков. На ядовитых клетках цветов быть не может. Требуется узнать, какое наибольшее количество цветов Mr. Битл сможет набрать по пути к кузине. В клетках (1,1) и (N,M) как цветов, так и яда нет.

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

В первой строке записаны два числа N и M (1<=N<=800, 1<=M<=800, N+M>2) - количества строк и столбцов таблицы соответственно. Далее в N строках записано по M символов, описывающих сад. Если в строке номер P (из этих N) в позиции Q стоит цифра, то в соответствующей клетке поля растет такое количество цветов. Если в этой клетке стоит символ "*", значит в клетке яд.

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

Если безопасный путь существует, то выведите в первой строке неотрицательное число - наибольшее количество цветов, собранных по пути. Если безопасного пути к кузине не существует, выведите фразу "SEE YOU LATER". Mr. Битл может позволить себе пройти через клетку (N,M), побывать где-то еще и потом окончательно вернуться к кузине. Не забывайте, что Mr. Битл ходит только вправо, влево или вниз.

Пример

Ввод

3 5
0044*
300*7
00100

Вывод

12

Поиск ключа

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

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

 

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

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

В первой строке записаны N и K (1<=K<=N<=1000). Далее идет N строк с числами, записанными на первой странице рукописи.

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

Выведите S.

Пример

Ввод

6 3
999
-05
-10
0
1`3
0101

Вывод

-15

Многоугольник

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

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

 

Подобрав ключ, ученые столкнулись с загадкой, записанной на второй странице. Там был нарисован правильный N-угольник и две точки вне N-угольника. И вопрос гласил: "Нитку какой минимальной длины можно взять, чтобы ею можно было соединить эти две точки, нигде не накрывая N-угольник?". Профессор Бурункин справедливо заметил, что граничные точки многоугольника накрывать наверняка можно, а то задача лишена смысла. Он даже вычислил требуемую длину нитки S, но он это сделал с очень маленькой точностью. Тогда он ввел декартову систему координат так, что центр N-угольника стал точкой с координатами (0,0). Затем записал координаты одной из вершин N-угольника, а также координаты 2-х заданных точек. По этим данным Вам необходимо найти S.

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

В первой строке записано число N (3<=N<=30). Во второй строке записаны координаты одной из вершин N-угольника. В третьей и четвертой строке записаны координаты первой и второй точки соответственно. Все координаты - действительные числа, по абсолютной величине не превосходящие 1000, заданные не более чем с двумя знаками после запятой, и записанные между собой через пробел.

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

Выведите S с точностью до двух знаков после запятой.

Пример

Ввод

3
0 3
4 0
-4 0

Вывод

9.30