Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1206. Factor Replacement System
Простые числа, разложение на множителиМоделирование
Олимпиадные задачи на английском языке
| 02/10/2004 | Личное первенство университета по программированию (6) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
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.
Input
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.
Output
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.
Sample Input
2 150 49 2 1 2 450 44 2 9 4 3 1 1 27 0
Sample Output
FRS #1:
450 becomes 147
44 becomes 11
FRS #2:
27 becomes 4
