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

Вариант № 7408953

Демонстрационная версия ЕГЭ−2021 по информатике

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

	П1	П2	П3	П4	П5	П6	П7
П1				9			7
П2				5		11
П3						12
П4	9	5			4	13	15
П5				4		10	8
П6		11	12	13	10
П7	7			15	8

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

Логическая функция F задаётся выражением (x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.

Переменная 1	Переменная 2	Переменная 3	Переменная 4	Функция
1		1		1
0	1		0	1
	1	1	0	1

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

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

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

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

Решение. Значение выражения всегда ложно тогда, когда переменная w равна 1. Следовательно, столбцы, в которых содержится единица, не могут соответствовать переменной w, то есть переменной w соответствует четвёртый столбец.

Чтобы выражение было истинным, переменная z или переменная y должна принимать значение 0. Значит, в первом столбце в третьей строке должен стоять 0. Из третьей строки заключим, что переменные y и z должны соответствовать первому и второму столбцам таблицы. Если переменная y будет соответствовать первому столбцу, а переменная z  — второму, то во второй строке выражение окажется ложным, поскольку переменная x в третьем столбце второй строки должна быть равна 0, чтобы строки таблицы истинности не повторялись. Тогда y соответствует второму столбцу, а z  — первому. Значит, третьему столбцу соответствует переменная x.

Таким образом, ответ: zyxw.

Приведём другое решение.

Составим таблицу истинности для выражения (x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w вручную или при помощи языка Python:

print("x y z w")

for x in range(0, 2):

for y in range(0, 2):

for z in range(0, 2):

for w in range(0, 2):

if (x or y) and not(y == z) and not(w):

print(x, y, z, w)

Далее выпишем те наборы переменных, при которых данное выражение равно 1. В наборах переменные запишем в порядке х, y, z, w. Получим следующие наборы:

(0, 1, 0, 0),

(1, 0, 1, 0),

(1, 1, 0, 0).

Сопоставим эти наборы с приведенным в задании фрагментом таблицы истинности.

Ни в одном из наборов переменная w не принимает единичное значение. Следовательно, переменной w соответствует четвертый столбец таблицы.

Заметим, что в первой и в третьей строках таблицы как минимум две переменные принимают единичные значения. Следовательно, набор (0, 1, 0, 0) может соответствовать только второй строке таблицы, тогда во второй строке в третьем столбце стоит 0, а второй столбец соответствует переменной у, принимающей в этом наборе единичное значение.

Заметим, что переменная, стоящая в третьем столбце таблицы, принимает единичное значение дважды, значит, третий столбец соответствует переменной х.

Тогда первый столбец соответствует переменной z.

Ответ: zyxw.

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

Таблица 1
ID	Фамилия_И. О.	Пол	Год рождения
14	Краснова Н. А.	Ж	1937
24	Сканави И. П.	М	1943
25	Сканави П. И.	М	1974
26	Сканави П. П.	М	2001
34	Кущенко А. И.	Ж	1964
35	Кущенко В. С.	Ж	1990
36	Кущенко С. С.	М	1964
44	Лебедь А. С.	Ж	1938
45	Лебедь В. А.	М	1953
46	Гросс О. С.	Ж	1993
47	Гросс П. О.	М	2009
54	Клычко А. П.	Ж	1995
64	Крот П. А.	Ж	1973
...	...	...	...

Таблица 2
ID_Родителя	ID_Ребенка
24	25
44	25
25	26
64	26
24	34
44	34
34	35
36	35
14	36
34	46
36	46
25	54
64	54
...	...

Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв  — П и Р  — кодовые слова неизвестны.

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

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1.  Строится двоичная запись числа N.

2.  К этой записи дописываются справа ещё два разряда по следующему правилу:

а)  складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б)  над этой записью производятся те же действия  — справа дописывается остаток от деления суммы её цифр на 2.

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

Определите, при каком наибольшем введённом значении переменной s программа выведет число 64. Для Вашего удобства программа представлена на четырёх языках программирования.

Си++	Python
#include <iostream> using namespace std; int main() {     int s, n;     cin >> s;     s = s / 10;     n = 1 ;     while (s < 51) {         s = s + 5;         n = n * 2;     }     cout << n << endl;     return 0; }	s = int(input()) s = s // 10 n = 1 while s < 51:     s = s + 5     n = n * 2 print(n)
Паскаль	Алгоритмический язык
var s, n: integer; begin     readln (s);     s := s div 10;     n := 1;     while s < 51 do     begin         s := s + 5;         n := n * 2     end;     writeln(n) end.	алг нач     цел n, s     ввод s     s := div( s, 10)     n := 1     нц пока s < 51         s := s + 5         n := n * 2     кц     вывод n кон

Для хранения произвольного растрового изображения размером 128 × 320 пикселей отведено 20 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?

Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?

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

Задание 9

Найдите разность между максимальным значением температуры и её средним арифметическим значением. В ответе запишите только целую часть получившегося числа.

10.  

С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «долг» или «Долг» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «долг», такие как «долги», «долгами» и т. д., учитывать не следует. В ответе укажите только число.

Задание 10

11.  

При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 15 символов и содержащий только символы из 8-⁠символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байт на один объект.

Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число  — количество байт.

12.  

Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

А)  заменить (v, w).

Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.

Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.

Б)  нашлось (v).

Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка

исполнителя при этом не изменяется.

Цикл

    ПОКА условие

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

    КОНЕЦ ПОКА

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

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

    ЕСЛИ условие

        ТО команда1

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

    КОНЕЦ ЕСЛИ

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

Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.

НАЧАЛО

    ПОКА нашлось (2222) ИЛИ нашлось (8888)

        ЕСЛИ нашлось (2222)

            ТО заменить (2222, 88)

            ИНАЧЕ заменить (8888, 22)

        КОНЕЦ ЕСЛИ

    КОНЕЦ ПОКА

КОНЕЦ

13.  

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

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

Решение. Количество путей до города Х = количество путей добраться в любой из тех городов, из которых есть дорога в Х.

При этом если путь должен не проходить через какой-то город, нужно просто не учитывать этот город при подсчёте сумм. А если город наоборот обязательно должен лежать на пути, тогда для городов, в которые из нужного города идут дороги, в суммах нужно брать только этот город.

С помощью этого наблюдения посчитаем последовательно количество путей до каждого из городов:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4

З = В = 4 (Г и Д не учитываем, поскольку путь должен проходить через В)

Ж = В + З = 4 + 4 = 8 (Е не учитываем, поскольку путь должен проходить через В)

И = З + Ж = 4 + 8 = 12

К = Л = И =12

М = К + Л = 24

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

Приведем другое решение.

Количество путей из города А в город М, проходящих через город В, равно произведению количества путей из города А в город В и количества путей из города В в город М.

Найдем количество путей из города А в город В:

А = 1

Б = А = 1

Д = А = 1

Г = А + Д = 1 + 1 = 2

В = А + Б + Г = 4.

Заметим, что из города В в город М можно добраться только через город И. Следовательно, количество путей из города В в город М равно произведению количества путей из города В в город И и количества путей из города И в город М.

Найдем количество путей из города В в город И (при этом В  — исходный пункт):

В = 1

З = В =1

Ж = В + З = 1 + 1 = 2

И = З + Ж = 1 + 2 = 3.

Из города И в город М есть два пути: И—К—М и И—Л—м.

Таким образом, количество путей из города А в город М, проходящих через город В, равно 4 · 3 · 2  =  24.

Ответ: 24.

14.  

Значение выражения 49⁷ + 7²¹ − 7? записали в системе счисления с основанием 7.

Сколько цифр 6 содержится в этой записи?

15.  

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

Для какого наибольшего натурального числа А формула

¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

16.  

Алгоритм вычисления значения функции F(n), где n  — натуральное число, задан следующими соотношениями:

F(n)  =  1 при n  =  1;

F(n)  =  n + F(n − 1), если n чётно;

F(n)  =  2 · F(n − 2), если n > 1 и при этом n нечётно.

Чему равно значение функции F(26)?

Решение. Приведём программу на Паскале, решающий данную задачу:

var n: longint;
function F(n: longint): longint;
  begin
    if n = 1 
      then F := 1
    else if ((n mod 2) = 0) 
      then F := n + F(n - 1)
    else if (((n mod 2) = 1) and (n > 1)) 
      then F := 2 * F(n - 2);
  end;
begin
  n := F(26);
  writeln(n);
end.

Приведём аналитическое решение. Заметим, что значения функции от нечётных n являются значениями степеней двойки: F(1)  =  1, F(3)  =  2, F(5)  =  4 и так далее. Значит, F(25)  =  4096. Тогда F(26)  =  26 + 4096  =  4122.

Ответ: 4122.

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

def F(n):

if n == 1:

return 1

if n % 2 == 0:

return n + F(n - 1)

if n % 2 != 0 and n > 1:

return 2 * F(n - 2)

print(F(26))

17.  

Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем максимальное число.

Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.

18.  

Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз  — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.

Задание 18

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

Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.

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

1	8	8	4
10	1	1	3
1	3	12	2
2	3	5	6

Для указанных входных данных ответом должна быть пара чисел 41 и 22.

Решение. Сначала найдём максимальную денежную сумму. Для этого найдём максимальную денежную сумму для каждой ячейки таблицы. Для каждой ячейки верхней строки это будет сумма всех ячеек слева от текущей. Для каждой ячейки левого столбца это будет сумма всех ячеек сверху от текущей. В ячейку L1 запишем формулу =СУММ($A$1:A1). Скопируем эту формулу во все ячейки в диапазоне M1:U1 и в диапазоне L2:L10. Для остальных ячеек будем сравнивать значение ячейки слева и значение ячейки сверху и присваивать текущей ячейке значение суммы той ячейки, в которой значение больше, и текущей ячейки. В M2 запишем формулу =ЕСЛИ(L2>M1;L2+B2;M1+B2) и скопируем эту формулу во все ячейки диапазона M2:U10. Таким образом, в ячейке U10 получим значение максимальной денежной суммы  — 1204.

Аналогичным образом найдём значение минимальной денежной суммы. Ячейки диапазонов L1:L10 и M1:U1 заполняются также, как при поиске максимальной денежной суммы. В M2 запишем формулу =ЕСЛИ(L2 < M1;L2+B2;M1+B2) и скопируем эту формулу во все ячейки диапазона M2:U10. Таким образом, в ячейке U10 получим значение минимальной денежной суммы  — 502.

Ответ: 1204502.

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

s = tuple(tuple(int(x) for x in m.split(';')) for m in open('18_demo.csv').read().splitlines())

N = len(s)

for f in [lambda a, b: max(a, b), lambda a,b: min(a, b)]:

m = [[0 for _ in range(N)] for _ in range(N)]

m[0][0] = s[0][0]

for i in range(1, N):

m[0][i]=s[0][i]+m[0][i-1]

m[i][0]=s[i][0]+m[i-1][0]

for row in range(1, N):

for column in range(1, N):

m[row][column] = s[row][column]+f(m[row-1][column], m[row][column-1])

print(m[N-1][N-1],end='')

19.  

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

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

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

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

Решение. Заметим, что игра должна закончиться в 2 хода. Минимальное значение количества камней в обеих кучах, при котором игра заканчивается,  — 77. Эта ситуация возможна, например, когда в первой куче 7 камней, а во второй  — 70. Значит, чтобы Ваня мог выиграть своим первым ходом, количество камней во второй куче должно быть ≥35. Поскольку удваиванием число 35 получить нельзя, после первого хода Пети во второй куче должно получиться 36 камней. Это возможно при значении S  =  18. При таком минимальном значении S Ваня выиграет своим первым ходом после неудачного хода Пети.

Ответ: 18.

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

def f(x, y, h):

if h == 3 and x + y >= 77:

return 1

elif h == 3 and x + y < 77:

return 0

elif x + y >= 77 and h < 3:

return 0

else:

if h % 2 == 0:

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

else:

return f(x + 1, y, h + 1) or f(x, y + 1, h + 1) or f(x * 2, y, h + 1) or f(x, y * 2, h + 1) # стратегия проигравшего(неудачный ход)

for x in range(1, 70):

if f(x, 7, 1) == 1:

print("Задача 19:", x)

break

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

from functools import lru_cache

def moves(h):

a, b = h

return (a+1, b), (a, b+1), (a*2, b), (b*2, a)

@lru_cache(None)

def game(h):

if sum(h) >= 77: return 'W'

if any(game(m) == 'W' for m in moves(h)): return 'P1'

if any(game(m) == 'P1' for m in moves(h)): return 'V1'

for s in range(1, 70):

if game((7, s)) == 'V1':

print(s)

break

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

def f(a,b,m):

if a+b>=77:

return m%2==0

if m==0:

return 0

h = [f(a+1,b,m-1),f(a*2,b,m-1),f(a,b+1,m-1),f(a,b*2,m-1)]

return any(h) if (m-1)%2==0 else any(h)

print(min([s for s in range(1,70) if not f(7,s,1) and f(7,s,2)]))

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

def f(k1, k2, hod):

# hod - номер хода. 1 - первый ход Пети, 2 - первый ход Вани, 3 - второй ход Пети, 4 - второй ход Вани

if hod == who_win and k1 + k2 >= win_sum:

# нужный игрок победил на нужном ходе

return 1

elif hod == who_win and k1 + k2 < win_sum:

# нужный игрок не победил на нужном ходе

return 0

elif hod < who_win and k1 + k2 >= win_sum:

# Петя или Ваня победил раньше времени

if ZADANIE != 21:

return 0

elif hod == who_win-2:

# в №21 допускаем победу Вани первым ходом(раньше времени, когда hod == 3)

return 1

# дальше начинается сам ход игрока

# ПРИМЕР: если hod = 3, то выше мы проверили не победил ли Ваня после своего первого хода

# если ещё не победил, тогда уже делаем второй ход Пети

else:

# hod - чётный, значит, сейчас ходит Ваня, иначе(нечёт) Петя

if hod % 2 == 0:

# действия Вани с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 21:

# играем за Ваню, подойдёт любое удобное дейтсвие(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 20:

# играем против Вани, проверяем все его возможные действия(and)

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

else:

# действия Пети с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 20:

# играем против Пети или за Петю, подойдёт любое неудачное/удачное действие Пети(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 21:

# играем против Пети, проверяем все его возможные действия(and) для победы Вани 2ым ходом

if who_win == 5:

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

elif who_win == 3:

# играем против Пети: проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if ((f(k1, k2 + sum2, hod + 1) + f(k1 + sum1, k2, hod + 1) + f(k1, k2 * x2, hod + 1) + f(k1 * x1, k2, hod + 1)) < kol):

return 1

# УСЛОВИЯ ЗАДАЧИ ------------------------------------------------

sum1 = 1 # сколько можно прибавлять в 1ую кучу

sum2 = 1 # сколько можно прибавлять во 2ую кучу

x1 = 2 # во сколько раз можно умножать 1ую кучу

x2 = 2 # во сколько раз можно умножать 2ую кучу

kol = 4 # количество вариантов действий с кучами

k1 = 7 # количество камней в 1ой куче

win_sum = 77 # общая сумма камней от которой начинается победа

k2_max = 69 # максимальное S(количество камней во 2ой куче)

# НОМЕР ЗАДАЧИ --------------------------------------------------

ZADANIE = 19 # для какого задания программа (19, 20 или 21)

if ZADANIE == 19:

# who_win - кто должен выиграть и каким ходом?

who_win = 3 # №19 - Ваня первым ходом

elif ZADANIE == 20:

who_win = 4 # №20 - Петя вторым ходом

elif ZADANIE == 21:

who_win = 5 # №21 - Ваня вторым ходом

for k2 in range(1, k2_max):

if f(k1, k2, 1) == 1:

if ZADANIE == 21:

who_win = 3 # проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if f(k1, k2, 1) == 1:

print(k2)

break

else:

print(k2)

if ZADANIE != 20:

break

20.  

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой  — 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

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

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

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

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

Решение. Из хода решения предыдущего задания можно заключить, что значения S 35 и 36 не подходят, поскольку в этом случае Петя может выиграть своим первым ходом. Рассмотрим значение S  =  34. В этом случае Петя своим первым ходом может добавить в первую кучу один камень и получить кучу (8, 34). После первого хода Вани может возникнуть одна из четырёх позиций: (9, 34), (8, 35), (16, 34), (8, 68). Во всех случаях Петя удваивает количество камней во второй куче и выигрывает своим вторым ходом.

Второе значение S  — 31. При S  =  31 Петя удваивает количество камней в первой куче и получает позицию (14, 31). После первого хода Вани может возникнуть одна из четырёх позиций: (15, 31), (14, 32), (28, 31), (14, 62). Во всех случаях Петя удваивает количество камней во второй куче и выигрывает своим вторым ходом.

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

Ответ: 3134.

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

def f(x, y, h):

if h == 4 and x + y >= 77:

return 1

elif h == 4 and x + y < 77:

return 0

elif x + y >= 77 and h < 4:

return 0

else:

if h % 2 != 0:

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

else:

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

for x in range(1, 70):

if f(x, 7, 1) == 1:

print("Задача 20:", x)

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

def f (k1,k2, m):

if k1+k2 >= 77:

return m%2==0

if m==0:

return 0

h=[f(k1+1, k2, m-1),f(k1, k2+1, m-1), f(k1*2, k2, m-1), f(k1, k2*2, m-1)]

return any(h) if m%2 !=0 else all(h)

print('Задание 20:', (*[s for s in range (1, 70) if f(7,s,3) and not f(7, s, 1)]))

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

def f(k1, k2, hod):

# hod - номер хода. 1 - первый ход Пети, 2 - первый ход Вани, 3 - второй ход Пети, 4 - второй ход Вани

if hod == who_win and k1 + k2 >= win_sum:

# нужный игрок победил на нужном ходе

return 1

elif hod == who_win and k1 + k2 < win_sum:

# нужный игрок не победил на нужном ходе

return 0

elif hod < who_win and k1 + k2 >= win_sum:

# Петя или Ваня победил раньше времени

if ZADANIE != 21:

return 0

elif hod == who_win-2:

# в №21 допускаем победу Вани первым ходом(раньше времени, когда hod == 3)

return 1

# дальше начинается сам ход игрока

# ПРИМЕР: если hod = 3, то выше мы проверили не победил ли Ваня после своего первого хода

# если ещё не победил, тогда уже делаем второй ход Пети

else:

# hod - чётный, значит, сейчас ходит Ваня, иначе(нечёт) Петя

if hod % 2 == 0:

# действия Вани с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 21:

# играем за Ваню, подойдёт любое удобное дейтсвие(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 20:

# играем против Вани, проверяем все его возможные действия(and)

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

else:

# действия Пети с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 20:

# играем против Пети или за Петю, подойдёт любое неудачное/удачное действие Пети(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 21:

# играем против Пети, проверяем все его возможные действия(and) для победы Вани 2ым ходом

if who_win == 5:

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

elif who_win == 3:

# играем против Пети: проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if ((f(k1, k2 + sum2, hod + 1) + f(k1 + sum1, k2, hod + 1) + f(k1, k2 * x2, hod + 1) + f(k1 * x1, k2, hod + 1)) < kol):

return 1

# УСЛОВИЯ ЗАДАЧИ ------------------------------------------------

sum1 = 1 # сколько можно прибавлять в 1ую кучу

sum2 = 1 # сколько можно прибавлять во 2ую кучу

x1 = 2 # во сколько раз можно умножать 1ую кучу

x2 = 2 # во сколько раз можно умножать 2ую кучу

kol = 4 # количество вариантов действий с кучами

k1 = 7 # количество камней в 1ой куче

win_sum = 77 # общая сумма камней от которой начинается победа

k2_max = 69 # максимальное S(количество камней во 2ой куче)

# НОМЕР ЗАДАЧИ --------------------------------------------------

ZADANIE = 20 # для какого задания программа (19, 20 или 21)

if ZADANIE == 19:

# who_win - кто должен выиграть и каким ходом?

who_win = 3 # №19 - Ваня первым ходом

elif ZADANIE == 20:

who_win = 4 # №20 - Петя вторым ходом

elif ZADANIE == 21:

who_win = 5 # №21 - Ваня вторым ходом

for k2 in range(1, k2_max):

if f(k1, k2, 1) == 1:

if ZADANIE == 21:

who_win = 3 # проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if f(k1, k2, 1) == 1:

print(k2)

break

else:

print(k2)

if ZADANIE != 20:

break

21.  

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой  — 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

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

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

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

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

Решение. Такое значение S  — 30. При S  =  30 Петя своим первым ходом может получить одну из четырёх позиций: (7, 31), (8, 30), (14, 30), (7, 60).

В позиции (7, 60) Ваня удваивает количество камней во второй куче и выигрывает своим первым ходом.

Из позиций (14, 30) и (7, 31) Ваня может получить позицию (14, 31). В этом случае после второго хода Пети может возникнуть одна из четырёх позиций: (15, 31), (14, 32), (28, 31), (14, 62). Во всех случаях Ваня удваивает количество камней во второй куче и выигрывает своим вторым ходом.

Из позиции (8, 30) Ваня своим первым ходом может получить позицию (16, 30). После второго хода Пети может возникнуть одна из четырёх позиций: (17, 30), (16, 31), (32, 30), (16, 60). Во всех случаях Ваня удваивает количество камней во второй куче и выигрывает своим вторым ходом.

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

Ответ: 30.

Примечание. Докажем, что при S ≤ 29 либо выигрывает Петя своим первым или вторым ходом, либо игра не завершится за 4 хода.

При S ≤ 7 Петя своим первым ходом может добавить в большую кучу один камень. Тогда, даже если изначально S  =  7, наибольшее количество камней, которое можно получить суммарно в обеих кучах за 4 хода, каждый раз удваивая большую кучу, равняется 71.

При 8 ≤ S ≤ 16 Петя может выбрать такую стратегию, которая не позволит победить Ване за один или два хода. Для этого Петя каждый ход может прибавлять к первой куче один камень. При этом наибольшее суммарное количество камней в обеих кучах, которое можно получить за 4 хода, равно 9 + 64  =  73.

При S  =  17. Петя первым ходом может получить позицию (7, 18). Из этой позиции Ваня может получит позиции (8, 18), (7, 19), (14, 18) и (7, 36). В позиции (7, 36) Петя выигрывает своим вторым ходом. В остальных позициях у Пети есть стратегия, которая позволяет ему получить позиции, из которых Ваня не сможет выиграть своим вторым ходом.

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

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

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

def f(x, y, h):

if (h == 3 or h == 5) and x + y >= 77:

return 1

elif h == 5 and x + y < 77:

return 0

elif x + y >= 77 and h < 5:

return 0

else:

if h % 2 == 0:

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

else:

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

def f1(x, y, h):

if h == 3 and x + y >= 77:

return 1

elif h == 3 and x + y < 77:

return 0

elif x + y >= 77 and h < 3:

return 0

else:

if h % 2 == 0:

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

else:

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

for x in range(1, 70):

if f(x, 7, 1) == 1:

print(x)

print("====")

for x in range(1, 70):

if f1(x, 7, 1) == 1:

print(x)

Приведём решение Михаила Глинского на языке Python.

def f(x,y,n):

if n%2==0 and (x+y)>=77: return 1

if n==4 and (x+y)<77: return 0

if n%2==1 and (x+y)>=77: return 0

else:

if n%2==0: return f(x+1,y,n+1) and f(x*2,y,n+1) and f(x,y+1,n+1) and f(x,y*2,n+1)

if n%2==1: return f(x+1,y,n+1) or f(x*2,y,n+1) or f(x,y+1,n+1) or f(x,y*2,n+1)

for s in range(1,70):

if f(7,s,0):

print(s)

break

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

def f(k1, k2, hod):

# hod - номер хода. 1 - первый ход Пети, 2 - первый ход Вани, 3 - второй ход Пети, 4 - второй ход Вани

if hod == who_win and k1 + k2 >= win_sum:

# нужный игрок победил на нужном ходе

return 1

elif hod == who_win and k1 + k2 < win_sum:

# нужный игрок не победил на нужном ходе

return 0

elif hod < who_win and k1 + k2 >= win_sum:

# Петя или Ваня победил раньше времени

if ZADANIE != 21:

return 0

elif hod == who_win-2:

# в №21 допускаем победу Вани первым ходом(раньше времени, когда hod == 3)

return 1

# дальше начинается сам ход игрока

# ПРИМЕР: если hod = 3, то выше мы проверили не победил ли Ваня после своего первого хода

# если ещё не победил, тогда уже делаем второй ход Пети

else:

# hod - чётный, значит, сейчас ходит Ваня, иначе(нечёт) Петя

if hod % 2 == 0:

# действия Вани с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 21:

# играем за Ваню, подойдёт любое удобное дейтсвие(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 20:

# играем против Вани, проверяем все его возможные действия(and)

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

else:

# действия Пети с кучами (по условию: k1/k2 + 1 и k1/k2 * 2)

if ZADANIE == 19 or ZADANIE == 20:

# играем против Пети или за Петю, подойдёт любое неудачное/удачное действие Пети(or)

return f(k1, k2 + sum2, hod + 1) or f(k1 + sum1, k2, hod + 1) or f(k1, k2 * x2, hod + 1) or f(k1 * x1, k2, hod + 1)

elif ZADANIE == 21:

# играем против Пети, проверяем все его возможные действия(and) для победы Вани 2ым ходом

if who_win == 5:

return f(k1, k2 + sum2, hod + 1) and f(k1 + sum1, k2, hod + 1) and f(k1, k2 * x2, hod + 1) and f(k1 * x1, k2, hod + 1)

elif who_win == 3:

# играем против Пети: проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if ((f(k1, k2 + sum2, hod + 1) + f(k1 + sum1, k2, hod + 1) + f(k1, k2 * x2, hod + 1) + f(k1 * x1, k2, hod + 1)) < kol):

return 1

# УСЛОВИЯ ЗАДАЧИ ------------------------------------------------

sum1 = 1 # сколько можно прибавлять в 1ую кучу

sum2 = 1 # сколько можно прибавлять во 2ую кучу

x1 = 2 # во сколько раз можно умножать 1ую кучу

x2 = 2 # во сколько раз можно умножать 2ую кучу

kol = 4 # количество вариантов действий с кучами

k1 = 7 # количество камней в 1ой куче

win_sum = 77 # общая сумма камней от которой начинается победа

k2_max = 69 # максимальное S(количество камней во 2ой куче)

# НОМЕР ЗАДАЧИ --------------------------------------------------

ZADANIE = 21 # для какого задания программа (19, 20 или 21)

if ZADANIE == 19:

# who_win - кто должен выиграть и каким ходом?

who_win = 3 # №19 - Ваня первым ходом

elif ZADANIE == 20:

who_win = 4 # №20 - Петя вторым ходом

elif ZADANIE == 21:

who_win = 5 # №21 - Ваня вторым ходом

for k2 in range(1, k2_max):

if f(k1, k2, 1) == 1:

if ZADANIE == 21:

who_win = 3 # проверяем, что не при любых ходах Пети, Ваня может выиграть первым ходом

if f(k1, k2, 1) == 1:

print(k2)

break

else:

print(k2)

if ZADANIE != 20:

break

22.  

Ниже на четырех языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.

C++	Python
#include <iostream> using namespace std; int main() {     int x, L, M, Q;     cin >> x;     Q = 9;     L = 0;     while (x >= Q){         L = L + 1;         x = x - Q;     }     M = x;     if (M < L){         M = L;         L = x;     }     cout << L << endl << M << endl;     return 0; }	x = int(input()) Q = 9 L = 0 while x >= Q:     L = L + 1     x = x - Q M = x if M < L:     M = L     L = x print(L) print(M)
Паскаль	Алгоритмический язык
var x, L, M, Q: integer; begin     readln(x);     Q := 9;     L := 0;     while x >= Q do begin         L := L + 1;         x := x - Q;     end;     M := x;     if M < L then begin         M := L;         L := x;     end;     writeln(L);     writeln(M); end.	алг нач     цел x, L, M, Q     ввод x     Q := 9     L := 0     нц пока x >= Q         L := L + 1         x := x - Q     кц     M := x     если M < L         то             M := L             L := x     все     вывод L, нс, M кон

23.  

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

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

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

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

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

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

Траектория вычислений программы  — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

24.  

Текстовый файл состоит не более чем из 10⁶ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.

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

Задание 24

Решение. Для решения данной задачи будем посимвольно считывать текстовый файл. Объявим переменные c1 и c2, которые будут хранить предыдущий символ в файле и текущий. Также объявим переменные k и max. Первая нужна для определения длины каждой последовательности неповторяющихся символов, вторая  — для хранения максимальной длины такой последовательности. Алгоритм будет сравнивать значение текущего символа со значением предыдущего и, если символы не будут повторяться, увеличивать значения счётчика k на 1.

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

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

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

Ответ: 35.

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

Приведём решение Николая Чуркина (Тимашевск) на языке Python.

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

k = 1

m = 0

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

if f[i] != f[i-1]:

k += 1

else:

m = max(m, k)

k = 1

m = max(m, k)

print(m)

Приведём решение Максима Григорьева на языке Python.

from itertools import permutations

with open('24_demo.txt') as f:

s = f.read()

pod = [''.join(x) for x in permutations('XYZ', 2)]

x, counter, c_max = 0, 0, 0

for i in range(len(s)):

if s[i + x:i + 2 + x] in pod:

counter += 1

x = 2

else:

c_max = max(c_max, counter)

counter, x = 0, 0

print(c_max)

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

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

a = ''.join(['*' if s[i]!=s[i-1] else ' ' for i in range(1,len(s))]).split()

print(max(len(x) for x in a)+1)

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

f=open('24_demo.txt').readline()

m = 0

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

for j in range (i+m, len(f)):

c = f[i:j+1]

if all(not x in c for x in['XX','ZZ','YY']):

m = max(m,len(c))

else: break

print(m)

Приведём решение Михаила Глинский на языке Python.

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

s=s.replace('XX','X X').replace('YY','Y Y').replace('ZZ','Z Z')

m=[len(x) for x in s.split()]

print(max(m))

Приведём решение Екатерины Паркаевой на языке С.

#include

int main()

{

FILE *f;

int mk = 0, k = 0;

char s = 'Q', p_s = 'Q';

if((f = fopen(«24_demo.txt", "r")) == NULL)

{

printf("file not open");

return 1;

}

while(!feof(f))

{

if(p_s != s)

k++;

else

{

if(mk < k)

mk = k;

k = 1;

}

p_s = s;

fscanf(f, "%c", &s);

}

fclose(f);

printf("%d", mk);

return 0;

}

Приведём решение Севы Тимофеева на языке С++.

#include

using namespace std;

int main () {

ifstream fin("24_demo.txt");

char a,b;

int s=0;

int f=0;

fin >> a;

while(fin >> a){

if(a != b)f++;

if(f>s)s=f;

if(a == b)f=1 ;

b=a;

    }

   cout << s << endl;

}

25.  

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в два соседних столбца на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке также должны следовать в порядке возрастания.

Например, в диапазоне [5; 9] ровно два различных натуральных делителя имеют числа 6 и 8, поэтому для этого диапазона вывод на экране должна содержать следующие значения:

2 3

2 4

Ответ:

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

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

var

numDel, i, j: longint;

d: array[1..2] of longint;

begin

for i := 174457 to 174505 do begin

numDel := 0;

for j := 2 to i div 2 do begin

if i mod j = 0 then begin

numDel := numDel + 1;

if numDel > 2 then break;

d[numDel] := j;

end;

if numDel = 2 then writeln(d[1], ' ', d[2]);

end;

end.

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

3 58153

7 24923

59 2957

13 13421

149 1171

5 34897

211 827

2 87251

Приведём решение Владимира Лукьянчикова на языке Pascal.

uses school;

begin

for var i := 174457 to 174505 do begin

var w := i.Divisors;

if w.Count = 4 then println(w[1], w[2]);

end;

end.

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

def f(x):

k=2

deliteli=set()

while k * k <= x:

if x % k==0:

deliteli.add(k)

if x // k < x:

deliteli.add(x // k)

k = k + 1

return sorted(deliteli)

start = 174457

end = 174505

for i in range(start, end + 1):

if len(f(i)) == 2:

print(f(i))

Приведём решение Максима Глинских на языке Python.

for x in range(174457,174505+1):

k=0

s=[]

for y in range(2,x//2+1):

if x%y==0:

k+=1

s.append(y)

if k>2:

break

if k==2:

print(*s)

Приведём решение Игоря Орлова на языке PascalABC.NET.

Uses School;
begin
Range(174457,174505).Where(x->x.Divisors.count=4).ForEach(x->Println(x.divisors[1]:3,x.divisors[2]:6))
end.

26.  

Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.

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

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

Задание 26

В первой строке входного файла находятся два числа: S  — размер свободного места на диске (натуральное число, не превышающее 10 000) и N  — количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.

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

Пример входного файла:

100 4

При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов  — 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар  — 50, поэтому ответ для приведённого примера:

2 50

Ответ:

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

f = open('26_demo.txt')

data = f.readlines()

s = data[0].split()

s = int(s[0])

del (data[0]) # первая строка больше не нужна, удаляем ее

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

data[i] = int(data[i])

data = sorted(data)

summa = 0

for count in range(0, len(data)):

if summa + data[count] > s: break

summa += data[count]

print(count)

zapas = s - summa

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

if data[i] - data[count - 1] <= zapas:

itog = data[i]

print(itog)

Ответ: 568  50.

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

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

s = [i for i in open('26_demo.txt').readlines()]

size = int(s[0].split()[0])

files = [int(i) for i in s[1:]]

selectedFiles = []

files = sorted(files) # Список файлов отсортирован от меньших значений к большим значениям

while (size - sum(selectedFiles)) >= files[0]:

selectedFiles.append(files[0])

files = files[1:] # Удаляем из списка файлов выбранный файл

lastFileMaxSize = size - sum(selectedFiles[:-1])

biggestPossibleLastFile = max([file for file in files if file <= lastFileMaxSize])

print(len(selectedFiles), biggestPossibleLastFile)

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

f = open('26_demo.txt')

s,n = list(map(int,f.readline().split()))

files = sorted([int(line) for line in f])

filessum = [files[0]]

for x in files[1:]: filessum.append(filessum[-1]+x)

ndx = max([i for i in range(len(filessum)) if filessum[i] <= s])

freespace = s-filessum[ndx-1]

maxfile = max([x for x in files if x <= freespace])

print(ndx+1,maxfile)

Приведём другое решение.

Сначала считаем в массив данные из файла. После этого отсортируем массив в порядке возрастания. Таким образом, последовательно складывая элементы массива с начала и сравнивая сумму с размером свободного места на диске, получим максимальное количество пользователей, чьи файлы могут поместиться на диске. Далее, вычитая из найденной суммы наибольший файл в текущей последовательности, будем пробовать прибавлять файлы с большим весом. Если такой файл будет найден, то заменяем значение наибольшего файла, который возможно поместить на диск.

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

var 
i, j, t: integer;
a: array [1..1000] of integer;
s: integer;
n: integer;
sum: integer;
maxi: integer;
f: text;
begin
    assign(f,'C:\26.txt');
    reset(f);
    readln(f, s, n);
    for i := 1 to n do readln(f, a[i]);
    for i := 1 to n do
        for j := i + 1 to n do 
            if a[i] > a[j] then begin
                t := a[i];
                a[i] := a[j];
                a[j] := t;
            end;
    sum := 0;
    maxi := 1;
    for i := 1 to n do
        if sum + a[i] <= s then begin
            sum := sum + a[i];
            maxi := i;
        end;
    t := a[maxi];
    for i := maxi to n do
        if ((sum - t) + a[i]) <= s then begin
            sum := sum - t + a[i];
            t := a[i];
        end;
    writeln(maxi, ' ', t);
end.

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

27.  

Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число  — максимально возможную сумму, соответствующую условиям задачи.

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

Файл A

Файл B

Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.

Пример организации исходных данных во входном файле:

1 3

5 12

6 9

5 4

3 3

1 1

Для указанных входных данных значением искомой суммы должно быть число 32.

В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

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

Ответ:

Решение. Последовательно считывая данные из файла, будем прибавлять к сумме максимальное число в паре. Также заметим, что в случае, если получившееся в результате суммирования максимальных чисел во всех парах число будет кратно трём, достаточно будет вычесть из этой суммы минимальную разницу между какими-⁠либо двумя числами. Для этого при считывании пар помимо максимального числа в каждой паре будем искать минимальную разницу среди пар, не кратную трём.

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

var

x, y: longint;

n: longint;

sum: longint;

mindif: longint;

f: text;

begin

assign(f,'C:\27-A.txt');

reset(f);

readln(f, n);

sum := 0;

mindif := 20001;

while not eof(f) do begin

readln(f, x, y);

if x > y then

sum := sum + x

else

sum := sum + y;

if (abs(x - y) < mindif) and (abs(x-y) mod 3 <> 0) then mindif := abs(x-y);

end;

if sum mod 3 <> 0 then

writeln(sum)

else

writeln(sum - mindif);

end.

В результате работы данного алгоритма при вводе данных из файла A ответ  — 127127, из файла B  — 399762080.

Примечание.

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

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

f = open("27-B_demo (2).txt") # для файла A замените название

s = f.readlines()

n = int(s[0]) # количество пар

summi = 0

d = 10**6

for i in range(1, n + 1):

x, y = map(int, s[i].split())

summi += max(x, y)

if abs(x - y) % 3 != 0:

d = min(d, abs(x - y))

if summi % 3 != 0:

print(summi)

else:

print(summi - d)

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

a=[list(map(int,s.split())) for s in open('27-B_demo.txt')][1:]

s=sum([max(x) for x in a])

d=min([abs(x[0]-x[1]) for x in a if (x[0]-x[1])%3!=0])

print(s if s%3!=0 else s-d)

	П1	П2	П3	П4	П5	П6	П7
П1				9			7
П2				5		11
П3						12
П4	9	5			4	13	15
П5				4		10	8
П6		11	12	13	10
П7	7			15	8

№ п/п	№ задания	Ответ
1	27398	9
2	27399	zyxw
3	27400	64
4	27401	100
5	27402	19
6	27403	259
7	27404	16
8	27405	48
9	27406	14
10	27407	1
11	27408	600
12	27409	22
13	27410	24
14	27411	13
15	27412	18
16	27413	4122
17	27414	15687935
18	27415	1204502
19	27416	18
20	27417	3134
21	27418	30
22	27419	49
23	27420	28
24	27421	35
25	27422	3 58153 7 24923 59 2957 13 13421 149 1171 5 34897 211 827 2 87251
26	27423	568 50
27	27424	127127 399762080

	П1	П2	П3	П4	П5	П6	П7
П1				9			7
П2				5		11
П3						12
П4	9	5			4	13	15
П5				4		10	8
П6		11	12	13	10
П7	7			15	8

Демонстрационная версия ЕГЭ−2021 по информатике

Ключ

	П1	П2	П3	П4	П5	П6	П7
П1				9			7
П2				5		11
П3						12
П4	9	5			4	13	15
П5				4		10	8
П6		11	12	13	10
П7	7			15	8