Задача A. Ёлочки 2

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

Условие

Скоро Новый Год! А это значит, что на носу конец второй четверти и Тимофею самое время взяться за исправление отметок по рисованию. На сегодняшнем уроке весь класс рисует зимний лес. К сожалению, с передачей художественных образов изобразительными методами дела у Тимофея обстоят из рук вон плохо. Но хоть что-то нарисовать нужно, поэтому Тимофей рисует ёлочки по клеточкам.

Каждая елочка имеет свою красоту, равную количеству ветвей с одной стороны ствола и (так уж совпало) длине самой нижней ветви. Каждая следующая верхняя ветка на одну клетку короче предыдущей. Между ветвями, а также под самой нижней и над самой верхней ветвями находится ствол дерева шириной ровно в одну клетку. На рисунке вы видите ёлки кисти Тимофея красотой от 0 до 5 включительно.

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

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

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

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

Выведете одно натуральное число - периметр ёлки красоты n.

Ограничения

0 ≤ n ≤ 109

Система оценки и описание подзадач

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

Подзадача 1: 0 ≤ n ≤ 105, баллы: 30.

Подзадача 2: нет дополнительных ограничений, баллы: 70.

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

Стандартный вход Стандартный выход
1
5
84

Задача B. Пёстрые числа

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

Условие

Целое неотрицательное число, все цифры которого различны, назовем пёстрым. Напишите программу .

Требуется написать программу, находящую максимальное пёстрое число, которое делится на заданное натуральное число n.

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

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

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

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

Ограничения

1 ≤ n ≤ 1015

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

Стандартный вход Стандартный выход
1
10
9876543210
2
200
0

Задача C. Четыре в ряд

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

Условие

Игра "четыре в ряд" идёт на прямоугольном клетчатом поле из 7 столбцов и 6 строк. Первоначально все клетки пустые (символ "."). Игроки по очереди ставят на поле свои символы, первый игрок ставит символ "X" (ASCII 88), второй игрок — символ "O" (ASCII 79).

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

Игра заканчивается, когда один из игроков собрал четыре своих символа в ряд по вертикали, горизонтали или диагонали.

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

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

Первая строка содержит целое число T — количество тестов. Далее идут описания тестов, на каждый тест 6 строк по 7 символов в каждой — описание позиции. Тесты разделены одиночными пустыми строками.

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

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

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

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

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

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

.......
.......
.......
....X..
....O..
...OX..

.......
.......
.......
....X..
.X..O..
...OX..

.......
.......
.......
....X..
....O..
O..OX..

.......
.......
.......
..X....
....O..
...OX..

.......
.......
.......
....X..
....O..
O..OX..

.......
OO.....
OO.....
OX.....
XX.....
XX.X...

.......
.......
.......
....O..
OOO.OOO
XXXXXXX

.......
.......
.......
.......
OOO.OOO
XXXXXXX

.......
.O.....
OO.....
OX.....
OX.....
XX.XX..
1 5
4 5 5 5 4
-1
-1
-1
-1
-1
-1
13 7 7 6 6 5 5 3 3 2 2 1 1 4
11 1 1 2 1 2 1 2 2 5 2 4

Задача D. Каравай

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

Условие

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

Каравай состоит из 3 круглых коржей. Площади коржей различны и возрастают от верхнего коржа к нижнему. Радиус каждого следующего коржа отличается от предыдущего не менее чем на d.

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

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

Известно, что центр каравая находится в точке (0,0). Все коржи имеют общий центр.

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

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

Первая строка входных данных содержит 2 вещественных числа: S, d.

Вторая строка входных данных содержит количество мармеладок: N.

В следующих N строках содержатся по 2 вещественных числа: x, y - координаты мармеладки.

Вещественные числа содержат не более 4 знаков после запятой

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

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

Если коржи слепить не представляется возможным - ответом является -1

Ограничения

1.0 ≤ S ≤ 109

1.0 ≤ d ≤ 103

109 ≤ x, y ≤ 109

1 ≤ N ≤ 105

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100.0 2.0
3
0.1 0.1
0.2 0.2
0.6 0.6
2
2
100.0 40.0
1
1.5 1.5
-1

Задача E. Паркет

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

Условие

Андрей укладывает дома пол. У него длинный коридор длиной L.

У Андрея есть бесконечное количество досок, длины которых равны d. Необходимо полностью уложить пол досками. Доски можно пилить, но при этом в укладке нельзя использовать части досок короче c.

Сколько досок Андрею необходимо разрезать, чтобы уложить пол?

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

Входные данные содержат три целых числа: L, d, c.

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

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

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

Ограничения

1 ≤ L, d ≤ 109

0 ≤ c ≤ 109

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

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

Задача F. Игра с конфетами

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

Условие

Внимание! У этой задачи необычные правила оценивания. Прочитайте раздел "Описание подзадач и системы оценивания".

Алхимик и его ездовой огр играют в следующую игру: изначально у огра A конфет, у алхимика B конфет. Игроки ходят по очереди и могут сделать одно из двух действий: съесть свою конфету, или забрать конфету у другого игрока при условии того, что на прошлом ходу другой игрок не забирал конфету у нас. Если так случилось, что игрок не может сделать ход, но конфеты ещё не закончились, он просто ждёт. Если у игрока есть возможный ход, он не может ждать и ничего не делать. Игра кончается когда у огра и у алхимика по 0 конфет. Первым ходит огр.

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

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

Первая строка входного файла содержит два целых числа a и b.

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

Первая строка выходного файла должна содержать целое число N  — количество ходов, совершённых игроками. Вторая строка должна содержать N символов  — ходы игроков, нечётные ходы — это ходы огра, чётные — алхимика. Символ "E" означает, то что ходящий игрок съедает свою конфету, символ "T" означает, то что игрок забирает конфету у другого игрока, символ "W" означает, то что игрок не может ходить и ждёт.

Ограничения

0 ≤ a, b ≤ 3000

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

За каждый тест балл выставляется в зависимости от близости к правильному решению. Если ваш ответ хуже правильного ответа меньше чем на 1 или совпадает с ним, вы получаете 2 балла, если ваш ответ хуже правильного на 2 или на 3, вы получаете 1 балл. Всего в задаче 60 тестов. 10 тестов где 0 ≤ a, b ≤ 10, 40 тестов 0 ≤ a, b ≤ 300.

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

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

0.214s 0.005s 21