НОВ БЪЛГАРСКИ УНИВЕРСИТЕТ
Състезание_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 |