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


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

Автомобиль, участвующий в гонке, может быть оснащен двумя разными типами колес (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

Решение.

Пусть P0 — точка старта, P1 — первая станция, P2 — вторая, …, PN — финиш. Пусть Xi — минимально возможное время от старта до отправления из Pi, при условии, что автомобиль отправляется из Pi с колесами A, а Yi — минимально возможное время от старта до отправления из Pi, при условии, что автомобиль отправляется из Pi с колесами B. С колесами A можно выехать из Pi только при условии, что с этими же колесами автомобиль прибыл на этот пункт (установить колеса A в ходе гонки нельзя), поэтому Xi = Xi-1 + ai. Если автомобиль выехал из Pi с колесами B, они могли быть установлены либо на станции в этом пункте, либо ранее. Для нахождения Yi нужно вычислить время для каждого из этих случаев и выбрать из них меньшее. Получается, что Yi = min(Xi + t, Yi-1 + bi). Кроме того, очевидно, что X0 = 0, Y0 = 0.

Используя эти соотношения, можно найти значения Xi и Yi для всех i от 1 до N, помня лишь текущие значения ai и bi. Окончательным ответом задачи будет меньшее из значений XN и YN.

 

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

 

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

INPUT N

INPUT t

x = 0: y = 0

FOR i = 1 TO N

INPUT a, b

x = x + a

y1 = x + t

y2 = y + b

IF y1 < y2 THEN

y = y1

ELSE

y = y2

END IF

NEXT i

IF x < y THEN

PRINT x

ELSE

PRINT y

END IF

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 := 0;

for i := 1 to N do begin

readln(a, b);

x := x + a;

y1 := x + t;

y2 := y + b;

if y1 < y2 then y := y1

else y := y2;

end;

if x < y then writeln(x)

else 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;

cin >> t;

x = 0; y = 0;

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

cin >> a >> b;

x = x + a;

y1 = x + t;

y2 = y + b;

if (y1 < y2) y = y1;

else y = y2;

}

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

}

алг

нач

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

цел t | время замены

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

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

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

цел x, y

цел y1, y2

цел i

ввод N

ввод t

x:=0; y:=0

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

ввод a,b

x := x + a

y1 := x + t

y2 := y + b

если y1 < y2

то y := y1

иначе y := y2

все

кц

если x < y

то вывод x

иначе вывод y

все

кон

 

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

 

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 := 3;

k := 11;

for i := 3 to 11 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 := 3;

k := k-1;

end;

val[1] := 0;

val[2] := 0;

for i := 1 to 10 do begin

val[1] := val[1] + times[i,1];

val[2] := val[2] + times[i,2];

end;

min_time := MaxInt;

for i := 1 to 11 do

if val[i] < min_time then min_time := val[i];

writeln(min_time);

end.