Задачи личного первенства областной олимпиады школьников по информатике 2005

Некто задумал два целых числа от 0 до 1000 и сообщил вам их сумму и их произведение. Напишите программу, угадывающую задуманные числа.

В первой строке входного файла содержится два целых числа, разделенных пробелом – сумма задуманных чисел `S` (`0\ ≤\ S\ ≤\ 2000`) и произведение задуманных чисел `P` (`0\ ≤\ P\ ≤\ 1000000`).

В выходной файл вывести два задуманных целых числа через пробел в порядке возрастания.

22 120

10 12

Магнитный компас показывает курс корабля, но только с точностью до градуса. Качка корабля приводит к тому, что стрелка компаса перепрыгивает с одного деления на другое. Для повышения точности определения курса корабля показания компаса можно снять несколько раз за некоторый интервал времени, а затем найти их среднее арифметическое. Гарантируется, что даже во время шторма стрелка компаса не отклоняется более чем на 20 градусов от своего среднего положения. Напишите программу, вычисляющую на основании показаний компаса усредненный курс корабля.

В первой строке входного файла содержится целое число `N` (`1\ ≤\ N\ ≤\ 200`) – количество показаний компаса. В второй строке – `N` целых чисел в диапазоне от 0 до 359, разделенных пробелами – углы для курса корабля, измеренные с помощью компаса в некоторые моменты времени.

В первой строке выходного файла вывести два целых числа через пробел – градусы (от 0 до 359) и минуты (от 0 до 59) для угла, полученного в результате усреднения всех показаний компаса. Результат усреднения должен быть выведен с точностью до минуты.

7
95 97 97 99 96 95 94

96 9

Для этой игры используется обычная шахматная доска `8\ times\ 8`. Играют двое. У каждого игрока от 1 до 12 фишек, у одного черного, а у другого белого цвета. Фишка игрока может ходить по вертикали или горизонтали на расстояние, равное числу фишек обоих игроков, стоящих на вертикали или горизонтали, по которой производится ход, включая фишку, делающую ход. Фишка при ходе может прыгать через фишки своего цвета, но не через фишки другого цвета. Приземляться фишка должна на свободное поле или на поле, занятое фишкой другого цвета (в этом случае фишка противника снимается с доски). Напишите программу, подсчитывающую число вариантов хода у каждого игрока в заданной позиции.

Во входном файле содержится 8 строк по 8 символов 'X', 'O' или '.'. Символом '.' (точка) обозначается свободная клетка, 'X' – клетка, занятая черной фишкой, а 'O' – клетка, занятая белой фишкой.

В первой строке выходного файла вывести два целых числа через пробел – количество вариантов хода у игрока, владеющего белыми фишками, и у игрока, владеющего черными фишками.

O.......
O......X
O.....XX
O....XXX
..O..XXX
........
..O..XXX
........

9 16

Наконец пять конкурсов завершились, и перед победителем популярного телевизионного шоу заветные двери, ведущие в сокровищницу. Перед сокровищницей расположено `N` длинных коридоров, все коридоры и сокровищница соединены между собой `M` дверьми, как показано на рисунке. Игрок находится в первом коридоре. Чтобы добежать до сокровищницы, у него всего `K` секунд. Если он не успеет за отведенное время добежать до нее, то он ничего не получает. Отчет времени начнется, когда он выберет одну из `M` дверей и станет перед ней. За секунду он может либо открыть дверь и перейти в следующий коридор, либо перейти к соседней двери в том же коридоре, слева или справа от текущей. Чтобы добраться до выигрыша в 1000000$, игрок должен пройти через `N` дверей. Но проблема не в том, чтобы открыть эти двери – замков на них нет, а в том, что на каждой двери написано некоторое число, и сумма чисел на дверях, через которые прошел игрок, будет вычтена из его выигрыша. Естественно, игрок хочет максимизировать свой выигрыш, и в этом ему должна помочь ваша программа.

В первой строке входного файла содержится три целых числа, разделенных пробелами – количество коридоров `N` (`1\ ≤\ N\ ≤\ 50`), количество дверей `M` (`1\ ≤\ M\ ≤\ 50`) и лимит времени игрока `K` (`N\ ≤\ K\ ≤\ M*(N-1)+1`). Далее следует `N` строк, в каждой строке `M` целых чисел в диапазоне от 1 до `1000000/N`, разделенных пробелами – числа на дверях. `j`-е число в `(i+1)`-й строке входного файла соответствует числу, написанному на `j`-й двери в `i`-м коридоре.

В первой строке выходного файла вывести `N` целых чисел, разделенных пробелами – номера дверей в порядке их прохождения игроком. Время прохождения не должно превышать `K` секунд, а сумма чисел на пройденных дверях минимальна.

4 5 6
250000 100000 150000 200000 200000
100000 150000 250000 100000 250000
150000 250000 100000 100000 1
250000 100000 250000 100000 100000

3 4 5 5

На листе бумаги выполнено несколько разрезов. Отрезки-разрезы имеют наклон только 0, 45, 90 и 135 градусов к оси ординат. Таким образом в одной точке могут пересекаться не более 4 отрезков. Отрезки, расположенные на одной прямой, не пересекаются. Разрезы не доходят до краев бумаги. Напишите программу, определяющую на сколько отдельных кусков был разрезан лист бумаги.

В первой строке входного файла содержится целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество разрезов. Далее следует `N` строк, в каждой строке четыре целых числа X1, Y1, X2, Y2 в диапазоне от 1 до 999, разделенных пробелами – координаты двух концов разреза. Координаты левого нижнего угла бумаги `(0,\ 0)`, а правого верхнего – `(1000,\ 1000)`.

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

4
100 300 800 300
100 200 700 800
400 300 400 900
600 700 600 100

3