НОВ БЪЛГАРСКИ УНИВЕРСИТЕТ
Състезание_1
INF295
16.12.2003
Задача Б. Тристъпална редица
Методът "бързо сортиране" на масив от числа се основава
на алгоритъма за деление на масива на 2 дяла, като всеки елемент от първия
дял е по-малък от всеки елемент от втория дял. Делението се прави относно
даден елемент от масива и този елемент, заедно с други, равни на него,
образуват трети дял, който се намира между първите два. Задачата е да се
установи дали даден масив от числа е разделен на дялове. Ето и точната
формулировка:
Една редица от цели числа a1,
a2,
..., an се нарича "тристъпална", ако може да се намери
елемент ak, 1< k < n, който да дели редицата
на 3 части:
a1, a2, ..., ap;
ap+1, ap+2,
..., aq;
aq+1, aq+2,
..., an;
като 1 < p < q < n и
ai< ak за i = 1,...,
p;
ai = ak за i = p+1, ...,
q;
ai > ak за i = q+1, ...,
n.
Да се напише програма 3steps.exe за
определяне дали дадена редица е "тристъпална". Елементите на редицата са
цели положителни числа, не по-големи от 10000 и не повече от 1000.
ВХОД - файл 3steps.inp
За всяка редица на отделен ред се задават броят
на членовете на редицата и след това самите членове. Входният файл съдържа
много редици и завършва с дължина на редица 0.
ИЗХОД - файл 3steps.out
За всяка редица се извеждат числата p и q.
Ако съществуват няколко двойки такива числа, извежда се онази двойка, за
която числото n - p - q е най-малко неотрицателно число (т.е. масивът
е разделен на две "максимално равни" части). Ако редицата не е "тристъпална"
да се счита, че p = -1 и q = -1.
Пример:
10
1 1 1 1 2 2 4 3 3 3
11
1 1 2 3 5 8 13 21 34 45 79
4
10 2 3 5
0
Решение на примера:
4 6
5 6
-1 -1