Го­ноч­ная трас­са со­сто­ит из двух ос­нов­ных дорог и не­сколь­ких пе­ре­ез­дов, поз­во­ля­ю­щих пе­рей­ти с одной до­ро­ги на дру­гую. На всех участ­ках, вклю­чая пе­ре­ез­ды, дви­же­ние раз­ре­ше­но толь­ко в одну сто­ро­ну, по­это­му пе­ре­езд воз­мо­жен толь­ко с до­ро­ги A на до­ро­гу B. Гон­щик стар­ту­ет в точке A₀ и дол­жен фи­ни­ши­ро­вать в точке B_N. Он знает, за какое время смо­жет прой­ти каж­дый уча­сток пути по каж­дой до­ро­ге, то есть время про­хож­де­ния участ­ков A₀A₁, A₁A₂, …, A_N-1A_N, B₀B₁, B₁B₂, …, B_N-1BN. Время про­хож­де­ния всех пе­ре­ез­дов A₀B₀, A₁B₁, …, A_NB_N оди­на­ко­во и из­вест­но гон­щи­ку. Не­об­хо­ди­мо опре­де­лить, за какое ми­ни­маль­ное время гон­щик смо­жет прой­ти трас­су.

Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.

За­да­ние А. Име­ет­ся 10 пунк­тов А_i и 10 пунк­тов В_i, время про­хож­де­ния всех пе­ре­ез­дов из­вест­но. На­пи­ши­те про­грам­му для ре­ше­ния этой за­да­чи. В этом ва­ри­ан­те за­да­ния оце­ни­ва­ет­ся толь­ко пра­виль­ность про­грам­мы, время ра­бо­ты и раз­мер ис­поль­зо­ван­ной па­мя­ти не имеют зна­че­ния.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

За­да­ние Б. Име­ет­ся набор дан­ных о пунк­тах A_i и B_i. На­пи­ши­те про­грам­му для ре­ше­ния этой за­да­чи.

По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

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

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

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

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

Вход­ные дан­ные

В пер­вой стро­ке задаётся ко­ли­че­ство участ­ков трас­сы N. Во вто­рой стро­ке задаётся целое число t  — время (в се­кун­дах) про­хож­де­ния каж­до­го из пе­ре­ез­дов A₀B₀, A₁B₁, …, A_NB_N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но два целых числа ai и bi, за­да­ю­щих время (в се­кун­дах) про­хож­де­ния оче­ред­но­го участ­ка на каж­дой из дорог. В пер­вой из этих строк ука­зы­ва­ет­ся время про­хож­де­ния участ­ков A₀A₁ и B₀B₁, во вто­рой  — A₁A₂ и B₁B₂ и т. д.

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

3

20

320 150

200 440

300 210

Вы­ход­ные дан­ные

Про­грам­ма долж­на на­пе­ча­тать одно целое число: ми­ни­маль­но воз­мож­ное время про­хож­де­ния трас­сы (в се­кун­дах).

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

750

Ав­то­мо­биль, участ­ву­ю­щий в гонке, может быть осна­щен двумя раз­ны­ми ти­па­ми колес (A и B). Вдоль трас­сы рас­по­ло­же­ны стан­ции, на ко­то­рых можно вы­пол­нить за­ме­ну колес A на B, эта опе­ра­ция за­ни­ма­ет t се­кунд. За­ме­на колес B на A в ходе гонки тех­ни­че­ски не­воз­мож­на. На старт можно выйти с любым ком­плек­том. Для каж­до­го участ­ка между стан­ци­я­ми из­вест­но, за какое время можно прой­ти этот уча­сток с каж­дым из ком­плек­тов колес. Не­об­хо­ди­мо опре­де­лить, за какое ми­ни­маль­ное время можно прой­ти всю трас­су.

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

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

Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.

За­да­ние А. Име­ют­ся дан­ные о вре­ме­ни про­хож­де­ния участ­ков трас­сы с раз­лич­ны­ми ти­па­ми колёс. Всего пунк­тов 10 штук. На­пи­ши­те про­грам­му для ре­ше­ния этой за­да­чи. В этом ва­ри­ан­те за­да­ния оце­ни­ва­ет­ся толь­ко пра­виль­ность про­грам­мы, время ра­бо­ты и раз­мер ис­поль­зо­ван­ной па­мя­ти не имеют зна­че­ния.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

За­да­ние Б. Име­ют­ся дан­ные о вре­ме­ни про­хож­де­ния участ­ков трас­сы с раз­лич­ны­ми ти­па­ми колёс. Пунк­тов может быть очень много. По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

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

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

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

Вход­ные дан­ные

В пер­вой стро­ке за­да­ет­ся ко­ли­че­ство участ­ков трас­сы N. Во вто­рой стро­ке за­да­ет­ся целое число t  — время (в се­кун­дах) на за­ме­ну колес A на B. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но два целых числа a_i и b_i, за­да­ю­щих время (в се­кун­дах) про­хож­де­ния оче­ред­но­го участ­ка с каж­дым из ком­плек­тов. В пер­вой из этих строк ука­зы­ва­ет­ся время про­хож­де­ния участ­ка от стар­та до пер­вой стан­ции, во вто­рой – от пер­вой стан­ции до вто­рой и т. д.

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

3

10

130 210

320 140

100 120

Вы­ход­ные дан­ные

Про­грам­ма долж­на на­пе­ча­тать одно целое число: ми­ни­маль­но воз­мож­ное время про­хож­де­ния трас­сы (в се­кун­дах).

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

400

На вход про­грам­ме по­да­ет­ся по­сле­до­ва­тель­ность целых чисел. В пер­вой стро­ке со­об­ща­ет­ся ко­ли­че­ство чисел N, во вто­рой стро­ке идут сами числа.

Тре­бу­ет­ся на­пи­сать про­грам­му, ко­то­рая будет вы­во­дить на экран числа в сле­ду­ю­щем по­ряд­ке:

сна­ча­ла от­ри­ца­тель­ные числа, потом по­ло­жи­тель­ные. При этом долж­но со­хра­нять­ся ис­ход­ное вза­им­ное по­ло­же­ние, как среди от­ри­ца­тель­ных, так и среди по­ло­жи­тель­ных чисел

Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.

За­да­ние А. Име­ет­ся набор дан­ных, со­сто­я­щий из N = 20 пар целых чисел.

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

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

За­да­ние Б. Име­ет­ся набор дан­ных, со­сто­я­щий из почти про­из­воль­но­го ко­ли­че­ства N целых чисел, чисел не может быть боль­ше ста, N < 100. На­пи­ши­те про­грам­му для ре­ше­ния такой за­да­чи.

По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

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

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

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

На вход даны пары чисел. Нужно вы­брать из каж­дой пары по од­но­му числу так, чтобы сумма всех вы­бран­ных чисел была нечётна и при этом была мак­си­маль­но воз­мож­ной. На­пи­ши­те про­грам­му, вы­во­дя­щую такую сумму на экран. Если же ее не­воз­мож­но по­лу­чить, вы­ве­ди­те 0. Каж­дый эле­мент в паре целый, не­от­ри­ца­тель­ный.

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

За­да­ние Б яв­ля­ет­ся усложнённым ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме.

А. На­пи­ши­те на любом языке про­грам­ми­ро­ва­ния про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, в ко­то­рой вход­ные дан­ные будут за­по­ми­нать­ся в мас­си­ве. Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния.

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния А. Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А  — 2 балла.

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

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

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

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

На­по­ми­на­ем! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.

За­да­ча А. Ко­ли­че­ство пар из­вест­но за­ра­нее и равно 6. Числа не пре­вы­ша­ют 100 000.

За­да­ча Б. Ко­ли­че­ство пар N не из­вест­но за­ра­нее и может при­ни­мать зна­че­ния 2 <= N <= 100 000. На вход по­да­ет­ся сна­ча­ла ко­ли­че­ство пар, затем сами пары. Числа не пре­вы­ша­ют 10 000.

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

6

5 4

3 2

1 1

18 3

11 12

2 5

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

43

Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.

За­да­ние А. Име­ет­ся набор дан­ных, со­сто­я­щий из 6 пар по­ло­жи­тель­ных целых чисел. Не­об­хо­ди­мо вы­брать из каж­дой пары ровно одно число так, чтобы сумма всех вы­бран­ных чисел не де­ли­лась на 3 и при этом была мак­си­маль­но воз­мож­ной. Если по­лу­чить тре­бу­е­мую сумму не­воз­мож­но, в ка­че­стве от­ве­та нужно вы­дать 0.

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

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

За­да­ние Б. Име­ет­ся набор дан­ных, со­сто­я­щий из пар по­ло­жи­тель­ных целых чисел. Не­об­хо­ди­мо вы­брать из каж­дой пары ровно одно число так, чтобы сумма всех вы­бран­ных чисел не де­ли­лась на 3 и при этом была мак­си­маль­но воз­мож­ной. Если по­лу­чить тре­бу­е­мую сумму не­воз­мож­но, в ка­че­стве от­ве­та нужно вы­дать 0.

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

По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

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

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

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

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

Как в ва­ри­ан­те А, так и в ва­ри­ан­те Б про­грам­ма долж­на на­пе­ча­тать одно число  — мак­си­маль­но воз­мож­ную сумму, со­от­вет­ству­ю­щую усло­ви­ям за­да­чи (или 0, если такую сумму по­лу­чить нель­зя).

НА­ПО­МИ­НА­ЕМ! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.

Перед тек­стом про­грам­мы крат­ко опи­ши­те Ваш ал­го­ритм ре­ше­ния, ука­жи­те ис­поль­зо­ван­ный язык про­грам­ми­ро­ва­ния и его вер­сию (на­при­мер, Free Pascal 2.6.4).

Вход­ные дан­ные

Для ва­ри­ан­та А на вход про­грам­ме подаётся шесть строк, каж­дая из ко­то­рых со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.

При­мер вход­ных дан­ных для ва­ри­ан­та А:

1 3

5 12

6 9

5 4

3 3

1 1

Для ва­ри­ан­та Б на вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство пар N (1 ≤ N ≤ 100 000). Каж­дая из сле­ду­ю­щих N строк со­дер­жит два на­ту­раль­ных числа, не пре­вы­ша­ю­щих 10 000.

При­мер вход­ных дан­ных для ва­ри­ан­та Б:

6

1 3

5 12

6 9

5 4

3 3

1 1

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

Дана по­сле­до­ва­тель­ность N целых по­ло­жи­тель­ных чисел. Рас­смат­ри­ва­ют­ся все пары эле­мен­тов по­сле­до­ва­тель­но­сти, раз­ность ко­то­рых чётна, и в этих парах, по край­ней мере, одно из чисел пары де­лит­ся на 17. По­ря­док эле­мен­тов в паре не­ва­жен. Среди всех таких пар нужно найти и вы­ве­сти пару с мак­си­маль­ной сум­мой эле­мен­тов. Если оди­на­ко­вую мак­си­маль­ную сумму имеет не­сколь­ко пар, можно вы­ве­сти любую из них. Если под­хо­дя­щих пар в по­сле­до­ва­тель­но­сти нет, нужно вы­ве­сти два нуля.

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

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

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

5

34

12

51

52

51

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

51 51

По­яс­не­ние. Из дан­ных пяти чисел можно со­ста­вить три раз­лич­ные пары, удо­вле­тво­ря­ю­щие усло­вию: (34, 12), (34, 52), (51, 51). Наи­боль­шая сумма по­лу­ча­ет­ся в паре (51, 51). Эта пара до­пу­сти­ма, так как число 51 встре­ча­ет­ся в ис­ход­ной по­сле­до­ва­тель­но­сти два­жды.

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

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

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

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

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

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

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