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


Вариант № 5872103

При выполнении заданий с кратким ответом впишите в поле для ответа цифру, которая соответствует номеру правильного ответа, или число, слово, последовательность букв (слов) или цифр. Ответ следует записывать без пробелов и каких-либо дополнительных символов. Дробную часть отделяйте от целой десятичной запятой. Единицы измерений писать не нужно.


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


Версия для печати и копирования в MS Word
Времени прошло:0:00:00
Времени осталось:3.9166666666666665:55:00
1
Задание 1 № 405

Вычислите сумму чисел х и у при x = B316, у = 1101102. Результат представьте в десятичной системе счисления.


Ответ:

2
Задание 2 № 15842

Логическая функция F задаётся выражением (x ∧ ¬y) ∨ (yz ) ∨ w.

Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.

Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.

 

Переменная 1Переменная 2Переменная 3Переменная 4Функция
????????????F
10
10000
1100

 

В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

Пример. Пусть задано выражение xy, зависящее от двух переменных x и y, и фрагмент таблицы истинности:

 

Переменная 1Переменная 1Функция
??????F
010

 

Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.


Ответ:

3
Задание 3 № 11232

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах).

 

П1П2П3П4П5П6П7П8
П1152018
П21525
П3252422
П42012
П5131617
П6241315
П71216
П818221715

 

Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину дороги из пункта Б в пункт Г. В ответе запишите целое число.


Ответ:

4
Задание 4 № 15972

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, сколько жителей родились в том же городе, что и их внук или внучка. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.

 

Таблица 1
IDФамилия И.О.ПолМесто рождения
64Келдыш С.М. МЛипецк
66Келдыш О.Н. ЖБрянск
67Келдыш М.И. МЛипецк
68Келдыш Н.С. ЖЛипецк
69Дейнеко Н.А.ЖБрянск
70Сиротенко В.Н.МТула
72Сиротенко Д.В.МТула
75Сиротенко Н.П,МТамбов
77Мелконян А.А.МТамбов
81Мелконян И.Н.ЖТамбов
82Лурье А.В.ЖТула
86Хитрово Н.И.МБрянск
88Хитрово Т.Н.ЖТула
89Гурвич З.И.ЖТула

Таблица 2
ID РодителяID Ребенка
6664
6764
8666
8169
7570
8970
7072
8872
8177
7581
8981
7082
8882
8688


Ответ:

5
Задание 5 № 1105

Для кодирования букв И, Д, Т, О, X решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ТИХОХОД таким способом и результат запишите шестнадцатеричным кодом.


Ответ:

6
Задание 6 № 13536

Автомат получает на вход четырёхзначное десятичное число, в котором все цифры нечётные. По этому числу строится новое число по следующим правилам.

1. Складываются первая и вторая, а также третья и четвёртая цифры.

2. Полученные два числа записываются друг за другом в порядке неубывания (без разделителей).

Пример. Исходное число: 7511. Суммы: 7 + 5 = 12; 1 + 1 = 2. Результат: 212. Сколько существует чисел, в результате обработки которых автомат выдаст число 414


Ответ:

7
Задание 7 № 1610

В электронной таблице значение формулы =CPЗHAЧ(C2:D5) равно 4. Чему равно значение формулы =CУMM(C5:D5), если значение формулы =CPЗHAЧ(C2:D4) равно 5? Пустых ячеек в таблице нет.


Ответ:

8
Задание 8 № 3249

Определите, что будет напечатано в результате работы следующего фрагмента программы:

 

 

БейсикPython

DIM N, S AS INTEGER

N = 4

S = 0

WHILE N <= 8

    S = S + N

    N = N + 1

WEND

PRINT S

n = 4

s = 0

while n <= 8:

    s += n

    n += 1

print(s)

ПаскальАлгоритмический язык

var n, s: integer;

begin

    n := 4;

    s := 0;

    while n <= 8 do

    begin

        s := s + n;

        n := n + 1;

    end;

    writeln(s);

end.

алг

нач

    цел n, s

    n := 4

    s := 0

    нц пока n <= 8

        s := s + n

        n := n + 1

    кц

    вывод s

кон

Си++

#include <iostream>

using namespace std;

int main() {

    int n, s;

    n = 4, s = 0;

    while (n <= 8) {

        s = s + n;

        n = n + 1;

    }

    cout << s << endl;

    return 0;

}

 


Ответ:

9
Задание 9 № 14695

Автоматическая фотокамера производит растровые изображения размером 800 х 600 пикселей. При этом объём файла с изображением не может превышать 600 Кбайт, упаковка данных не производится. Какое максимальное количество цветов можно использовать в палитре?


Ответ:

10
Задание 10 № 4802

Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?


Ответ:

11
Задание 11 № 9362

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.

 

БейсикPython

DECLARE SUB F(n)

DECLARE SUB G(n)

 

SUB F(n)

    IF n > 0 THEN G(n - 1)

END SUB

 

SUB G(n)

    PRINT "*"

    IF n > 1 THEN F(n - 3)

END SUB

def F(n):

    if n > 0:

        G(n - 1)

def G(n):

    print("*")

    if n > 1:

        F(n - 3)

ПаскальАлгоритмический язык

procedure F(n: integer); forward;

procedure G(n: integer); forward;

 

procedure F(n: integer);

begin

    if n > 0 then

        G(n - 1);

end;

 

procedure G(n: integer);

begin

    writeln('*');

    if n > 1 then

        F(n - 3);

end;

алг F(цел n)

нач

    если n > 0 то

        G(n - 1)

    все

кон

 

алг G(цел n)

нач

    вывод "*"

    если n > 1 то

        F(n - 3)

    все

кон

Си

void F(int n);

void G(int n);

 

void F(int n){

    if (n > 0)

        G(n - 1);

}

 

void G(int n){

    printf("*");

    if (n > 1)

        F(n - 3);

}

 

 

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?


Ответ:

12
Задание 12 № 2228

Петя записал IP-адрес школьного сервера на листке бумаги и положил его в карман куртки. Петина мама случайно постирала куртку вместе с запиской. После стирки Петя обнаружил в кармане четыре обрывка с фрагментами IP-адреса. Эти фрагменты обозначены буквами А, Б, В и Г. Восстановите IP-адрес. В ответе укажите последовательность букв, обозначающих фрагменты, в порядке, соответствующем IP-адресу.

 


Ответ:

13
Задание 13 № 1910

Индивидуальные номера страховых медицинских свидетельств жителей в некоторой стране содержат только цифры 1, 3, 5, 7 и содержат одинаковое количество цифр, а именно 3 цифры. Известно, что медицинскую страховку имеют абсолютно все жители и номера всех свидетельств различны. Каково максимально возможное количество жителей в стране?


Ответ:

14
Задание 14 № 5083

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:

вверх вниз влево вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх ↑, вниз ↓, влево ←, вправо →.

Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ (также по отношению к наблюдателю):

сверху
свободно
снизу
свободно
слева
свободно
справа
свободно

Цикл

ПОКА < условие >

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно.

В конструкции

ЕСЛИ < условие >

ТО команда1

ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно)

 

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?

 

НАЧАЛО

ПОКАснизу свободно ИЛИ справа свободно

ПОКА снизу свободно

вниз

КОНЕЦ ПОКА

вправо

КОНЕЦ ПОКА

КОНЕЦ


Ответ:

15
Задание 15 № 15855

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.

Сколько существует различных путей из города А в город М, проходящих через город Ж?


Ответ:

16
Задание 16 № 2319

Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 31 оканчивается на 4.


Ответ:

17
Задание 17 № 5095

В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» - символ «&».

В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.

 

ЗапросНайдено страниц
(в тысячах)
Гоголь6000
Башмачкин40
Кряква600
Гоголь & Кряква200
Гоголь & Башмачкин30

 

По запросу Башмачкин & Кряква ни одной страницы найдено не было.

Какое количество страниц (в тысячах) будет найдено по запросу Гоголь | Башмачкин | Кряква? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.


Ответ:

18
Задание 18 № 15140

Сколько существует целых значений числа A, при которых формула

 

((x < A) → (x2 < 81)) ∧ ((y2 ≤ 36) → (yA))

 

тождественно истинна при любых целых неотрицательных x и y?


Ответ:

19
Задание 19 № 11355

В программе используется одномерный целочисленный массив A с индексами от 0 до 9. Значения элементов равны 1, 2, 5, 8, 9, 3, 4, 0, 7, 6 соответственно, т. е. A[0] = 1, A[1] = 2 и т. д.

Определите значение переменной j после выполнения следующего фрагмента программы (записанного ниже на пяти языках программирования).

 

БейсикPython

j = 5

WHILE A(j) < A(j-1)

    t = A(j)

    A(j) = A(j-1)

    A(j-1) = t

    j = j - 1

WEND

j = 5

while A[j] < A[j-1]:

    A[j],A[j-1]=A[j-1],A[j]

    j -= 1

ПаскальАлгоритмический язык

j := 5;

while A[j] < A[j-1] do

    begin

        t := A[j];

        A[j] := A[j-1];

        A[j-1] := t;

        j := j - 1;

    end;

j := 5

нц пока A[j] < A[j-1]

    t := A[j]

    A[j] := A[j-1]

    A[j-1] := t

    j := j - 1

кц

Си++

j = 5;

while (A[j] < A[j-1])

    {

        t = A[j];

        A[j] = A[j-1];

        A[j-1] = t;

        j -= 1;

    }

 


Ответ:

20
Задание 20 № 15930

Ниже на пяти языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа a и b. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 12.

 

 

БейсикPython

DIM X, A, B AS INTEGER

INPUT X

A = 0: B = 1

WHILE X > 0

    IF X MOD 2 > 0 THEN

        A = A + X MOD 8

    ELSE

        B = B * X MOD 8

    END IF

    X = X \ 8

WEND

PRINT A

PRINT B

 

x = int(input())

a=0; b=1

while x > 0:

    if x%2 > 0:

        a += x%8

    else:

        b = b * (x%8)

    x = x//8

print(a, b)

 

ПаскальАлгоритмический язык

var x, a, b: longint;

begin

    readln(x);

    a := 0; b := 1;

    while x > 0 do begin

        if x mod 2 > 0 then

            a := a + x mod 8

        else

            b := b * (x mod 8);

        x := x div 8;

    end;

    writeln(a); write(b);

end.

 

алг

нач

    цел x, a, b

    ввод x

    a := 0; b := 1

    нц пока x > 0

        если mod(x,2)>0

            то a := a + mod(x,8)

            иначе b := b*mod(x,8)

        все x := div(x,8)

    кц

    вывод a, нс, b

кон

 

С++

#include <iostream>

using namespace std;

int main()

{

    int x, a, b;

    cin >> x;

    a = 0; b = 1;

    while (x > 0) {

        if (x%2 > 0)

            a += x%8;

        else

            b *= x%8;

        x = x / 8;

    }

    cout << a << endl << b << endl;

    return 0;

}

 

 


Ответ:

21
Задание 21 № 5466

Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма (для Вашего удобства алгоритм представлен на пяти языках).

 

 

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

DIM A, B, T, M, R AS INTEGER

A = -10: B = 31

M = A: R = F(А)

FOR T = A TO B

    IF F(T) > R THEN

        M = T

        R = F(T)

    END IF

NEXT T

PRINT M

    FUNCTION F(x)

        F = 2*(x*x-1)*(x*x-1)+17

    END FUNCTION

var a,b,t,M,R :integer;

Function

F(x:integer):integer;

    begin

    F := 2*(x*x-1)*(x*x-1)+17

    end;

begin

    a := -10; b := 31;

    M := a; R := F(a);

    for t := a to b do begin

        if (F(t) > R) then begin

            M := t;

            R := F(t)

        end

    end;

    write(M)

end.

Си++Алгоритмический

#include <iostream>

using namespace std;

int F(int x)

{

    return 2*(x*x-1)*(x*x-1)+17;

}

int main()

{

    int a, b, t, M, R;

    a = -10; b = 31;

    M = a; R = F(a);

    for (t = a; t <= b; t++) {

        if (F(t) > R) {

            M = t; R = F(t);

        }

    }

    cout « M « endl;

}

алг

нач

цел a, b, t, M, R

a := -10; b := 31

M := a; R := F(a)

нц для t от a до b

    если F(t) > R

        то M := t; R := F(t)

    все

кц

вывод M

кон

алг цел F(цел x)

нач

    знач:=2*(x*x-1)*(x*x-1)+17

кон

Python

def f(x):

    return 2*(x*x-1)*(x*x-1)+17

a = -10

b = 31

M = a

R = f(a)

for t in range(a, b+1):

    if (f(t) > R):

        M = t

        R = f(t);

print(M)

 


Ответ:

22
Задание 22 № 14708

Исполнитель Тренер преобразует число на экране.

У исполнителя есть две команды, которым присвоены номера:

 

1. Прибавить 1

2. Умножить на 2

 

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Тренер —  это последовательность команд.

Сколько существует программ, которые преобразуют исходное число 1 в число 30 и при этом траектория вычислений содержит числа 10 и 21?

Траектория должна содержать оба указанных числа. Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 14, 15, 30.


Ответ:

23
Задание 23 № 8671

Сколько существует различных наборов значений логических переменных x1,

x2, … x10, которые удовлетворяют всем перечисленным ниже условиям?

¬(x1 ≡ x2) ∧ (¬x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ (¬x2 ≡ x4) = 0

¬(x8 ≡ x9) ∧ (¬x8 ≡ x10) = 0

В ответе не нужно перечислять все различные наборы значений переменных

x1, x2, … x10 при которых выполнена данная система равенств. В качестве

ответа Вам нужно указать количество таких наборов.


Ответ:

24
Задание 24 № 5067

Требовалось написать программу, при выполнении которой с клавиатуры считываются координаты точки на плоскости (х, у — действительные числа) и определяется принадлежность этой точки заданной закрашенной области (включая границы). Ученик написал такую программу:

 

ПаскальБейсик
var x, y: real;

begin

readln(x,у);

if у >= x*x − 6 then begin

if x*x + y*y <= 16 then write('принадлежит')

end

else

if x >= 0 then

write('принадлежит')

else

write('не принадлежит')

end.

INPUT х, у

IF у >= х*х − 6 THEN

IF х*х + у*у <= 16 THEN PRINT "принадлежит"

ELSE

IF х => О THEN

PRINT "принадлежит"

ELSE

PRINT "не принадлежит"

END IF

END IF

END

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

#include <iostream>

using namespace std;

int main(){

float x, y;

cin >> x >> y;

if (y >= x*x − 6) {

if (x*x +y*y <= 16) cout << принадлежит;

}

else

if (x >= 0)

cout << "принадлежит";

else

cout << "не принадлежит";

}

алг

нач

вещ х, у

ввод х, у

если у >= х*х − 6 то

если х*х + у*у <= 16 то

вывод 'принадлежит'

все

иначе

если х >= 0 то

вывод 'принадлежит'

иначе

вывод 'не принадлежит'

все

все

кон

Python

x = float(input())

y = float(input())

if у >= х*х − 6:

    if х*х + у*у <= 16:

        print("принадлежит")

else:

    if х => 0:

        print("принадлежит")

    else:

        print("не принадлежит")

 

При проверке работы программа выполнялась по шагам для некоторых контрольных значений х и у, при этом был заполнен протокол тестирования. В результате неаккуратного обращения протокол был испорчен, частично сохранились только четыре строки:

 

ОбластьУсловие 1 (y >= x*x – 6)Условие 2 (x*x + y*y<= 16)Условие 3 (x >= 0)ВыводВерно
да
принадлежитнет
не принадлежитда
да
дада

 

Графы протокола содержат следующую информацию.

 

Область - часть плоскости, которой принадлежит проверяемая точка. (Все

возможные области отмечены на рисунке буквами А, В, С, ... S.)

 

Условие 1, Условие2, Условие 3 — результат проверки соответствующего

условия (да или нет). Если условие не проверялось, в протокол записывался

прочерк.

 

Вывод — сообщение, которое вывела программа. Если программа ничего не вывела, в протокол записывался прочерк.

 

Верно - итоговое заключение (да или нет) о правильности результата работы программы при данных значениях х и у.

 

Последовательно выполните следующее.

1. Восстановите уцелевшие строки протокола, заполнив все клетки таблицы. Там, где содержание восстанавливается неоднозначно, запишите любое возможное значение. Например, если для нескольких областей получается одинаковая строка таблицы, укажите в графе «Область» любую из этих областей.

2. Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы. (Это можно сделать несколькими способами, достаточно указать любой способ доработки исходной программы.)


Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.

25
Задание 25 № 7936

Дан массив, содержащий неотрицательные целые числа. Необходимо вывести:

- максимальный чётный элемент, если количество чётных элементов не меньше, чем нечётных;

- максимальный нечётный элемент, если количество нечётных элементов больше, чем чётных.

Например, для массива из шести элементов, равных соответственно 4, 6, 12, 17, 3, 8, ответом будет 12 — наибольшее чётное число, поскольку чётных чисел в этом массиве больше.

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

 

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

CONST N=2000

DIM A(N) AS INTEGER

DIM I, J, K, M AS INTEGER

FOR I = 1 TO N

INPUT A(I)

NEXT I

END

const

N=2000;

var

a: array [1..N] of integer;

i, j, k, m: integer;

begin

for i:=1 to N do

readln(a[i]);

end.

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

#include <iostream>

using namespace std;

#define N 2000

int main(){

int a[N];

int i, j, k, m;

for (i=0; i < N; i++)

 

cin >> a[i];

return 0;

}

алг

нач

цел N=2000 | Изменять значение
этой переменной нельзя

целтаб a[1:N]

цел i, j, k, m

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

ввод a[i]

кц

кон

Python

// допускается также использовать

// целочисленные переменные j, k, m

a = []

n = 2000 // менять значение n нельзя

for i in range(0, n):

    a.append(int(input()))

 

В качестве ответа Вам необходимо привести фрагмент программы, который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например, Free Pascal 2.6). В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в приведённых фрагментах.


Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.

26
Задание 26 № 16455

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

 

добавить в одну из куч один камень или

увеличить количество камней в куче в два раза.

 

Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 18). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

В начальный момент в первой куче было 10 камней, во второй куче — S камней, 1 ≤ S ≤ 51.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по ней игрока, которые не являются для него безусловно выигрышными, то есть не гарантируют выигрыш независимо от игры противника.

Выполните следующие задания.

Задание 1.

а) Назовите все значения S, при которых Петя может выиграть первым ходом, причём у Пети есть ровно один выигрывающий ход.

б) Назовите минимальное значение S, при котором Ваня может выиграть первым ходом в случае неудачного первого хода Пети.

Задание 2.

Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для указанного значения S опишите выигрышную стратегию Пети.

Задание 3.

Укажите такое значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

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


Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.

27
Задание 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


Решения заданий с развернутым ответом не проверяются автоматически.
На следующей странице вам будет предложено проверить их самостоятельно.
Времени прошло:0:00:00
Времени осталось:3.9166666666666665:55:00
Завершить тестирование, свериться с ответами, увидеть решения.