aoklyunin/ege-py

Java решения заданий ЕГЭ

Объяснения лежат здесь

Задания взяты с сайта Константина Полякова.

Java Исходники решений

С++ Исходники решений

Задание 1

Пример 1

(№ 4145) (Е. Джобс) На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. В таблице в левом столбце указаны номера пунктов, откуда совершается движение, в первой строке – куда. Определите длину дороги между пунктами А и Б, если известно, что длина дороги между Г и Д меньше длины дороги между Г и Е. Передвигаться можно только по указанным дорогам.

Ответ: 10

Исходник

Пример 2

Р-09. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Известно, что длина кратчайшего пути из пункта А в пункт Ж не больше 15. Определите, какова длина кратчайшего пути из пункта Д в пункт В. В ответе запишите целое число – так, как оно указано в таблице.

Ответ: 19

Исходник

Пример 3

Р-10 (демо-2021). На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.

Ответ: 9

Исходник

Пример 4

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.

Ответ: 20

Исходник

Пример 5

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице.

Ответ: 46

Исходник

Пример 6

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.

Ответ: 17

Исходник

Пример 7

Между населёнными пунктами A, B, C, D, E, F, Z построены дороги с односторонним движением. В таблице указана протяжённость каждой дороги. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет. Например, из A в B есть дорога длиной 4 км, а из B в A дороги нет.

Сколько существует таких маршрутов из A в Z, которые проходят через 6 и более населен-ных пунктов? Пункты A и Z при подсчете учитывать. Два раза проходить через один пункт нельзя.

Ответ: 6

Исходник

Пример 8

Р-04. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Ответ: 23

Исходник

Пример 9

Р-03. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Ответ: 9

Исходник

Задания для самостоятельного выполнения

Задание 2

Пример 1

Логическая функция F задаётся выражением

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

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

?	?	?	?	F
0	0	0	1	0
0	1	0	1	0
0	1	1	1	0

Ответ: x y z w

Исходник

Пример 2

Логическая функция F задаётся выражением

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

?	?	?	?	F
1		1		1
0	1		0	1
	1	1	0	1

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

Ответ: z y x w

Исходник

Пример 3

Логическая функция F задаётся выражением

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

?	?	?	?	F
	0	0	1	1
1	1	0	0	1
0			1	1

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

Ответ: z y w x

Исходник

Пример 4

Логическая функция F задаётся выражением

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

?	?	?	?	F
0	1	1	1	1
0	1	0		1
0	1	0		1

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

Ответ: x w z y

Исходник

Пример 5

Логическая функция F задаётся выражением

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

?	?	?	?	F
1			1	0
			1	0
1		1		1

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

Ответ: y x z w

Исходник

Задания для самостоятельного выполнения

Задание 5

Пример 1

Автомат обрабатывает натуральное число N по следующему алгоритму:

1. Строится двоичная запись числа N.
2. Удаляются первая слева единица и все следующие непосредственно за ней нули. Если после этого в числе не остаётся цифр, результат этого действия считается равным нулю.
3. Полученное число переводится в десятичную запись.
4. Новое число вычитается из исходного, полученная разность выводится на экран.

Пример: дано число N = 11. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1011.
2. Удаляется первая единица и следующий за ней ноль: 11.
3. Десятичное значение полученного числа 3.
4. На экран выводится число 11 – 3 = 8.

Сколько разных значений будет показано на экране автомата при последовательном вводе всех натуральных чисел от 500 до 5000?

Ответ: 256, 512, 1024, 2048, 4096

Исходник

Пример 2

Учитель предлагает детям три цифры. Ученики должны сначала найти сумму первой и второй цифр, потом – сумму второй и третьей цифр. Затем полученные числа записываются друг за другом в порядке невозрастания (правое число меньше или равно левому).

Пример. Исходные цифры: 6, 3, 9. Суммы: 6 + 3 = 9; 3 + 9 = 12.

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

1. 1915

2. 1815

3. 188

4. 1518

Ответ: 2

Исходник

Пример 3

Автомат получает на вход четырёхзначное натуральное число и строит новое число по следующему алгоритму:

1. вычисляются суммы первой и второй, второй и третьей и третьей и четвёртой цифр;

2. из полученных сумм отбрасывается наименьшая;

3. остальные записываются в порядке неубывания.

Пример: исходное число: $1284$. Суммы: 1 + 2 = 3; 2 + 8 = 10; 8 + 4 = 12. Отбрасывается наименьшая сумма 3. Результат: 1012. Укажите наименьшее и наибольшее число, при вводе которого автомат выдаёт значение 511.

*Ответ: максимальное число равно 9232, минимальное - 1056

Исходник

Пример 4

Автомат получает на вход два двузначных шестнадцатеричных числа. В этих числах все цифры не превосходят цифру 6 (если в числе есть цифра больше 6, автомат отказывается работать). По этим числам строится новое шестнадцатеричное число по следующим правилам.

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

Пример. Исходные числа: 66, 43. Поразрядные суммы: A, 9. Результат: 9A.

Определите, какое из следующих чисел может быть результатом работы автомата.

1. 9F

2. 911

3. 42

4. 7A

Исходник

Задания для самостоятельного выполнения

Задание 8

Пример 1

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

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

Сколько различных кодовых слов может использовать Игорь?

Ответ: 48

Исходник

Пример 2

Маша составляет шестибуквенные слова перестановкой букв слова КАПКАН. При этом она избегает слов с двумя подряд одинаковыми буквами. Сколько различных кодов может составить Маша?

Ответ: 84

Исходник

Пример 3

Маша составляет 5-буквенные коды из букв В, У, А, Л, Ь. Каждую букву нужно использовать ровно 1 раз, при этом буква Ь не может стоять на первом месте и перед гласной. Сколько различных кодов может составить Маша?

Ответ: 60

Исходник

Пример 4

Все 4-буквенные слова, составленные из букв К, Л, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:

2. КККК

3. КККЛ

4. КККР

5. КККТ

   ...

Запишите слово, которое стоит на 67-м месте от начала списка.

Ответ: ЛККР

Исходник

Задания для самостоятельного выполнения

Задание 12

Пример 1

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

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

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

нашлось (v)

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

Дана программа для исполнителя Редактор:

    НАЧАЛО
    ПОКА нашлось (2222) ИЛИ нашлось (8888)
        ЕСЛИ нашлось (2222)
        ТО заменить (2222, 88)
        ИНАЧЕ заменить (8888, 22)
        КОНЕЦ ЕСЛИ
    КОНЕЦ ПОКА
    КОНЕЦ

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

Ответ: 22

Исходник

Пример 2

В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции:

Длина(a) – возвращает количество символов в строке a. (Тип «целое») Извлечь(a,i) – возвращает i-тый (слева) символ в строке a. (Тип «строка») Склеить(a,b) – возвращает строку, в которой записаны сначала все символы

строки a, а затем все символы строки b. (Тип «строка»)

Значения строк записываются в одинарных кавычках (Например, a:='дом'). Фрагмент алгоритма:

i := Длина(a)
k := 2
b := 'А'
пока i > 0
    нц
    c := Извлечь(a,i)
    b := Склеить(b,c)
    i := i – k
    кц
b := Склеить(b,'Т')

Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’?

1. ‘АДЕПТ’

2. ‘АДЗЕОП’

3. ‘АДТЕТПТ’

4. ‘АДЕОТ’

Ответ: 1)

Исходник

Задания для самостоятельного выполнения

Задание 14

Пример 1

Значение арифметического выражения: 49^7 + 7^{21} – 7 – записали в системе счисления с основанием 7. Сколько цифр $6$ содержится в этой записи?

Ответ: 13.

Исходник

Пример 2

Сколько значащих нулей в двоичной записи числа

4^{512} + 8^{512} – 2^{128} – 250

Ответ: 519.

Исходник

Пример 3

Запись числа 381_{10} в системе счисления с основанием N оканчивается на 3 и содержит 3 цифры. Укажите наибольшее возможное основание этой системы счисления N.

Ответ: 18.

Исходник

Задания для самостоятельного выполнения

Задание 15

Пример 1

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

\lnot ДЕЛ(x,А)\Rightarrow (ДЕЛ(x,6)\Rightarrow \lnot ДЕЛ(x,9))

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

Ответ: 18.

Исходник

Пример 2

Укажите наименьшее целое значение А, при котором выражение

(5k + 6n \gt 57) \lor ((k \leq A) \land (n \lt A))

истинно для любых целых положительных значений k и n.

Ответ: 10.

Исходник

Пример 3

На числовой прямой даны отрезки $A = [70; 90]$, $B = [40; 60]$ и $C =[0; N]$ и функция

$$ F(x) = (\lnot (x \in A) \Rightarrow (x \in B) ) \land (\lnot (x \in C) \Rightarrow (x \in A) ) $$

При каком наименьшем числе N функция F(x) истинна более чем для 30 целых чисел x?

Ответ: 49.

Исходник

Пример 4

Введём выражение $M & K$, обозначающее поразрядную конъюнкцию $M$ и $K$ (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число a, такое что выражение

( x & 125 \ne 1) \lor ((x & 34 = 2) \rightarrow (x & a = 0))

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

Ответ: 4.

Исходник

Задания для самостоятельного выполнения

Задание 16

Пример 1

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

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

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

F(n) = 2* F(n–2), если n нечётно.

Чему равно значение функции F(24)? Для выполнения задания можно также написать программу или воспользоваться редактором электронных таблиц.

Ответ: 2074.

Исходник

Пример 2

Определите, сколько символов * выведет эта процедура при вызове F(22):

def F( n ):
  print('*')
  if n >= 1:
    print('*')
    F(n-1)
    F(n-2)
    F(n-3)

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

Ответ: 1957585.

Исходник

Задания для самостоятельного выполнения

Задание 17

Пример 1

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

Ответ: 1568 7935

Исходник

Задания для самостоятельного выполнения

Задания 19-21

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.

Задание 19

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

Ответ: 18

Исходник

Задание 20

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

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

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

Ответ: 31 34

Исходник

Задание 21

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

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

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

Исходник

Ответ: 30

Пример 2

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

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

Задание 19

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

Ответ: 13

Исходник

Задание 20

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

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

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

Ответ: 21 24

Исходник

Задание 21

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

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

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

Исходник

Ответ: 20

Задания для самостоятельного выполнения

Задания для самостоятельного выполнения

Задание 22

Получив на вход число x, этот алгоритм печатает два числа: L и M.

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)

Исходник

Ответ: 30

Задания для самостоятельного выполнения

Пример 1

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 2

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

Исходник

Ответ: 28

Пример 2

Исполнитель М17 преобразует число на экране. У исполнителя есть три команды, которым присвоены номера:

1. Прибавить 1
2. Прибавить 2
3. Умножить на 3

Первая команда увеличивает число на экране на 1, вторая – увеличивает его на 2, а третья – умножает его на 3. Программа для исполнителя М17 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 12 и при этом траектория вычислений содержит числа 8 и 10?

Исходник

Ответ: 60

Пример 3

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:

1. Прибавить 1
2. Умножить на 2

Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 2 результатом является число 29 и при этом траектория вычислений содержит число 14 и не содержит числа 25?

Исходник

Ответ: 13

Задания для самостоятельного выполнения

Задание 24

Пример 1

Текстовый файл 24.txt состоит не более чем из $10^6$ символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны. Для выполнения этого задания следует написать программу.

Исходник

Ответ: 35

Пример 2

В текстовом файле k8.txt находится цепочка из символов, в которую могут входить заглавные буквы латинского алфавита A...Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Для каждой цепочки максимальной длины выведите в отдельной строке сначала символ, из которого строится эта цепочка, а затем через пробел – длину этой цепочки.

Исходник

Ответ: 10

Пример 3

Текстовый файл 24-157.txt состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита A...Z. Определите максимальное количество идущих подряд символов, среди которых нет сочетания стоящих рядом букв P и R (в любом порядке).

Исходник

Ответ: 2940

Пример 4

В текстовом файле k7-9.txt находится цепочка из символов латинского алфавита A, B, C, D, E. Найдите максимальную длину цепочки вида ABCABC... (составленной из фрагментов ABC, последний фрагмент может быть неполным).

Исходник

Ответ: 35

Задания для самостоятельного выполнения

Файлы для задач

Задание 25

Пример 1

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

Исходник

Ответ:

2 87251
3 58153
5 34897
7 24923
13 13421
59 2957
149 1171
211 827

Пример 2

Среди чисел, больших 520000, найти такие, сумма всех делителей которых, не считая единицы и самого числа, образует число-палиндром (например, число 1221: если его «перевернуть», получается то же самое число). Вывести первые пять чисел, удовлетворяющих вышеописанному условию, справа от каждого числа вывести его максимальный делитель.

Исходник

Ответ:

520211 16781
520993 47363
521653 47423
521947 16837
522077 22699

Пример 3

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

Исходник

Ответ:

800120 400062
800253 266754
800273 21666
800375 160080
800396 400200

Задания для самостоятельного выполнения

Задание 26

Пример 1

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

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

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

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

100 4
80
30
50
40

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

2 50

Ответ: 8176 29

Исходник

Пример 2

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

Входные данные представлены в файле 26-59.txt следующим образом. В первой строке входного файла находится одно число: N – количество занятых мест (натуральное число, не превышающее 10 000). В следующих N строках находятся пары чисел: ряд и место выкупленного билета, не превышающие 100000. В ответе запишите два целых числа: номер ряда и наименьший номер места из найденных в этом ряду подходящих пар.

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

10
5 5
5 9
5 6
16 9
16 3
16 6
20 23
20 28
20 35
20 40

В данном примере есть следующие свободные места, удовлетворяющие условию: 7 и 8 в ряду 5, 4 и 5 в ряду 16, а также 7 и 8 в ряду 16. Выбираем наибольший номер ряда: 16 и наименьший номер места: 4. В ответе нужно указать: 16 4.

Исходник

Ответ: 20164 63

Пример 3

Начинающему админу Ване для тренировки выдали аппарат для сварки оптоволокна и N кусков оптоволокна, из которых попросили получить цельные куски по M метров. С целью снижения затухания сигнала в полученном кабеле нужно минимизировать количество сварок. Да и работы меньше. Укажите в ответе два числа: сколько всего сварок будет в цельных кусках и сколько останется кусков, из которых не сварить цельный кусок требуемой длины. Ваня выбирал куски строго по уменьшению длины, за исключением последнего, который выбирался исходя из минимизации длины каждого обрезка. Обрезок идет обратно в пучок кусков для следующего использования.

Входные данные представлены в файле 26-57.txt следующим образом. В первой строке входного файла записаны значения N (количество кусков оптоволокна) и M (длина необходимого цельного куска). Каждая из следующих N строк содержит одно целое число – длину очередного куска.

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

10 30
17 
15 
14 
12 
11 
8 
6 
5 
4 
2

Сперва взяли 17 и 14, обрез 1 обратно в кучу [15,12,11,8,6,5,4,2,1] – одна сварка. Затем взяли 15,12 и 4, обрез длиной 1 обратно в кучу [11,8,6,5,2,1,1] – две сварки. И затем взяли 11,8,6 и 5, ровно 30, без обреза – три сварки. Итого: 6 сварок и 3 оставшихся куска оптоволокна.

Ответ: 9833 167

Исходник

Задания для самостоятельного выполнения

Файлы для задач

Задание 27

Пример 1

Дана последовательность из N натуральных чисел. Рассматриваются все её непрерывные подпоследовательности, такие что сумма элементов каждой из них кратна k = 43. Найдите среди них подпоследовательность с максимальной суммой, определите её длину. Если таких подпоследовательностей найдено несколько, в ответе укажите количество элементов самой короткой из них.

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

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

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

7
1
3
4
93
8
5
95

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

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

Исходник

Пример 2

В файле записана последовательность натуральных чисел. Гарантируется, что все числа различны. Рассматриваются всевозможные непустые подмножества, состоящие из элементов последовательности. Необходимо найти количество подмножеств, в которых сумма элементов кратна 12.

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

Даны два входных файла (файл Файл A и файл Файл B), каждый из которых содержит в первой строке количество пар $N (1 \leq N \leq 100000)$. Каждая из следующих N строк содержит одно натуральное число, не превышающих $10^6$.

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

4
5
7
12
23

Для указанных данных можно выбрать следующие подмножества: {12}; {5, 7}; {5, 7, 12}. Программа должна вывести количество этих множеств – 3. В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Ответ: 87375 93824992247807

Исходник

Пример 3

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

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

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

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

3
7 4
11 9
5 23

Для указанных входных данных значением искомой суммы должно быть число 36 (выбраны числа 4, 9 и 23, их сумма 36 делится на 6). В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.

Ответ: 108444 401536398

Исходник

Пример 4

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

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

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

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

Ответ: 267 1619987709

Исходник

Задания для самостоятельного выполнения

Файлы для задач