21 декабря 2013 года.
10 "В" класс, самостоятельная работа

I: Выручка театра

В театре N рядов по M мест в каждом. Даны две матрицы - в первой записаны стоимости билетов. Вторая - сообщает, какие билеты проданы, а какие - нет (1 - соответствующий билет продан, 0 - не продан).

Определите общую выручку от спектакля.

Входные данные. В первой строке заданы числа N и M. Затем задана матрица стоимостей билетов (N строк по M чисел, каждое из чисел от 0 до 10000). После нее идет пустая строка. Далее задана матрица проданных билетов (опять же N строк по M чисел). N и M не превышают 100.

Выходные данные. Выведите общую выручку от продажи билетов.

Ввод Вывод
3 4
1 100 100 1
1 5 5 1
2 2 3 2

1 0 1 1
0 1 1 0
0 0 1 0
115

J: Театр - самые дешевые билеты

В театре N рядов по M мест в каждом. Даны две матрицы - в первой записаны стоимости билетов. Вторая - сообщает, какие билеты проданы, а какие - нет (1 - соответствующий билет продан, 0 - не продан).

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

Входные данные. В первой строке заданы числа N и M. Затем задана матрица стоимостей билетов (N строк по M чисел, каждое из чисел от 0 до 10000). После нее идет пустая строка. Далее задана матрица проданных билетов (опять же N строк по M чисел). N и M не превышают 100.

Выходные данные. Выведите максимальный размер компании. Если все самые дешевые билеты уже проданы, то размер компании равен 0.

Ввод Вывод
3 4
1 100 100 1
1 5 5 1
2 2 3 2

1 0 1 1
0 1 1 0
0 0 1 0
2
3 4
1 100 100 1
1 5 5 1
2 2 3 2

1 0 0 1
1 1 1 1
0 0 1 0
0

K: Хождение за золотом - 1

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

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

Входные данные. Вводится план комнаты. Сначала вводится количество строк N, затем - количество столбцов M (1≤N≤20,1≤M≤20). Затем записано N строк по M чисел в каждой - количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число X - сколько клеток обошел мудрец. Далее записаны координаты этих клеток (координаты клетки - это два числа: первое определяет номер строки, второе - номер столбца, верхняя левая клетка на плане имеет координаты (1,1), правая нижняя - (N,M)). Общее число клеток в пути мудреца не превышает 10000.

Выходные данные. Выведите количество килограммов золота, которое собрал мудрец.

Ввод Вывод
3 4
1 2 3 4
5 6 7 8
9 10 11 12
5
1 1
2 1
2 2
2 3
1 3
22
3 4
1 2 3 4
5 6 7 8
9 10 11 12
9
1 1
2 1
2 2
2 3
1 3
1 2
1 1
1 2
2 2
24

L: Хождение за золотом - 2

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

Входные данные. Вводится план комнаты. Сначала вводится количество строк N, затем - количество столбцов M (1≤N≤20,1≤M≤20). Затем записано N строк по M чисел в каждой - количество килограммов золота, которое лежит в данной клетке (число от 0 до 50). Далее записано число X (от 1 до 10000) - сколько клеток обошел мудрец.

Известно, что мудрец начал с клетки с координатами (1,1). Далее в строчку записано X-1 число: куда перемещался мудрец:

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

Выходные данные. Выведите количество килограммов золота, которое собрал мудрец.

Ввод Вывод
3 4
1 2 3 4
5 6 7 8
9 10 11 12
9
4 1 1 2 3 3 1 4
24

M: Страны и города

Дан список стран и городов каждой страны. Затем даны названия городов. Для каждого города укажите, в какой стране он находится.

Программа получает на вход количество стран N. Далее идет N строк, каждая строка начинается с названия страны, затем идут названия городов этой страны. В следующей строке записано число M, далее идут M запросов - названия каких-то M городов, перечисленных выше.

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

Ввод Вывод
2
Russia Moscow Petersburg Novgorod Kaluga
Ukraine Kiev Donetsk Odessa
3
Odessa
Moscow
Novgorod
Ukraine
Russia
Russia

A: Количество равных соседей

Даны числа, которые вводятся по одному в строке до тех пор, пока не введут 0.
Посчитайте количество пар соседних чисел, которые равны между собой.

Ввод Вывод
1 
2 
2 
3 
2 
2 
2
0
3
1 
2 
2 
3 
3 
3 
2 
2 
2
0
5

D: Простое с максимальным произведением цифр

Даны числа A и B. На отрезке от A до B (включая A и B) найдите простое число, произведение цифр которого максимально. Если таких чисел несколько, выведите наименьшее из них. Если на отрезке нет ни одного простого числа, выведите 0.

Числа A и B записаны каждое в отдельной строке.

Совет: напишите две функции: функцию, проверяющую число на простоту, и функцию, вычисляющую произведение цифр числа.

Ограничения: 2 ≤ A ≤ B ≤ 10 000 000, при этом B − A ≤ 1000.
Ввод Вывод
10
30
29
15
16
0

G: Рекурсивная генерация последовательностей**

Напечатайте все последовательности длины N, на каждом месте в последовательности может стоять любое число от 1 до K, но нигде подряд не стоит двух одинаковых чисел.

На вход программе задается два числа N и K.

Программа должна напечатать все такие последовательности в лексикографическом порядке. Каждая последовательность должна быть напечатана на отдельной строке. Числа в последовательности должны разделяться пробелами.

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

Ввод Вывод
4
3
1 2 1 2
1 2 1 3
1 2 3 1
1 2 3 2
1 3 1 2
1 3 1 3
1 3 2 1
1 3 2 3
2 1 2 1
2 1 2 3
2 1 3 1
2 1 3 2
2 3 1 2
2 3 1 3
2 3 2 1
2 3 2 3
3 1 2 1
3 1 2 3
3 1 3 1
3 1 3 2
3 2 1 2
3 2 1 3
3 2 3 1
3 2 3 2