НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА
ОБЛАСТЕН КРЪГ, 13 МАРТ 2004 Г.
ТЕМА ЗА ГРУПА A (11-12 клас)

А1. ЛЪЧИ

В равнината са дадени N + 1 точки Ai с координати  xi  и  yi,   i = 0, ..., N, като Ai ≠  A0 при i ≠  0. Разглеждаме само онези от ъглите AiA0Aj, 1  i < j  N, които са остри, прави или тъпи и във вътрешността им няма лъчи от вида A0Ak, k = 1, ..., N.
Напишете програма RAYS.EXE, която подрежда разглежданите ъгли по големина в растящ ред.
Данните се въвеждат от стандартния вход. На първия ред е записано числото N. Следват N + 1 реда, всеки съдържащ поредната двойка координати xi, yi,  i = 0, ..., N, като две цели числа, разделени с интервал. 
На всеки ред на стандартния изход се извежда двойката индекси i и j, съответстваща на поредния по големина ъгъл AiA0Aj. Ако някои от  разглежданите ъгли са равни по големина, първо се извежда лексикографски по-малката двойка индекси.
Ограничения: 3 < N < 2000,  xi и yi са цели числа от интервала [–105, 105].

ПРИМЕР
Вход
4
0 0
1 0
1 1
0 1
-1 0

Изход
1 2
2 3
3 4

A2. ПЕРМУТАЦИИ

Нека a1, a2, a3, ..., an e пермутация на числата от 1 до n. Ако ai < ai+1, казваме, че числата ai и ai+1 образуват “издигане”. Например в пермутацията  6, 7, 2, 4, 1, 3, 5 има точно 4 издигания (6 < 7, 2 < 4, 1 < 3 и 3 < 5). 
Напишете програма PERM.EXE, която намира броя на пермутациите на числата от 1 до n, които имат точно k издигания. 
От стандартния вход се въвеждат числата n и k (записани на един ред и разделени с интервал). На стандартния изход се извежда търсеното число. 
Ограничения: 2  n  15, 0  k  n.  

ПРИМЕР
Вход
3 1

Изход
4

A3.  БЪРЗО ПРИДВИЖВАНЕ

В големите градове бързината на придвижването не винаги зависи само от дължината на маршрута, който трябва да бъде изминат, а също и от натовареността на движението и пропускливостта на отделните улици. Пропускливостта се определя от ширината на улицата, от качеството на настилката, от нейната обезопасеност и т.н. и, в края на краищата, се измерва с някакво цяло положително число, което можем да наричаме ширина. Колкото по-голяма е ширината, толкова по-голяма е пропускливостта на улицата. Ширината на един маршрут в града е равна на ширината на тази улица по маршрута, която има най-малка ширина. 
Напишете програма FAST.EXE, която в даден град с N кръстовища (номерирани с числата от 1 до N) и M улици, всяка от които свързва две от кръстовищата, намира маршрут с най-голяма ширина от кръстовището с номер 1 до кръстовището с номер N, ако такъв маршрут съществува.
Входните данни ще бъдат зададени на стандартния вход. На първия ред, разделени с един интервал ще бъдат числата N и M, 2  N  10000, 1  M  100000. Всеки от следващите M реда ще съдържа по три цели положителни числа  I,  J  и  W,   1  W  65000, разделени с по един интервал, които означават, че кръстовищата с номера I и J са свързани с улица с ширина W. 
Програмата трябва да изведе на стандартния изход най-голямата ширина на маршрут от кръстовището с номер 1 до кръстовището с номер N, при условие, че такива маршрути съществуват. В противен случай програмата трябва да изведе на стандартния изход числото 0.

ПРИМЕР 1					ПРИМЕР 2
Вход						Вход
5 6						6 6
1 2 1					1 3 4
1 3 3					1 4 3
1 4 9					3 4 5
2 5 10					2 6 6
3 5 4					2 5 8
4 5 2					5 6 7

Изход 						Изход
3						0