РЕШУ ЕГЭ — информатика

Вариант № 9135234

ЕГЭ−2021 по информатике 24.06.2021. Основная волна. Разные задачи

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или четыре камня или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16, 19 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

В начальный момент в куче было S камней, 1 ≤ S ≤ 46.

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

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

В начальный момент в куче было S камней; 1 ≤ S ≤ 46.

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

—  Петя не может выиграть за один ход;

—  Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

В начальный момент в куче было S камней; 1 ≤ S ≤ 46.

Найдите минимальное значение S, при котором одновременно выполняются два условия:

—  у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

—  у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение. Минимальное значение S: 18. После первого хода Пети в куче будет 19, 22 или 36 камней. Если в куче станет 36 камней, Ваня удвоит количество камней и выиграет первым ходом. В ситуации, когда в куче 19 или 22 камня, Ваня добавляет в кучу 4 или 1 камень таким образом, чтобы получилось 23 камня. В этом случае при любой игре Пети Ваня выигрывает своим следующим ходом.

Таким образом, ответ  — 18.

Ответ: 18.

Приведём другое решение на языке Python.

Исключим стратегию Вани, которая позволит ему гарантированно выиграть первым ходом:

def f(x, h):

if (h == 3 or h == 5) and x >= 47:

return 1

elif h == 5 and x < 47:

return 0

elif x >= 47 and h < 5:

return 0

else:

if h % 2 == 0:

return f(x + 1, h + 1) or f(x + 4, h + 1) or f(x * 2, h + 1) # стратегия победителя

else:

return f(x + 1, h + 1) and f(x + 4, h + 1) and f(x * 2, h + 1) # стратегия проигравшего

def f1(x, h):

if h == 3 and x >= 47:

return 1

elif h == 3 and x < 47:

return 0

elif x >= 47 and h < 3:

return 0

else:

if h % 2 == 0:

return f1(x + 1, h + 1) or f1(x + 4, h + 1) or f(x * 2, h + 1) # стратегия победителя

else:

return f1(x + 1, h + 1) and f1(x + 4, h + 1) and f(x * 2, h + 1) # стратегия проигравшего(любой ход)

for x in range(1, 47):

if f(x, 1) == 1:

print(x)

print("====")

for x in range(1, 47):

if f1(x, 1) == 1:

print(x) # Исключим эти значения из списка выше

Текстовый файл содержит только заглавные буквы латинского алфавита (ABC…Z). Определите наибольшую длину цепочки символов, среди которых нет символов K и L, стоящих рядом.

Например, в тексте ABCAABAKLD самая длинная цепочка символов, удовлетворяющая условию,  — ABCAABAK, её длина равна 8.

Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.

Задание 24

Решение. Будем посимвольно считывать строку из файла. Сначала считаем первый символ строки. Далее в цикле будем считывать символы и проверять, встречается ли в текущей цепочке комбинация символов KL или LK. Если такая комбинация не встречается  — увеличиваем счётчик k, если такая комбинация встречается  — сбрасываем счётчик в значение 1.

Приведём решение данной задачи на языке Pascal.

var k, max: integer;
c1, c2: char;
f: text;
begin
    assign(f,'C:\24.txt');
    reset(f);
    k := 1;
    max := 0;
    read(f, c1);
    while not Eof(f) do begin
        c2 := c1;
        read(f, c1);
        if ((c2 = 'K') and (c1 = 'L')) or ((c2 = 'L') and (c1 = 'K')) then begin
            if k > max then 
                max := k;
            k := 1;
        end
        else
            k := k + 1;
    end;
    if k > max then 
        max := k;
    writeln(max);
end.

В результате работы данных алгоритмов при вводе данных из файла в условии получаем ответ  — 2796.

Ответ: 2796.

Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.

Приведём решение Витаса Ремейкиса на языке Python.

file = open('24.txt', 'r')

st = file.readline()

k = 1

mx = 0

for i in range(1, len(st)):

if (st[i] == 'K' and st[i-1] == 'L') or (st[i-1] == 'K' and st[i] == 'L'):

k = 1

else:

k += 1

if k > mx:

mx = k

print(mx)

Приведём решение Ильи Крылова на языке Python.

t = open("24.txt").readline().replace("LK", "L/K").replace("KL", "K/L")

maximum = 0

counter = 0

for i in t:

if i != "/":

counter += 1

else:

maximum = max(maximum, counter)

counter = 0

print(maximum)

Приведём решение Бориса Савельева на языке Python.

f = open('24.txt')

s = f.readline()

maxi = 0

s = s.replace('KL','K L')

s = s.replace('LK','L K')

s = s.split(' ')

for i in range (0,len(s)):

maxi = max(maxi,len(s[i]))

print(maxi)

Приведём решение Ильи Андрианова на языке Python.

s = open('24.txt').readline()

s = s.replace('KL', 'K L').replace('LK', 'L K')

print(max([len(x) for x in s.split()]))

Напишите программу, которая перебирает целые числа, большие 600 000, в порядке возрастания и ищет среди них такие, среди делителей которых есть хотя бы одно число, оканчивающееся на 7, но не равное 7 и самому числу. Необходимо вывести первые 5 таких чисел, и наименьший делитель, оканчивающийся на 7, не равный 7 и самому числу.

Формат вывода: для каждого из 5 таких найденных чисел в отдельной строке сначала выводится само число, затем  — наименьший делитель, оканчивающийся на 7, не равный 7 и самому числу. Строки выводятся в порядке возрастания найденных чисел.

Количество строк в таблице для ответа избыточно.

Ответ:

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

Приведём решение на языке Pascal.

var
    i, j, halfI: longint;
    count: integer;
begin
    count := 0;
    i := 600001;
    while (count < 5) do begin
        halfI := i div 2;
        for j := 2 to halfI do
            if (i mod j = 0) and (j mod 10 = 7) and (j <> 7) then begin
                writeln(i, ' ', j);
                count := count + 1;
                break;
            end;
        i := i + 1;
    end;
end.

В результате работы программа должна вывести следующее:

600001 437

600002 47

600003 1227

600005 217

600012 16667

Приведём решение на языке Python.

count = 0

i = 600001

while count < 5:

halfI = i // 2

for j in range(2, halfI + 1):

if i % j == 0 and j % 10 == 7 and j != 7:

print(i, ' ', j)

count += 1

break

i += 1

Приведём решение Дашкина Семёна на языке Python.

c = 0

x = 600000

while c < 5:

x += 1

a = []

for d in range(17,x//2 + 1, 10):

if x % d == 0:

a.append(d)

if len(a) > 0:

c += 1

print(x, min(a))

Приведём решение Десяткина Александра на языке Python.

a = 600000

count = 0

while count < 5:

a+=1

for i in range(17,a//2+1,10):

if a%i==0:

print(a, i)

count+=1

break

Приведём решение Егора Чернецова на языке Python.

n, c = 600001, 0

while c < 5:

(d := next((i for i in range(17, n, 10) if n % i == 0), 0)) and (print(n, d) or (c := c + 1)); n += 1

№ п/п	№ задания	Ответ
1	37132	12
2	37133	1922
3	37134	18
4	37131	2796
5	37130	600001 437 600002 47 600003 1227 600005 217 600012 16667

ЕГЭ−2021 по информатике 24.06.2021. Основная волна. Разные задачи

Ключ