СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




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

Гоночная трасса состоит из двух основных дорог и нескольких переездов, позволяющих перейти с одной дороги на другую. На всех участках, включая переезды, движение разрешено только в одну сторону, поэтому переезд возможен только с дороги 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.