Начало
Соревнования
Задачи заочного тура личного первенства 2002
1. Лото
В немецком лото вы должны выбрать 6 чисел из множества {1,2, …, 49}.
Популярная стратегия, чтобы играть в лото – хотя это не увеличивает вашу возможность победы – это выбрать подмножество `S`, содержащее `k` (`k\ >\ 6`) из этих 49 чисел, и затем играть отдельные игры, выбирая числа только из `S`.
Например, для `k\ =\ 8` и `S\ =\ 1,2,3,5,8,13,21,34` имеются 28 возможных игр: [1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], …, [3,5,8,13,21,34].
Вы должны написать программу, которая читается число k и множество `S` и затем печатает все возможные игры, выбирая числа только из `S`.
Ввод
Ввод будет содержать один или большее количество случаев.
Каждый случай состоит из одной строки, содержащей целые числа, отделенные от друг друга пробелами. Первое целое число в строке будет номер `k` (`6\ <\ k\ <\ 13`). Затем `k` целых чисел, определяющие множество `S`, будет следовать в порядке возрастания.
Ввод будет закончен значением нуля (0) для `k`.
Вывод
Для каждого случая, печатайте все возможные игры, каждая игра на отдельной строке.
Числа для каждой игры должны сортироваться в порядке возрастания и отделены из друг друга точно одним пробелом. Игры непосредственно должны сортироваться лексикографически, что означает сортировку по первому номеру сначала, затем второму и так далее, как продемонстрировано в типовом выводе ниже.
Случаи должны быть отделены от друг друга точно одной пустой строкой. Не помещайте пустую строку после последнего случая.
Пример ввода
7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0
Пример вывода
1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7 1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 1 2 3 5 8 13 1 2 3 5 8 21 1 2 3 5 8 34 1 2 3 5 13 21 1 2 3 5 13 34 1 2 3 5 21 34 1 2 3 8 13 21 1 2 3 8 13 34 1 2 3 8 21 34 1 2 3 13 21 34 1 2 5 8 13 21 1 2 5 8 13 34 1 2 5 8 21 34 1 2 5 13 21 34 1 2 8 13 21 34 1 3 5 8 13 21 1 3 5 8 13 34 1 3 5 8 21 34 1 3 5 13 21 34 1 3 8 13 21 34 1 5 8 13 21 34 2 3 5 8 13 21 2 3 5 8 13 34 2 3 5 8 21 34 2 3 5 13 21 34 2 3 8 13 21 34 2 5 8 13 21 34 3 5 8 13 21 34
2. Матричное умножение
Предположим, что вы должны вычислить выражение подобное `A*B*C*D*E`, где `A`, `B`, `C`, `D` и `E` – матрицы. Так как матричное умножение ассоциативно, порядок, в котором умножение выполняются, произволен. Однако, число элементарных умножения, необходимых строго зависит от порядка вычисления, который Вы выбираете.
Например, допустим матрица `A` размером `50\ times\ 10`, `B` – `10\ times\ 20` и `C` – `20\ times\ 5`. Имеются две различных cтратегии, чтобы вычислить `A*B*C`, а именно `(A*B)\ *C` и `A*\ (B*C)`. Первая требует 15000 элементарных умножений, а вторая только 3500.
Вы должны написать программу, которая определяет число элементарных умножений, необходимых для данного порядка вычислений.
Ввод
Ввод состоит из двух частей: списка матриц и списка выражений.
Первая строка ввода содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 26`), представлящее число матриц в первой части. В каждой из следующие n строк содержится одна заглавная буква, определяющая название матрицы, и два целых числа, определяющие число строк и столбцов матрицы.
Вторая часть ввода строго придерживается следующего синтаксиса (данного в расширенной форме Бекуса-Наура):
SecondPart = Line { Line }
Line = Expression
Expression = Matrix | "(" Expression Expression ")"
Matrix = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
Вывод
Для каждого выражения, найденного во второй части ввода, печатайте одну строку, содержащую слово "error", если вычисление выражения ведет к ошибке из-за несоответствия матриц. Иначе печатайте одну строку, содержащую число элементарных умножений, необходимых, чтобы вычислить выражение в порядке, установленном круглыми скобками.
Пример ввода
9 A 50 10 B 10 20 C 20 5 D 30 35 E 35 15 F 15 5 G 5 10 H 10 20 I 20 25 A B C (AA) (AB) (AC) (A(BC)) ((AB)C) (((((DE)F)G)H)I) (D(E(F(G(HI))))) ((D(EF))((GH)I))
Пример вывода
0 0 0 error 10000 error 3500 15000 40500 47500 15125
3. Humble Numbers
A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, … shows the first 20 humble numbers.
Write a program to find and print the nth element in this sequence.
Input Specification
The input consists of one or more test cases. Each test case consists of one integer `n` with `1\ ≤\ n\ ≤\ 5842`. Input is terminated by a value of zero (0) for `n`.
Output Specification
For each test case, print one line saying "The `n`th humble number is number.". Depending on the value of n, the correct suffix "st", "nd", "rd", or "th" for the ordinal number nth has to be used like it is shown in the sample output.
Sample Input
1 2 3 4 11 12 13 21 22 23 100 1000 5842
Sample Output
The 1st humble number is 1. The 2nd humble number is 2. The 3rd humble number is 3. The 4th humble number is 4. The 11th humble number is 12. The 12th humble number is 14. The 13th humble number is 15. The 21st humble number is 28. The 22nd humble number is 30. The 23rd humble number is 32. The 100th humble number is 450. The 1000th humble number is 385875. The 5842nd humble number is 2000000000.
