Задачи очного тура личного первенства университета 2004

Санта-Клаус хочет подарить всем уникальные подарочные наборы ровно из `M` предметов. Для этого у него есть неограниченное количество предметов, относящимся к `N` классам (фрукты, игрушки, косметика и т.д.). В каждом классе можно выделить также несколько категорий предметов, например, в класс фрукты попадают яблоки, апельсины, груши и т.д. Все предметы, относящиеся к одной категории, являются одинаковыми. Санта-Клаус не хочет, чтобы в одном наборе оказалось несколько предметов, относящихся к одному классу, например, яблоко и апельсин или два яблока.

Напишите программу, которая по числу классов и числу категорий в каждом классе определит количество различных подарочных наборов из `M` предметов, которые сможет сформировать Санта-Клаус. Подарочные наборы являются различными, если они отличаются хотя бы одной категорией входящих в них предметов.

Во входном файле в первой строке содержатся два целых числа `N` и `M` (`0\ <\ M\ ≤\ N\ ≤\ 10`), разделенных пробелом – количество классов и количество предметов в наборе. Во второй строке содержится `N` целых чисел от 1 до 10, разделенных пробелами – количество категорий в каждом классе.

В выходной файл вывести одно число – количество различных подарочных наборов из `M` предметов.

3 2
2 3 4

26

1 апреля 2005 года будет проведена реформа английского языка, позволяющая облегчить его освоение иностранцами и английскими школьниками. Во-первых, из алфавита уберут четыре буквы C, Q, W и X (на клавиатуре компьютера вместо них будут клавиши, вызывающие программы Word, eXcel и другие). Вместо c перед буквами e, i, y нужно будет писать букву s, а в остальных случаях – букву k. Вместо буквы q нужно будет писать букву k, вместо сочетания qu – kv, вместо x – ks, а вместо w – v. Во-вторых, сочетание букв ph будет записываться как f, you и oo – как u, ee – как i, th – как z. Кроме того, все двойные согласные (включая образовавшиеся после замен), вызывающие большие трудности у учащихся, станут одинарными, например, apple после реформы нужно писать как aple.

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

Во входном файле содержится текст на английском языке, без переносов слов. Длина строк не превышает 100 символов.

В выходной файл вывести тот же текст, но уже соответствующий реформе. Если первая буква заменяемого сочетания букв была прописной, то первая буква замены должна быть также прописной. Вторая буква в заменах x `→` ks, qu `→` kv должна быть всегда строчной.

Too swift for Theex, too quick for Gallow,
Too strong for young Prince Joseph to follow.

Tu svift for Ziks, tu kvik for Galov,
Tu strong for ung Prinse Josef to folov.

Основой для задачи послужило несколько юмористических статей:

The European Union commissioners have announced that agreement has been reached to adopt English as the preferred language for European communications, rather than German, which was the other possibility. As part of the negotiations, Her Majesty's Government conceded that English spelling had some room for improvement and has accepted a five-year phased plan for what will be known as EuroEnglish (Euro for short).

In the first year, "s" will be used instead of the soft "c". Sertainly sivil servants will resieve this news with joy. Also, the hard "c" will be replased witk "k". Not only will this klear up konfusion, but typewriters kan have one less letter.

There will be growing publik enthusiasm in the sekond year, when the troublesome "ph" will be replaced by "f". This will make words like "fotograf" 20 persent shorter.

In the third year, publik akseptanse of the new spelling kan be expekted to reach the stage where more komplikated changes are possible. Governments will enkorage the removal of double letters, which have always ben a deterent to akurate speling. Also, al will agre that the horible mes of silent "e"s in the languag is disgrasful, and they would go.

By the fourth year, people wil be reseptiv to steps such as replasing "th" by "z" and "w" by "v". During ze fifz year, ze unesesary "o" kan be dropd from vords kontaining "ou" and similar changes vud of kors be aplid to ozer kombinations of leters.

After ze fifz yer, ve vil hav a reli sensibl riten styl. Zer vil be no mor trubls or difikultis and evrivun vil find it ezi tu understand ech ozer.

Ze drem vil finali kum tru.

For example, in Year 1 that useless letter "c" would be dropped to be replased either by "k" or "s," and likewise "x" would no longer be part of the alphabet. The only kase in which "c" would be retained would be the "ch" formation, which will be dealt with later. Year 2 might reform "w" spelling, so that "which" and "one" would take the same konsonant, wile Year 3 might well abolish "y" replasing it with "i" and Iear 4 might fiks the "g / j" anomali wonse and for all.

Jenerally, then, the improvement would kontinue iear bai iear with Iear 5 doing awai with useless double konsonants, and Iears 6-12 or so modifaiing vowlz and the rimeining voist and unvoist konsonants. Bai Iear 15 or sou, it wud fainali bi posibl tu meik ius ov thi ridandant letez "c," "y," and "x" – bai now jast a memori in the maindz ov ould doderez – tu riplais "ch," "sh," and "th" rispektivli.

Fainali, xen, aafte sam 20 iers ov orxogrefkl riform, wi wud hev a lojikl, kohirnt speling in ius xrewawt xe Ingliy-spiking werld.

Шарик бросается в дырку в верхней крышке коробки, представляющей из себя лабиринт. Коробку можно наклонять в 4 направлениях N, W, S и E (как показано на рисунке, буква указывает опускаемую сторону прямоугольной коробки) и управлять таким образом движением шарика. В нижней крышке коробки есть другая дырка, через которую шарик вывалится, если он до нее докатится. Крышки и стенки коробки непрозрачны, поэтому точное местоположение шарика в коробке неизвестно. По этой причине изменять направление движения шарика можно только, когда он докатится до какой-нибудь стенки (препятствия) и остановится. Путем просвечивания коробки рентгеном было выяснено расположение стенок в лабиринте.

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

Во входном файле в первой строке содержатся два целых числа `N` и `M`, разделенных пробелом – размеры коробки (`2\ ≤\ N\ ≤\ 100`, `2\ ≤\ M\ ≤\ 100`). Во следующих `N` строках содержится по `M` символов. Символ '#' используется для обозначения стенки (препятствия). Символ '.' (точка) обозначает свободное место. Символ '@' обозначает вход, а символ '$' – выход. Внешние стенки коробки во входном файле не описываются.

В выходной файл вывести последовательность, позволяющую выкатить шарик из лабиринта, обозначая наклоны символами N, S, W, E (соответствие показано на рисунке). Если существует несколько вариантов вывести любой (один) из них. Если вывести шарик из лабиринта невозможно, то программа должна напечатать слово IMPOSSIBLE.

4 4
@#.$
....
.#..
...#

SENE

В банке *** предлагается следующий кредит для покупки товара. Если товар стоимостью `S` покупается в кредит на `N` месяцев, то при его покупке нужно заплатить сумму `S/N`, затем в течении `N-1` месяца нужно платить ежемесячно сумму `S/N`, а по истечении `N` месяцев нужно заплатить накопившиеся проценты за использование кредита, которые рассчитываются следующим образом. За первый месяц процент за использование кредита составит `P*(N-1)*S/N`, за второй – процент на оставшуюся невыплаченной стоимость товара в сумме `P*(N-2)*S/N` плюс проценты на проценты за предыдущий месяц в сумме `P*P*(N-1)*S/N` и так далее.

Напишите программу, вычисляющую сумму последнего платежа.

Во входном файле в первой строке содержатся 3 числа, разделенных пробелом – стоимость покупки `S` (целое, `0\ <\ S\ <\ 10^9`), количество месяцев `N` (целое, `0\ <\ N\ <\ 100`) и число `P` (вещественное, `0\ <\ P\ ≤\ 0.01`).

В выходной файл вывести сумму последнего платежа с точностью `10^{-2}`.

10000 10 0.01

479.39

A ground-to-air radar system uses an antenna that rotates in a horizontal plane with a period of 2 seconds. Whenever the antenna faces an object, its distance from that antenna is measured and displayed on a circular screen as a white dot. The distance from the dot to the centre of the screen is proportional to the horizontal distance from the antenna to the object, and the angle of the line passing through the centre and the dot represents the direction of the object from the antenna. A dot directly above the centre represents an object that is north of the antenna; an object to the right of the centre represents an object to the east, and so on. The antenna rotates clockwise; that is, if it points north (0°) at time `t\ =\ 0.0`, it points east (90°) at `t\ =\ 0.5`, south (180°) at `t\ =\ 1.0`, west (270°) at `t\ =\ 1.5`, north at `t\ =\ 2`, and so on. If the object is directly on top of the radar antenna, it cannot be observed.

There are a number of objects in the sky. Each is moving at a constant velocity, and appears as a dot on the screen that appears in a different position every time the antenna observes it. Your task is to determine where the dot will appear on the screen the next time the antenna observes it, given the previous two observations. If there are several possibilities, you are to find them all.

The input consists of a number of lines, each with four real numbers: `a_1`, `d_1`, `a_2`, `d_2`. `a_1`, `d_1` are the angle (in degrees) and distance (in arbitrary distance units) for the first observation while `a_2`, `d_2` are the angle and distance for the second observation (`0\ ≤\ a_i\ <\ 360`, `0\ <\ d_i\ <\ 1000`).

The output consists of one line per line of input, containing all posible solutions sorted by ascending angle value and then by descending distance value; each solution consists of two real numbers (with two digits after the decimal place) indicating `a_3`, `d_3`, the angle and distance for the next observation.

90.0 100.0 90.0 110.0
90.0 100.0 270.0 10.0
90.0 100.0 180.0 50.0

90.00 120.00
270.00 230.00
199.93 64.96 223.39 130.49

A Factor Replacement System (FRS) transforms an input integer to another integer by applying rules. Each rule specifies how a set of prime factors of the input integer are replaced by a second set of prime factors. Consider these rules:

Rule 1: 150 `→` 49 [Note: 150=2*3*52; 49=72]

Rule 2: 2 `→` 1

Rule 1 specifies that if the integer has one factor of two, one factor of three, and two factors of five, then those factors are removed and replaced with two factors of seven. Using this rule, the integer 450 (=2*32*52) becomes 147 (=3*72), but the integer 44 (=22*11) is unaltered. Rule 2 specifies that a factor of two should be removed from the integer. Thus 147 is unaltered by this rule but 44 becomes 22 with one application of the rule.

The FRS rules are ordered. For a given input, the rules are examined in order to find a match. When a match is found, the rule is applied once and the process begins again with the first rule. An FRS halts when no rules can be applied. In the above example, the FRS terminates on input 450 with output value 147 and on input 44 with output 11.

Given the rules of an FRS and several positive integers, produce the result of applying the FRS to each integer. It is guaranteed that the FRS will halt for each input integer.

Each FRS description begins with a line containing a non-negative integer `n` (`n\ ≤\ 15`), the number of rules. The next `n` lines contain the rules. Each rule consists of two positive integers separated by at least one space; the first integer is the left part of the rule and the second integer is the right part of the rule, as described above. The first integer is greater than the second integer. The next line contains a non-negative integer `k`, the number of input integers. Each of the next `k` lines contains a single integer to be input to the FRS. All numbers used in the input file for rules and FRS input values are 32 bit integers.

Your program must stop processing input when it reaches an FRS in which n is zero.

For each data set, output a line indicating the data set number. For each input integer, output a single line containing the input integer and the final FRS value, as shown in the Sample Output. Leave a blank line after the output from different FRS's.

2
150 49
2 1
2
450
44
2
9 4
3 1
1
27
0

FRS #1:
     450 becomes 147
     44 becomes 11

FRS #2:
     27 becomes 4