Подразделы

Другие разделы

Дата и время

15/10/2024 12:10:51

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

printЗадачи региональной олимпиады по информатике 1998

1. Кубики

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Маленький Метью очень любил играть в кубики. Он делал столбики из кубиков и ставил эти столбики на квадратный столик (не случайным образом, а в клетки, если представить столик разлинованным на клетки по размерам кубиков). Из-за маленького роста Метью мог построить столбики не более 8 кубиков. На рисунке можно увидеть одно из его творений на столике размером 4x4.
10624.gif
Понравившиеся ему строения он зарисовывал. Но так как он не умел рисовать 3D-изображения, то ограничивался видом спереди и видом справа. Метью думал, что этой информации достаточно, чтобы построить это строение снова (но он никогда не пытался сделать это).
10621.gif
Вид спереди
10622.gif
Вид справа
Через несколько лет, рассматривая рисунки, он понял, что можно построить более чем одно строение с тем же самым видом спереди и справа.
Метью обнаружил, что существует некоторое "минимальное" из всех возможных строение с минимальным числом кубиков `N` и "максимальное" с числом кубиков `M`. Для показанного примера "минимальное" строение содержит `N=7` кубиков, а "максимальное" – `M=17` кубиков.
10623.gif
Минимальное строение
10620.gif
Максимальное строение
Напишите программу, которая позволяет вычислить максимальное (`M`) и минимальное (`N`) число кубиков для строения, задаваемого видами спереди и справа.
Входной файл содержит в первой строке размеры столика `K` (`1\ ≤\ K\ ≤\ 8`), во второй строке – `K` чисел через пробел: высота столбиков (от 0 до 8) на виде спереди, в третьей строке также `K` чисел – высота столбиков на виде справа. Известно, что по этим исходным данным можно построить как минимум одно строение.
В выходной файл вывести числа `N` и `M` через пробел.

Пример ввода

4
2 0 3 1
1 1 2 3

Пример вывода

7 17
Источник: ACM ICPC Western European RC, 1995

2. Рыба!

Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дан набор косточек домино. Требуется определить, можно ли составить из всех косточек набора непрерывную цепочку по обычным правилам игры в домино (т.е. стыкуя стороны с одинаковым числом очков).
Входной файл содержит в первой строке число косточек в наборе `N` (`1\ ≤\ N\ ≤\ 100`), далее `N` строк с парами чисел `i` `j` (`0\ ≤\ i,\ j\ ≤\ 6`), соответствующих косточке домино.
В выходном файле должен быть ответ YES или NO.

Пример ввода 1

3
1 2
3 4
2 3

Пример вывода 1

YES

Пример ввода 2

2
1 2
3 4

Пример вывода 2

NO

3. Ход конем

Ограничения: время – 500ms/1000ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На доске 8x8 некоторые клетки произвольным образом покрашены в черный цвет (кроме верхнего левого и правого нижнего угла доски). Требуется определить имеется ли путь для шахматного коня из верхнего левого в правый нижний угол доски, не проходящий по черным клеткам, и минимальное количество ходов, требующееся для этого.
Входной файл содержит 8 строк по 8 символов. Белая клетка кодируется символом '.' (точка), а черная – символом '#'.
В выходной файл записывается ответ NO или YES. При положительном ответе кроме того выводится через пробел число ходов.

Пример ввода 1

......##
.....##.
....##..
...##...
..##....
.##.....
##......
#.......

Пример вывода 1

YES 6

Пример ввода 2

.#.#.#.#
#.#.#.#.
.#.#.#.#
#.#.#.#.
.#.#.#.#
#.#.#.#.
.#.#.#.#
#.#.#.#.

Пример вывода 2

NO

4. Карданный вал

Ограничения: время – 200ms/500ms, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Напишите программу для определения объема отливки. Отливка имеет форма прямой призмы с высотой `h`, а форма основания определяется двумя непересекающимися ломаными линиями.
Входной файл содержит в первой строке высоту `h` (`0\ <\ h\ ≤\ 10`), во второй строке – количество отрезков в верхней ломаной `n` (`1\ ≤\ n\ ≤\ 50`), далее следует `n+1` строка с координатами точек верхней ломаной `x_i\ y_i` через пробел. Точки перечислены в порядке возрастания координаты `x_i`, таким образом линия `(x_{i-1}\ y_{i-1})-(x_i\ y_i)` является `i`-м отрезком ломаной (`i=1…n`). Далее идет количество отрезков в нижней ломаной `m` (`1\ ≤\ m\ ≤\ 50`), затем `m+1` строка с координатами точек ломаной `u_i\ v_i` через пробел.
Все координаты и высота `h` целые, не превосходящие по модулю 100, кроме того `x_0=u_0=0` и `x_n=u_m`, `x_{i-1}\ ≤\ x_i`, `u_{i-1}\ ≤\ u_i`.
В выходной файл вывести результат с точностью `10^{-2}`.

Пример ввода

4
2
0 1
5 6
10 1
3
0 -5
2 0
8 0
10 -5

Пример вывода

180.00
loading