НОВ  БЪЛГАРСКИ  УНИВЕРСИТЕТ

Състезание_2                 INF295             11.01.2005

    Задача Б. Тристъпална редица

    Методът "бързо сортиране" на масив от числа се основава на алгоритъма за деление на масива на 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.
    Да се напише програма b.exe за определяне дали дадена редица е "тристъпална". Елементите на редицата са цели положителни числа, не по-големи от 10000 и не повече от 1000.

    ВХОД
    За всяка редица на отделен ред се задават броят на членовете на редицата и след това самите членове. Входът съдържа много редици и завършва с дължина на редица 0.

    ИЗХОД
    За всяка редица се извеждат числата 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