Задания
Версия для печати и копирования в MS Word
Тип Д27 C4 № 7321
i

Го­ноч­ная трас­са со­сто­ит из двух ос­нов­ных дорог и не­сколь­ких пе­ре­ез­дов, поз­во­ля­ю­щих пе­рей­ти с одной до­ро­ги на дру­гую. На всех участ­ках, вклю­чая пе­ре­ез­ды, дви­же­ние раз­ре­ше­но толь­ко в одну сто­ро­ну, по­это­му пе­ре­езд воз­мо­жен толь­ко с до­ро­ги A на до­ро­гу B. Гон­щик стар­ту­ет в точке A0 и дол­жен фи­ни­ши­ро­вать в точке BN. Он знает, за какое время смо­жет прой­ти каж­дый уча­сток пути по каж­дой до­ро­ге, то есть время про­хож­де­ния участ­ков A0A1, A1A2, …, AN-1AN, B0B1, B1B2, …, BN-1BN. Время про­хож­де­ния всех пе­ре­ез­дов A0B0, A1B1, …, ANBN оди­на­ко­во и из­вест­но гон­щи­ку. Не­об­хо­ди­мо опре­де­лить, за какое ми­ни­маль­ное время гон­щик смо­жет прой­ти трас­су.

 

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

 

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

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

 

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

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

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

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

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

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

 

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

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

В пер­вой стро­ке задаётся ко­ли­че­ство участ­ков трас­сы N. Во вто­рой стро­ке задаётся целое число t  — время (в се­кун­дах) про­хож­де­ния каж­до­го из пе­ре­ез­дов A0B0, A1B1, …, ANBN. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но два целых числа ai и bi, за­да­ю­щих время (в се­кун­дах) про­хож­де­ния оче­ред­но­го участ­ка на каж­дой из дорог. В пер­вой из этих строк ука­зы­ва­ет­ся время про­хож­де­ния участ­ков A0A1 и B0B1, во вто­рой  — A1A2 и B1B2 и т. д.

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

3

20

320 150

200 440

300 210

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

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

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

750

Спрятать решение

Ре­ше­ние.

Пусть Xi – ми­ни­маль­но воз­мож­ное время дви­же­ния от A0 до Ai, а Yi  — ми­ни­маль­но воз­мож­ное время дви­же­ния от A0 до Bi. В точку Ai можно по­пасть толь­ко из точки Ai-1, по­это­му Xi = Xi-1 + ai. В точку Bi можно по­пасть двумя спо­со­ба­ми: из точки Bi-1 и из точки Ai. Чтобы найти ми­ни­маль­ное время, нужно вы­чис­лить время дви­же­ния каж­дым из этих спо­со­бов и вы­брать из них ми­ни­маль­ное. По­лу­ча­ет­ся, что Yi = min(Yi-1 + bi, Xi + t). Кроме того, оче­вид­но, что X0 = 0, Y0 = t. Ис­поль­зуя эти со­от­но­ше­ния, можно найти зна­че­ния Xi и Yi для всех i от 1 до N, не со­хра­няя всех зна­че­ний asub>i и bsub>i. Зна­че­ние YN будет окон­ча­тель­ным от­ве­том за­да­чи.

При­ме­ры пра­виль­ных и эф­фек­тив­ных про­грамм на раз­лич­ных язы­ках про­грам­ми­ро­ва­ния.

Бей­сикПас­каль

INPUT N

INPUT t

x = 0: y = t

FOR i = 1 TO N

INPUT a, b

x = x + a

y1 = y + b

y2 = x + t

IF y1 < y2 THEN

y = y1

ELSE

y = y2

END IF

NEXT i

PRINT y

END

program c4;

var

N: integer; {ко­ли­че­ство участ­ков}

t: integer; {время пе­ре­ез­да}

a, b: integer; {время про­хож­де­ния участ­ков}

x: integer; {те­ку­щее зна­че­ние X}

y: integer; {те­ку­щее зна­че­ние Y}

y1, y2: integer;

i: integer;

begin

readln(N);

readln(t);

x := 0; y := t;

for i := 1 to N do begin

readln(a, b);

x := x + a;

y1 := y + b;

y2 := x + t;

if y1 < y2 then y := y1

else y := y2;

end;

writeln(y);

end.

СиАл­го­рит­ми­че­ский язык

#include <stdio.h>

void main ()

{

int N; /* ко­ли­че­ство участ­ков */

int t; /* время пе­ре­ез­да */

int a, b; /* время про­хож­де­ния участ­ков */

int x; /* те­ку­щее зна­че­ние X */

int y; /* те­ку­щее зна­че­ние Y */

int y1, y2;

int i;

cin >> N;

scanf("%d" >> t;

x = 0; y = t;

for (i=1; i<=N; ++i) {

cin >> a >> b;

x = x + a;

y1 = y + b;

y2 = x + t;

if (y1 < y2) y = y1;

else y = y2;

}

printf("%d\n",y);

}

алг

нач

цел N | ко­ли­че­ство участ­ков

цел t | время пе­ре­ез­да

цел a, b | время про­хож­де­ния участ­ков

цел x | те­ку­щее зна­че­ние X

цел y | те­ку­щее зна­че­ние Y

цел y1, y2

цел i

ввод N

ввод t

x:=0; y:=t

нц для i от 1 до N

ввод a,b

x := x + a

y1 := y + b

y2 := x + t;

если y1 < y2

то y := y1

иначе y := y2

все

кц

вывод y

кон

При­мер ре­ше­ния за­да­чи А на языке Пас­каль.

 

var
  t: integer; {время за­ме­ны}
  a, b: integer; {время про­хож­де­ния участ­ков}
  times: array [1..10, 1..2] of integer; {ис­ход­ные дан­ные об участ­ках трас­сы}
  min_time: integer; {ми­ни­маль­ное время про­хож­де­ния трас­сы}
  val: array [1..11] of integer;
  x: integer;
  i, j, k: integer;
begin
  readln(t);
  for i := 1 to 10 do begin
    read(a, b);
    times[i,1] := a;
    times[i,2] := b;     
  end;
  x := 2;
  k := 10;
  for i := 2 to 10 do begin
    val[i] := t;
    for j := 1 to 10 do begin
      if x>k then
        val[i] := val[i] + times[j, 2]
      else val[i] := val[i] + times[j, 1];
      x := x + 1;
    end;
    x := 2;
    k := k-1;
  end;
  val[1] := t;
  for i := 1 to 10 do begin
    val[1] := val[1] + times[i,1];
  end;
  min_time := MaxInt;
  for i := 1 to 10 do
    if val[i] < min_time then min_time := val[i];
  writeln(min_time);
end.
Спрятать критерии
Критерии проверки:

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
По­яс­не­ния для про­ве­ря­ю­щих.

1. За­да­ние Б яв­ля­ет­ся услож­не­ни­ем за­да­ния А. Если в ка­че­стве ре­ше­ния за­да­ния Б пред­став­ле­но ре­ше­ние за­да­ния А, то со­глас­но при­ведённым ниже кри­те­ри­ям его оцен­ка будет такой же, как если бы это ре­ше­ние было пред­став­ле­но в ка­че­стве ре­ше­ния за­да­ния А.

2. Два за­да­ния (и, со­от­вет­ствен­но, воз­мож­ность для эк­за­ме­ну­е­мо­го пред­ста­вить две про­грам­мы) дают уче­ни­ку воз­мож­ность (при его же­ла­нии) сна­ча­ла на­пи­сать менее слож­ное и менее эф­фек­тив­ное ре­ше­ние (за­да­ние А), ко­то­рое даёт ему право по­лу­чить 2 балла, а затем при­сту­пить к по­ис­ку более эф­фек­тив­но­го ре­ше­ния.

3. При­ведённые в п. 2.1–2.5 пра­ви­ла имеют целью из­бе­жать сни­же­ния оцен­ки из-за того, что уче­ник пе­ре­пу­тал обо­зна­че­ния за­да­ний

Кри­те­рии оце­ни­ва­ния за­да­ния А
При ре­ше­нии за­да­чи A про­грам­ма верно на­хо­дит тре­бу­е­мую сумму

для любых 6 пар ис­ход­ных дан­ных. До­пус­ка­ет­ся до пяти син­так­си­че­ских и при­рав­нен­ных к ним оши­бок (см. кри­те­рии оце­ни­ва­ния за­да­ния Б на 4 балла)

2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2 балла. Из опи­са­ния ал­го­рит­ма и общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи. До­пус­ка­ет­ся любое ко­ли­че­ство «опи­сок»1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1 или 2 балла0
Мак­си­маль­ный балл для за­да­ния А2

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

Про­грам­ма может со­дер­жать не более трёх син­так­си­че­ских оши­бок сле­ду­ю­щих видов:

1) про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции;

2) не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка про­грам­ми­ро­ва­ния;

3) не опи­са­на или не­вер­но опи­са­на пе­ре­мен­ная;

4) при­ме­ня­ет­ся опе­ра­ция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных.

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

4
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 4 балла.

Про­грам­ма в целом ра­бо­та­ет пра­виль­но для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Время ра­бо­ты про­пор­ци­о­наль­но ко­ли­че­ству введённых чисел; пра­виль­но ука­за­но, какие ве­ли­чи­ны долж­ны вы­чис­лять­ся по ходу чте­ния эле­мен­тов по­сле­до­ва­тель­но­сти чисел. Ко­ли­че­ство син­так­си­че­ских оши­бок («опи­сок») ука­зан­ных выше видов – не более пяти.

Ис­поль­зу­е­мая па­мять, воз­мож­но, за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел (на­при­мер, вход­ные дан­ные за­по­ми­на­ют­ся в мас­си­ве, кон­тей­не­ре STL в C++ или дру­гой струк­ту­ре дан­ных).

До­пус­ка­ет­ся ошиб­ка при вводе и вы­во­де дан­ных, не вли­я­ю­щая на со­дер­жа­ние ре­ше­ния.

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

Кроме того, до­пус­ка­ет­ся на­ли­чие одной ошиб­ки, при­над­ле­жа­щей к од­но­му из сле­ду­ю­щих видов:

1) ошиб­ка ини­ци­а­ли­за­ции, в том числе от­сут­ствие ини­ци­а­ли­за­ции;

2) не вы­во­дит­ся ре­зуль­тат, рав­ный 0, или вме­сто 0 вы­во­дит­ся не­вер­ное зна­че­ние;

3) до­пу­щен выход за гра­ни­цу мас­си­ва;

4) ис­поль­зу­ет­ся знак “<” вме­сто “<=”, “or” вме­сто “and” и т.п.

3
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 или 4 балла.

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

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

2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2, 3 или 4 балла. Из опи­са­ния ал­го­рит­ма или общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи не­за­ви­си­мо от эф­фек­тив­но­сти. При этом про­грам­ма может быть пред­став­ле­на от­дель­ны­ми фраг­мен­та­ми, без огра­ни­че­ний на ко­ли­че­ство син­так­си­че­ских и со­дер­жа­тель­ных оши­бок. 1 балл ста­вит­ся также за ре­ше­ния, вер­ные лишь в част­ных слу­ча­ях1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Мак­си­маль­ный балл для за­да­ния Б4
Ито­го­вый мак­си­маль­ный балл4
Спрятать решение · КритерииСпрятать критерии · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026