Версия для копирования в MS Word
PDF-версии: горизонтальная · вертикальная · крупный шрифт · с большим полем
РЕШУ ЕГЭ — информатика
Задания
i

Дана по­сле­до­ва­тель­ность N целых по­ло­жи­тель­ных чисел. Рас­смат­ри­ва­ют­ся все пары эле­мен­тов по­сле­до­ва­тель­но­сти, на­хо­дя­щих­ся на рас­сто­я­нии не мень­ше 6 (раз­ни­ца в ин­дек­сах эле­мен­тов долж­на быть 6 или более). Не­об­хо­ди­мо опре­де­лить ко­ли­че­ство пар, раз­ность чисел в ко­то­рых крат­на 3.

Опи­са­ние вход­ных и вы­ход­ных дан­ных.

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (6 ≤ N ≤ 1000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10 000

При­мер вход­ных дан­ных:

8

2

6

5

4

6

7

9

8

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

1

По­яс­не­ние. Из вось­ми чисел можно со­ста­вить три пары, удо­вле­тво­ря­ю­щие усло­вию. Это будут эле­мен­ты с ин­дек­са­ми 1 и 7, 1 и 8, 2 и 8. Для за­дан­но­го на­бо­ра чисел по­лу­ча­ем пары (2, 9), (2, 8), (6, 8). Раз­но­сти чисел в этих парах равны 7, 6, 2. Одна из этих раз­но­стей крат­на 3.

На­пи­ши­те эф­фек­тив­ную по вре­ме­ни и по па­мя­ти про­грам­му для ре­ше­ния этой за­да­чи.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если при уве­ли­че­нии ко­ли­че­ства ис­ход­ных чисел N в k раз время ра­бо­ты про­грам­мы уве­ли­чи­ва­ет­ся не более чем в k раз.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если па­мять, не­об­хо­ди­мая для хра­не­ния всех пе­ре­мен­ных про­грам­мы, не пре­вы­ша­ет 1 ки­ло­бай­та и не уве­ли­чи­ва­ет­ся с ро­стом N.

Мак­си­маль­ная оцен­ка за пра­виль­ную (не со­дер­жа­щую син­так­си­че­ских оши­бок и да­ю­щую пра­виль­ный ответ при любых до­пу­сти­мых вход­ных дан­ных) про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти,  — 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную толь­ко по вре­ме­ни или толь­ко по па­мя­ти,  — 3 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, не удо­вле­тво­ря­ю­щую тре­бо­ва­ни­ям эф­фек­тив­но­сти,  — 2 балла.

Вы мо­же­те сдать одну или две про­грам­мы ре­ше­ния за­да­чи. Если Вы сда­ди­те две про­грам­мы, каж­дая из них будет оце­ни­вать­ся не­за­ви­си­мо от дру­гой, ито­го­вой ста­нет бо́льшая из двух оце­нок.

Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния. Ука­жи­те ис­поль­зо­ван­ный язык про­грам­ми­ро­ва­ния и его вер­сию.