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

Заяц решил построить себе новую избушку на одной из полян в лесу. Всего в лесу `N` полян, связанных между собой `K` тропинками разной длины. Между двумя полянами проложено не более одной тропинки. Тропинки не пересекаются между собой, так как прокладывались с использованием переходных мостов и подземных переходов. На полянах `A` и `B` уже построили себе домики Волк и Лиса, а Зайцу, естественно, хочется жить как можно дальше от них. Требуется выбрать полянку для строительства избушки, чтобы величина `1/a+1/b` была минимальной, где `a` – наименьшее расстояние по тропинкам от домика Зайца до домика Волка, а `b` – наименьшее расстояние от домика Зайца до домика Лисы. Если нет пути между полянами, то соответствующее слагаемое принимаем равным 0.

Во входном файле в первой строке четыре целых числа через один пробел: `N,\ K,\ A` и `B` – количество полян и тропинок, номера полян с домиками Волка и Лисы `(3≤N≤20,\ 1≤K≤100,\ 1≤A≤N,\ 1≤B≤N)`. Далее следует `K` строк с информацией о тропинках. В каждой строке содержится три целых числа через пробел: номера двух полянок, связанных тропинкой, и длина тропинки (от 1 до 1000).

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

5 4 2 3
2 4 7
4 5 1
1 5 4
1 3 8

1
5

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

Заяц обрубил все ветки, и от дерева остался цилиндр высотой `h` и радиусом `r`. Ограда имеет форму окружности с радиусом `R` и по высоте больше диаметра дерева. Центр дерева находится на расстоянии `b` от центра ограды. Заяц может повалить дерево в любую нужную ему сторону. После падения нижний край поваленного дерева касается (как касательная) окружности основания дерева, как показано на рисунке. Требуется определить, сможет ли Заяц повалить спиленное дерево, не повредив ограду.

Во входном файле в первой строке четыре целых числа через один пробел: `R`, `r`, `h` и `b` (`1\ ≤\ r\ ≤\ r+b\ <\ R\ ≤\ 100`, `1\ ≤\ h\ ≤\ 1000`).

В выходной файл вывести слово YES, если существует направление падения дерева, при котором ограда останется неповрежденной, и NO в противном случае.

90 3 50 10

YES

Горную вершину можно увидеть на фоне неба, если только она не скрывается за другой горой или ее контур не скрыт на фоне другой горы. Предположим, что склоны всех гор имеют наклон в `45°`, и известны координаты и высоты вершин всех гор. Требуется определить количество видимых горных вершин.

Во входном файле в первой строке целое число `N` (`1\ ≤\ N\ ≤\ 10\ 000`). Далее идет `N` строк, по два целых числа через пробел в каждой строке: координата `x_i` вершины (`0\ ≤\ x_i\ ≤\ 30\ 000`) и ее высота `y_i` (`1\ ≤\ y_i\ ≤\ 10\ 000`), последовательность вершин является упорядоченной по возрастанию координаты `x`: `x_1\ ≤\ x_2\ ≤\ …\ ≤\ x_N`.

В выходной файл вывести количество видимых вершин.

4
6 5
12 3
16 9
21 4

2

Краткое содержание фильма: для решающей битвы с силами зла были выбраны пять самых лучших бойцов Земли. Со стороны сил зла также будут сражаться пять бойцов. Каждый из бойцов сражается только один раз и только с одним противником. Чтобы Земля не была порабощена, каждый из бойцов Земли должен победить своего противника, а матч должен закончиться со счетом 5:0 в пользу Земли. Для каждой из возможных пар соперников известна вероятность `p_{ij}` победы `i`-го бойца Земли над `j`-ым бойцом сил зла. Требуется подобрать пары бойцов таким образом, чтобы вероятность счета 5:0 (т.е. `Πp_{ij}`) была максимальной.

Во входном файле пять строк по пять чисел (с точностью 3 разряда после запятой) в каждой строке – вероятности победы `p_{ij}\ (0\ <\ p_{ij}\ ≤\ 1)` для каждой пары бойцов, сначала строка с вероятностями для первого бойца Земли, затем для второго и т.д.

В выходной файл вывести пять целых чисел: номера противников `j_k` для каждого `k`-го бойца Земли, сначала номер противника для первого бойца, затем для второго и т.д. Если существует несколько вариантов, максимизирующих вероятность общей победы, вывести один (любой) из них.

0.500 0.544 0.595 0.600 0.550
0.800 0.001 0.050 1.000 0.500
0.700 0.020 0.021 0.456 0.906
0.323 0.345 0.930 0.456 0.455
0.300 1.000 1.000 0.900 0.800

1 4 5 3 2

Дана последовательность из `N` целых чисел. Найти в этой последовательности непрерывную подпоследовательность максимальной длины, сумма элементов которой равна 0.

Во входном файле в первой строке целое число `N` (`1\ ≤\ N\ ≤\ 1000`). Далее идет `N` строк с элементами последовательности, в каждой строке одно целое число от –100 до 100.

В выходной файл вывести длину найденной подпоследовательности и номер элемента, с которого эта подпоследовательность начинается. Если существует несколько таких подпоследовательностей, то вывести информацию о первой из них. Если такой подпоследовательности нет, то вывести 0 0 (два нуля).

4
1
-1
0
-1

3 1