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

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

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

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

 

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

 

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

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

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

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

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

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

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

 

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

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

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

3

10

130 210

320 140

100 120

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

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

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

400