В фирме, в которой работает ваш друг, ввели новый дизайн билетов на маршрутки. Теперь номер билета может быть любым натуральным числом. Радостные пассажиры тут же придумали новый, очень простой способ определения счастливости номера билета. Он состоит в следующем. Пусть номер билета равен \(N\). Если \(N<10\), то счастливость числа \(N\) (т.е. и самого билета) равна \(N\), иначе: посчитаем сумму цифр числа \(N\), пусть она равна \(S\) — тогда счастливость числа \(N\) будет равна счастливости числа \(S\).

Например, счастливость билета с номером \(7351\) равна счастливости билета с номером \(16\) (т.к. \(7+3+5+1=16\)), а она в свою очередь равна счастливости билета с номером 7 (т.к. \(1+6=7\)), а последняя просто равна 7 (т.к. \(7<10\)).

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

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

Напишите программу, которая будет решать эту задачу, т.е. по данному \(N\) находить такое его представление \(N=a_1\cdot a_2\cdot \ldots\), где все \(a_i\) натуральны, больше единицы, и суммарная счастливость чисел \(a_1\), \(a_2\), ... максимальна.

В последнее время в одной из школ Н. Новгорода, а также на одном из факультетов ННГУ стала очень популярна игра в настольный теннис. Игроки часто сталкиваются со следующей проблемой: довольно трудно уследить за всем ходом матча и при этом не сбиться со счёта, поэтому очень хотелось бы иметь программу, подсчитывающую счёт. Напишите программу, которая по данному протоколу матча восстановит итоговый счёт.

Протокол состоит из последовательности следующих событий: service, net, out, goal, return, eom.

События обозначают следующее:

* service — подача (при этом игрок ударяет по мячу). service — всегда первое событие во входном файле. После него могут следовать net, out, goal, return.

* net — мяч ударяется о половину поля того игрока, который ударял по мячу последним, слишком много раз. Игрок, который ударял по мячу последним, проигрывает розыгрыш. После этого события могут идти service или eom.

* out — мяч уходит в аут. Игрок, который ударял по мячу последним, проигрывает розыгрыш. После этого события могут идти service или eom.

* goal — игрок, который ударял по мячу последним, забивает гол (т.,е. выигрывает розыгрыш). Далее может быть service или eom.

* return — игрок отбивает мяч, ударяя по нему (игроки ударяют по мячу по очереди). Далее может быть net, out, goal, return.

* eom — матч окончен. Это всегда последнее событие.

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

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

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

На плоскости заданы дуга окружности, отрезок и точка. Как отрезок, так и дуга окружности непрозрачны. Определите, какая часть дуги видна из этой точки.

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

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

Система дорог в области устроена следующим простым образом. Есть \(N\) населённых пунктов, некоторые из которых соединены дорогами. Между каждой парой пунктов существует не более одной дороги, и более того, для каждой пары населённых пунктов есть ровно один способ добраться из одного в другой (возможно, через промежуточные посёлки).

В каждом населённом пункте можно разместить ремонтную подстанцию. В принципе, фирма может размещать как крупные подстанции, которые даже в одиночку смогут обслуживать всю область, но при этом будут требовать больших расходов на содержание, так и небольшие станции, которые будут обслуживать лишь прилегающие населённые пункты, но при этом будут обходиться намного дешевле. Фирма уже определила, что каждую подстанцию можно характеризовать параметром “мощность”, которая может принимать значения, являющиеся целыми положительными числами (равна нулю мощность быть не может). Подстанция с мощностью \(k\) будет обслуживать населённый пункт u, в котором она расположена, и все другие населённые пункты, до которых можно добраться из u, использовав не более k дорог (т.е. при \(k\)=1, например, подстанция обслуживает свой населённый пункт и все, которые напрямую соединены с ним дорогой). Стоимость содержания такой подстанции пропорциональна её мощности.

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

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