Информатика

Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.
Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X = 0 или Y = 0 такой фонарь освещает только тот дом, у которого он установлен.
Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.

Формат входных данных
Первая строка входных данных содержит целое число N (1 ≤ N ≤ 10⁵ ). Следующие четыре строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосходят 10⁵ .
Формат выходных данных
Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел — координату фонаря и расстояние, которое он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1 до N, рядом с каждым домом можно поставить только один фонарь. При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа должна вывести одно число −1

Замечание
В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 — также дома 3, 4, 6 и 7, а фонарь у дома 9 — также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно.

Для хранения произвольного растрового изображения размером 1536×2048 пикселей отведено не более 6 Мбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?

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

Цвет	Кодовое слово		Цвет	Кодовое слово
Белый	0		Синий
Зелёный	11111		Фиолетовый	11110
Красный	1110		Чёрный	10

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

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

Дан массив \([a_1, a_2, \ldots, a_n]\), состоящий из неотрицательных целых чисел.

Рассмотрим разбиение массива на \(k\) непустых отрезков подряд идущих элементов. Назовем перекосом разбиения разность между максимальной и минимальной суммой чисел в отрезках разбиения. Требуется найти максимальный перекос разбиения данного массива на \(k\) подотрезков.

Например, если массив равен \([2, 1, 3, 4]\), то у разбиения \([2, 1, 3][4]\) перекос равен \(6-4=2\), у разбиения \([2, 1] [3, 4]\) перекос равен \(7-3=4\), а у разбиения \([2] [1, 3, 4]\) перекос равен \(8-2=6\). Последний вариант является оптимальным среди всех разбиений массива на два непустых отрезка.

Формат входных данных
Первая строка содержит два целых числа \(n\) и \(k\) (\(2 \le k \le n \le 300\,000\)) — длину массива и количество подотрезков, соответственно.

Вторая строка содержит \(n\) целых чисел \(a_i\) (\(0 \le a_i \le 10^9\)) — элементы массива.

Формат выходных данных
Выведите одно число — максимальный перекос разбиения данного массива на \(k\) отрезков.

Примечание
Первый пример разобран в условии задачи.

Во втором примере оптимальным разбиением является \([2][1][3, 4][1]\). Максимальная сумма на подотрезках в данном разбиении равна \(3 + 4 = 7\), минимальная сумма равна \(1\), таким образом, перекос равен \(6\).

Вася — очень порядочный мальчик, он любит порядок во всём.

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

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

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(2 \le n \le 3 \cdot 10^{5}\)) — количество чисел в тетрадке у Васи.

Следующие \(n\) строк содержат \(n\) чисел, записанных в тетрадке, по одному в каждой строке. Все числа натуральные, не превосходящие \(10^9\).

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

Примечание

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

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

В третьем примере Вася может, например, получить числа 20, 25, 100. Возможны и другие варианты, но последнее число при любом способе дописывания цифр получится не меньше 100.

Дана клетчатая сетка, состоящая из \(n \times m\) клеток со стороной 1, в каждой клетке проведены обе диагонали.

Например, сетка \(1 \times 2\) выглядит следующим образом:

Назовём прямоугольник на данной сетке подходящим, если его вершины расположены в узлах сетки, а длины его стороны равны \(1\) или \(2\) (то есть подходящими являются прямоугольники \(1\times1\), \(1\times2\), \(2\times1\), \(2\times2\)).

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

Посчитайте количество хороших треугольников на данной сетке.

Формат входных данных
Программа получает на вход два числа \(n\) и \(m\), записанных в отдельных строках, — размеры сетки, \(1 \le n \le 10^{8}\), \(1 \le m \le 10^{8}\).

Формат выходных данных
Программа должна вывести одно целое число — количество искомых треугольников.

Обратите внимание на то, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в языке C++, тип int64 в Pascal, тип long в Java и C#).

В данной задаче \(20\) тестов помимо тестов из условия, каждый из них оценивается в \(5\) баллов. При этом в 4 тестах (помимо тестов из условия) \(n\) или \(m\) равно 1, в 4 других тестах \(n\) или \(m\) равно 2.

Все треугольники из первого примера:

Вдоль течения реки размещены \(n\) пристаней, пронумерованных числами от 1 до \(n\). Пристань номер 1 находится выше всех остальных по течению реки, пристань номер \(n\) находится в устье реки, расстояние между соседними пристанями равно 1 км.

Для развития туризма решено открыть два прогулочных речных маршрута. Маршруты будут начинаться на одной из промежуточных пристаней (пристани номер 1 или \(n\) не могут быть начальными точками маршрутов), один маршрут будет идти вверх по течению реки к пристани номер 1, другой маршрут будет идти вниз по течению к пристани номер \(n\). Промежуточных остановок на маршрутах нет.

Для подъёма вверх по течению реки судно тратит \(a\) минут на один километр, а для спуска вниз по течению реки — \(b\) минут на один километр. Определите, на какой пристани должны начинаться оба маршрута, чтобы их продолжительности различались как можно меньше. Это значит, что необходимо минимизировать модуль разности времени в пути двух маршрутов.

Формат входных данных
Первая строка входных данных содержит целое число \(n\) (\(3\le n\le 2\cdot 10^9\)) — общее количество пристаней на маршруте. Вторая строка содержит число \(a\) — время подъёма судна на один километр вверх по течению реки, третья строка содержит число \(b\) — время спуска на один километр вниз по течению, \(1\le b < a\le 2\cdot 10^9\).

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

Примечание
В примере из условия начальным пунктом маршрутов нужно сделать пристань 3. Тогда вверх по течению судно поднимется за \((3-1)\times 7=14\) минут, а вниз по течению реки спустится за \((8-3)\times3=15\) минут. Разница в продолжительности маршрутов составит 1, меньшей разности в данном примере достичь невозможно.

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня либо увеличить количество камней в куче в два раза. Например, имея кучу из 12 камней, за один ход можно получить кучу из 13, 16 или 24 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 27.

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

В начальный момент в куче было S камней; 1 ≤ S ≤ 26.

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

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.


Задание 2)
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

-       Петя не может выиграть за один ход;
-       Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 3)
Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:

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

Если найдено несколько значений S, в ответе запишите минимальное из них.



Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел
 

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

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 128.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.


Задание 2) 

Найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.


Задание 3)
Найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

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


Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 48.

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

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.



Задание 2)

Для игры, описанной в задании 19, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

-       Петя не может выиграть за один ход;
-       Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.


Задание 3) 

Для игры, описанной в задании 19, найдите значение S, при котором одновременно выполняются два условия:

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

Если найдено несколько значений S, в ответе запишите минимальное из них.


Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел

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

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

В начальный момент в куче было S камней; 1 ≤ S ≤ 42.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом


Задание 2)
Для игры, описанной в задании 19, найдите два таких минимальных значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.


Задание 3) 
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если найдено несколько значений S, в ответе запишите наименьшее из них.


Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел
 

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

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

В начальный момент в куче было S камней; 1 ≤ S ≤ 90.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.


Задание 2) 

Найдите два таких минимальных значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.


Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел

Задание 3) 

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если найдено несколько значений S, в ответе запишите наименьшее из них.

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

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 132.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.


Задание 2)
Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.


Задание 3)
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.


Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел

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

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

В начальный момент в первой куче было 17 камней, во второй куче - S камней; 1 ≤ S ≤ 213.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 1)
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.


Задание 2)
найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.


Задание 3)

Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.



Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 73.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, состоящую из 73 или более камней.
В начальный момент в куче было S камней; 1 ≤ S ≤ 72.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Задание 2)

Найдите два таких минимальных значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 3) 

Найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если найдено несколько значений S, в ответе запишите наименьшее из них.
 

Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел

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

Игра завершается в тот момент, когда количество камней в куче становится не менее 103.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, состоящую из 103 или более камней.
В начальный момент в куче было S камней; 1 ≤ S ≤ 102.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.

Задание 1)
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.

Задание 2)

Найдите два таких минимальных значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 3)
Найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Если найдено несколько значений S, в ответе запишите наименьшее из них.


Ответ на каждое задание запишите в отдельной строке:

1. в первой строке на задание 1;
2. во второй на задание 2;
3. в третьей на задание 3.

Если в ответе на какое-либо задание необходимо указать два числа, то в строке необходимо их записать через один пробел

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

У Старца Летовца есть набор чисел. Эти числа можно склеивать друг с другом (или не склеивать вовсе), чтобы получать новые числа. Например, из набора чисел 12, 2 и 10 можно склеить число 12210, а можно 10212 — вариантов много, но выбрать придётся только один, потому что все числа в наборе в единственном виде.
Летовёнок задумался: какое максимальное количество чисел, делящихся на три, можно получить из этого набора?

Помогите ему решить эту задачу.

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

В первой строке ввода дано единственное число n (1<= n <=1000). Во второй строке ввода через пробел даны n чисел numi (1<=numi<=1000).

Формат выходных данных
Выведите одно число - максимальное количество чисел, кратных трём, которые можно получить из набора.


Примечание
В первом тестовом примере можно склеить числа 2 и 10 (получить 210 или 102) и в итоге получится 2 числа, кратные трём.

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

Старец Летовец, известный своими суперскиллами, решил научить своих учеников создавать "Последовательность Трёх Сил". Он дал им список чисел и сказал: "Отсортируйте эти числа так, чтобы они образовали Последовательность Трёх Сил. Вот правила:"

1. Сила Тройки. Числа, которые делятся на 3, должны идти первыми.

2. Сила Порядка. Среди чисел, делящихся на 3, меньшие числа должны идти перед большими.

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

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

Формат входных данных
В первой строке записано натуральное число n (n <= 10⁵) - количество целых чисел в списке. Далее, в n строках записано по одному целому числу numi ( -10⁵ <= numi <= -10⁵).


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

Старец Летовец, известный своей любовью к математике, решил проверить смекалку своих учеников. Он дал им n конфет и сказал: "Разложите эти конфеты на три кучки так, чтобы в каждой кучке было не больше, чем limit. И определите сколькими различными способами это можно сделать?"

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

Формат входных данных
В первой строке входных данных записано натуральное число n, во второй - натуральное число limit.

Ограничения

• 1 <= n <= 1000
• 1 <= limit <= 1000

Формат выходных данных
Выведите одно число - количество способов


Примечание
В первом тестовом примере есть 3 способа разложить 5 конфет таким образом, чтобы в каждой кучке было не больше 2 конфет: (1, 2, 2), (2, 1, 2) и (2, 2, 1).
Во втором тестовом примере существует 10 способов распределить 3 конфеты таким образом, чтобы в каждой кучке было бы не больше 3 конфет: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) и (3, 0, 0).
 

В городе Летовецк  "Фестиваль Чисел" отмечается всегда в день с магической датой. Дата называется магической, если день, номер месяца и две последние цифры года совпадают. Например, 01.01.01 - магическая дата. 
По текущей дате, записанной в формате дд.мм.гг определите дату, когда будет отмечатся ближайший "Фестиваль чисел". То есть первую магическую дату, которая была бы не ранее текущей.

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