«Волшебные игральные кубики»
Представьте себе, что у меня есть 3 кубика. Обычные шестигранные кубики, на каждой грани которых написаны некоторые числа. Я предлагаю своему партнеру выбрать любой из этих кубиков, который ему больше понравился, а сам беру себе другой кубик из двух оставшихся. Далее мы начинаем играть: каждый бросает свой кубик, и выигрывает тот, на чьем кубике выпадет большее число. Оказывается, что при большом числе бросаний в среднем я буду в выигрыше, то есть я буду чаще выигрывать у партнера. Даже если партнер поменяет кубик, например, возьмет кубик, которым играл я, то он все равно будет проигрывать, если я воспользуюсь правом выбрать себе кубик из двух оставшихся.
Может ли такое быть? Оказывается, может. Весь секрет в числах, которые расставлены на гранях кубиков.
Пусть на гранях трех кубиков расставлены числа так:
первый кубик - 1, 1, 4, 4, 7, 7,
второй кубик – 2, 2, 5, 5, 5, 5,
третий кубик – 3, 3, 3, 3, 6, 6.
Нетрудно проверить, что второй кубик будет выигрывать у первого в среднем в пяти случаях из девяти, а проигрывать только в 4-х случаях из 9-и. Третий кубик будет выигрывать у второго также в 5-и случаях из 9-и. А первый будет выигрывать у третьего также в 5-и случаях из 9-и. (Правильнее сказать: в 20-и случаях из 36-и, так как вариантов выпадения граней двух кубиков равно 6х6. Но это то же самое, так как дроби можно сокращать.)
Ваша задача заключается в том, чтобы, используя наименьшее количество различных чисел, найти их расстановку (конечно, с повторениями) на гранях трех кубиков такую, чтобы кубики обладали описанным выше «волшебным» свойством.
Исходные данные. Входных данных нет.
Результат. Предположим, что невозможно найти указанную расстановку чисел, используя меньше 7-и различных чисел, тогда результат может быть представлен одной из возможных найденных расстановок в следующем виде:
(1, 1, 4, 4, 7, 7) <
(2, 2, 5, 5, 5, 5) <
(3, 3, 3, 3, 6, 6) <
(Здесь знак < или > должен указывать хуже или лучше кубик следующего кубика по циклу).
Известно, что с меньшим количеством различных чисел такие расстановки существуют.
«Роман в томах»
Необходимо издать роман, состоящий из N глав, в M томах ( 1≤ M ≤ N ). Известно число страниц в каждой из N глав. Каждая глава должна быть целиком помещена в одном из томов (делить главу между томами нельзя). Главы в томах должны идти строго в заданном порядке (изменять порядок глав нельзя).
Требуется разместить главы в M томах так, чтобы самый толстый том имел наименьшее число страниц из возможных.
Исходные данные.
В первой строке входного файла (стандартный ввод) задано через пробел два числа N и M.
Во второй строке задано N чисел: a1, a2, . . . , aN (разделены пробелами), где ai - число страниц в i – ой главе.
Результат.
Выдать M чисел: b1, b2, . . . , bM (через запятую), где bk - число страниц в k – ом томе.
Пример 1. Для следующих исходных данных:
15 2
10 15 20 10 15 20 10 15 20 10 15 20 10 15 20
результат должен быть таким:
115, 110
Пример 2. Для следующих исходных данных:
9 4
10 10 10 10 100 10 10 10 10
результат может быть таким:
40, 100, 20, 20
«Упрощенный Японский кроссворд
Рассмотрим задачу, известную как «японский кроссворд» в упрощенной форме.
Задан клетчатый прямоугольник размера N*M (N – число строк, M – число столбцов). Некоторые его клетки закрашены в черный цвет (пример на рис.).
3 | 4 | 5 | 6 | 7 | 6 | 5 | 3 | 1 | |
1 | |||||||||
3 | |||||||||
5 | |||||||||
7 | |||||||||
9 | |||||||||
8 | |||||||||
7 |
Рис.
Подсчитаем для каждой строки и для каждого столбца число закрашенных клеток. Получим набор чисел для строк и набор чисел для столбцов. (Эти числа показаны на рис. слева от прямоугольника для строк и сверху – для столбцов.)
Задача состоит в том, чтобы по этим наборам чисел восстановить фигуру, изображенную в прямоугольнике закрашенными клетками.
Упрощение задачи в нашем случае заключается в том, что мы будем рассматривать только такие фигуры, у которых в каждой строке и в каждом столбце закрашенные клетки идут подряд, без разрывов. (Фигура на рис. удовлетворяет этому условию.)
Исходные данные.
В первой строке входного файла (стандартный ввод) задано через пробел два числа N и M.
Во второй строке задано N чисел: a1, a2, . . . , aN, где ai - число закрашенных подряд клеток в i – ой строке и 0 ≤ ai ≤ M.
В третьей строке задано M чисел: b1, b2, . . . , bM, где bk - число закрашенных подряд клеток в k – ом столбце и 0 ≤ bk ≤ N.
Результат. Распечатать в текстовом режиме прямоугольник размера N*M в рамке с изображением найденной фигуры, при помощи символа █ (код 219) для закрашенных клеток и пробелов для пустых клеток прямоугольника. (Рамку можно задать любыми символами – звездочками, черточками).
Если решений несколько, достаточно вывести одно, удовлетворяющее условию задачи. Если решений не существует, вывести сообщение: DOES NOT EXIST.
Пример 1. Для следующих исходных данных:
7 9
1
результат может быть таким:
╔═════════╗
║ █ ║
║ ███ ║
║ █████ ║
║ ███████ ║
║█████████║
║████████ ║
║███████ ║
╚═════════╝
