Информатика

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

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

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

Формат входных данных
Первая строка входных данных содержит целое число \(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.

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

С клавиатуры вводится натуральное число n (n<=100). Напишите программу, которая вычисляет сумму
\(n^2 + (n+1)^2 + (n+2)^2 + ... + (2 \cdot n)^2\).
 

С клавиатуры вводится натуральное число n (n <= 100). Найдите сумму
\(1 + {1 \over 2}+{1 \over 3} +...+{1 \over n} \)

Ваш ответ будет проверен с точностью до 6 знака в дробной части.

Напишите программу, которая находит среднее арифметическое всех целых чисел от b до 2*b (значение b вводится с клавиатуры; 1 <= b <= 100). Ваш ответ будет проверен с точностью до 6 знака в дробной части.

Напишите программу, которая находит сумму всех целых чисел от a до 20 (значение a вводится с клавиатуры; 1 <= a <= 20).
 

Напишите программу, которая находит сумму чисел от 100 до 500 с помощью оператора цикла for. 

Формат входных данных
Программа ничего не получает на вход. 

Формат выходных данных
Выведите одно число - ответ на задачу. 

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

У Старца Летовца есть набор чисел. Эти числа можно склеивать друг с другом (или не склеивать вовсе), чтобы получать новые числа. Например, из набора чисел 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⁵).


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