В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».

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

Муха летит вдоль прямой. Если нанести на эту прямую координаты, то можно сказать, что в 0-й момент времени муха пролетает точку с координатой 0 и летит в положительном направлении со скоростью V. Муха может менять свою скорость, однако ускорение мухи не может по модулю превышать величины A, в частности, муха не может мгновенно остановиться. Максимальная скорость мухи не может превышать по модулю величины W.

Известно, что в момент времени T по прямой ударит мухобойка, которая полностью накроет отрезок от точки C до точки D. Если муха в этот момент окажется на этом отрезке, она погибнет.

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

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

Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (A_i, B_i).

Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (A_i, B_i) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах A_i и B_i и поменять их местами.

Например, если N=5. Тогда изначально Васей выписана последовательность

1 2 3 4 5

Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.

Например, он может последовательно получить следующие последовательности:

2 1 3 4 5 (поменяв числа на 1 и 2 местах)

2 5 3 4 1 (поменяв числа на 2 и 5 местах)

5 2 3 4 1 (поменяв числа на 1 и 2 местах).

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

От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).

Напишите программу, которая поможет Пете справиться с этой задачей.

SMS-сообщения на мобильном телефоне марки MOBILO набираются только заглавными английскими буквами. Для набора буквы нужно нажать кнопку, на которой эта буква написана, при этом если эта буква написана первой, то кнопку нужно нажать один раз, если второй – то два раза и т.д. Устройство клавиатуры телефона приведено на рисунке.

Таким образом, чтобы набрать слово SMS, нужно нажать следующие кнопки:

<PQRS> <PQRS> <PQRS> <PQRS> <MNO> <PQRS> <PQRS> <PQRS> <PQRS>

Для набора двух букв, которые находятся на одной кнопке, при наборе нужно сделать паузу между их вводом. Например, чтобы набрать BA, нужно два раза нажать кнопку <ABC>, затем сделать паузу и затем нажать кнопку <ABC> еще раз.

Если на кнопке написано три буквы, то как только эта кнопка нажата три раза подряд, последняя из написанных на ней букв сразу же добавляется в сообщение, а дальнейшие нажатия на эту кнопку воспринимаются как ввод следующей буквы. То же самое, если на кнопке написано 4 буквы. Таким образом, 4-х кратное нажатие на кнопку <ABC>, затем пауза, и затем нажатие на эту кнопку еще раз приведет к вводу текста CAA.

К сожалению, в силу произошедшего глюка, телефон стал иногда игнорировать паузы при вводе, а, иногда, наоборот, вести себя так, как будто была пауза тогда, когда паузы не было. Например, при вводе слова MOSCOW могло в итоге (как один из вариантов) получиться слово OMSCMNW.

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