Вверх

Линия заданий 27, ЕГЭ по информатике

12227. На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3 (разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 23.

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (3 ⩽ N ⩽ 1000), В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 3, в которых произведение элементов кратно 23.
Пример входных данных:
6
46
2
3
5
4
23
Пример выходных данных для приведённого выше примера входных данных:
5

Пояснение. Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 46 ⋅ 5, 46 ⋅ 4, 46 ⋅ 23, 2 ⋅ 4, 2 ⋅ 23, 3 ⋅ 23. Из них на 23 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, - 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени, - 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, - 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Произведение двух чисел делится на 23, если хотя бы один из сомножителей делится на 23.
При вводе чисел можно подсчитывать количество чисел, кратных 23, не считая 3 последних. Обозначим это количество чисел n23.
Сами числа, кроме 3 последних, при этом можно не хранить.
Очередное считанное число будем рассматривать как возможный правый элемент искомой пары.
Если очередное считанное число делится на 23, то к ответу следует прибавить количество чисел до него, не считая 3 последних (включая считанное).
Если очередное считанное число на 23 не делится, то к ответу следует прибавить n23.
Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на 8 элемента ранее, достаточно хранить только 3 последних элемента или информацию о них.
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12227.

12254. На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4 (разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 19.

Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (4 ⩽ N ⩽ 1000), В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 19.
Пример входных данных:
7
38
2
3
5
4
1
19
Пример выходных данных для приведённого выше примера входных данных:
5

Пояснение. Из шести заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 38 ⋅ 4, 38 ⋅ 1, 38 ⋅ 19, 2 ⋅ 1, 2 ⋅ 19, 3 ⋅ 19. Из них на 19 делятся 5 произведений.
Требуется написать эффективную по времени и памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, - 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени, - 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, - 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет большая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

Произведение двух чисел делится на 19, если хотя бы один из сомножителей делится на 19.
При вводе чисел можно подсчитывать количество чисел, кратных 19, не считая 4 последних. Обозначим их n19.
Сами числа, кроме 4 последних, при этом можно не хранить.
Очередное считанное число будем рассматривать как возможный правый элемент искомой пары.
Если очередное считанное число делится на 19, то к ответу следует прибавить количество чисел до него, не считая 4 последних (включая считанное).
Если очередное считанное число на 19 не делится, то к ответу следует прибавить n19.
Чтобы построить программу, эффективную по памяти, заметим, что, поскольку при обработке очередного элемента входных данных используются значения, находящиеся на 4 элемента ранее, достаточно хранить только 4 последних элемента или информацию о них.
Ниже приведена реализующая описанный алгоритм программа на языке Паскаль (использована версия PascalABC)

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12254.

12281. На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы - это целое неотрицательное число. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это непустое подмножество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), такое, что сумма значений скоростей у него чётна и максимальна среди всех возможных непустых подмножеств с чётной суммой.
Если таких подмножеств несколько, то из них выбирается то подмножество, которое содержит наименьшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 109. Все N чисел различны.

Пример входных данных:
5
123
2
1000
0
10
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.

Пример выходных данных для приведённого выше примера входных данных:
2 3 5

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12281.

12308. На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы - это целое неотрицательное число. Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны. Скорость, по крайней мере, одной частицы нечётна.

При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это непустое подмножество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), такое, что сумма значений скоростей у него нечётна и максимальна среди всех возможных непустых подмножеств с нечётной суммой. Если таких подмножеств несколько, то из них выбирается то подмножество, которое содержит наименьшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество.
Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое неотрицательное число, не превышающее 109. Все N чисел различны. Хотя бы одно из чисел нечётно.

Пример входных данных:
3
123
0
2
Программа должна вывести в порядке возрастания номера частиц, скорости которых принадлежат основному множеству данной серии. Нумерация частиц ведётся с единицы.

Пример выходных данных для приведённого выше примера входных данных:
1 3

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12308.

12335. На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы - это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны.

В серии обязательно присутствует хотя бы одна частица с отрицательной скоростью.
При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое подмножество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является минимальным среди всех возможных подмножеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то берётся то, которое содержит наибольшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя основное множество.
Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество частиц N. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109. Все N чисел различны.

Пример входных данных:
5
123
2
-1000
0
10

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

Пример выходных данных для приведённого выше примера входных данных:
1 2 3 5

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12335.

12362. На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Скорость частицы - это целое число (положительное, отрицательное или 0). Частиц, скорость которых измерена, может быть очень много, но не может быть меньше трёх. Скорости всех частиц различны.

При обработке результатов в каждой серии эксперимента отбирается основное множество скоростей. Это такое непустое множество скоростей частиц (в него могут войти как скорость одной частицы, так и скорости всех частиц серии), для которого произведение скоростей является максимальным среди всех возможных множеств. При нахождении произведения знак числа учитывается. Если есть несколько таких множеств, то основным считается то, которое содержит наибольшее количество элементов.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 1.0), которая будет обрабатывать результаты эксперимента, находя основное множество. Перед текстом программы кратко опишите используемый Вами алгоритм решения задачи. На вход программе в первой строке подаётся количество частиц М. В каждой из последующих N строк записано одно целое число, по абсолютной величине не превышающее 109.

Пример входных данных:
5
123
2
-1000
0
10

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

Пример выходных данных для приведённого выше примера входных данных:
1 2 5

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

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12362.

12389. По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности - наибольшее число R, удовлетворяющее следующим условиям:

1) R - произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 21.

Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: ...
Контроль пройден (или - Контроль не пройден)
Перед текстом программы кратко опишите используемый Вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:
6
70
21
997
7
9
300
21000

Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 21000
Контроль пройден

Произведение двух чисел делится на 21, если:
- один из сомножителей делится на 21 (второй может быть любым) либо
- ни один из сомножителей не делится на 21, причём один из сомножителей делится на 7, а другой - на 3.
Поэтому программа, вычисляющая кодовое число, может работать так. Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:
М7 - самое большое число, кратное 7, но не кратное 3;
M3 - самое большое число, кратное 3, но не кратное 7;
M21 - самое большое число, кратное 21;
МAX - самое большое число среди всех элементов последовательности, отличное от М21 (если число М21 встретилось более одного раза и оно же является максимальным, то MAX = M21).
После того как все данные прочитаны, искомое контрольное значение вычисляется как максимум из произведений М21 · MAX и М7 · М3.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы.
Допускаются решения, записанные на других языках программирования.

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12389.

12416. По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности - наибольшее число В, удовлетворяющее следующим условиям:

1) R - произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел, произведения различных элементов последовательности, равных по величине, допускаются);
2) R делится на 22.
Если такого числа R нет, то контрольное значение полагается равным 0.
В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pasacal 7.0), которая будет проверять правильность контрольного значения. Программа должна напечатать отчёт по следующей форме:
Вычисленное контрольное значение: ...
Контроль пройден (или - Контроль не пройден)
Перед текстом программы кратко опишите используемый вами алгоритм решения.
На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

Пример входных данных:
6
55
997
22
7
9
400
22000

Пример выходных данных для приведённого выше примера входных данных:
Вычисленное контрольное значение: 22000
Контроль пройден

Произведение двух чисел делится на 22, если:
- один из сомножителей делится на 22 (второй может быть любым) либо
- ни один из сомножителей не делится на 22, причём один из сомножителей делится на 2, а другой - на 11.
Поэтому программа, вычисляющая кодовое число, может работать так.
Программа читает все входные данные один раз, не запоминая все данные в массиве. Программа для прочитанного фрагмента входной последовательности хранит значения четырёх величин:
М2 - самое большое чётное число, не кратное 11;
M11 - самое большое число, кратное 11, но не кратное 2;
M22 - самое большое число, кратное 22;
МAX - самое большое число среди всех элементов последовательности, отличное от М22 (если число М22 встретилось более одного раза и оно же является максимальным, то MAX = M22).
После того как все данные прочитаны, искомое контрольное значение вычисляется как максимум из произведений М22 · MAX и М2 · М11.
Ниже приведён пример программы на языке Паскаль, которая реализует описанный алгоритм.
Кроме того, приведён пример программы на языке Бейсик, которая правильно решает задачу, но использует алгоритм, немного отличающийся от описанного выше. Возможны и другие правильные алгоритмы.
Допускаются решения, записанные на других языках программирования.

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12416.

12443. Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 6 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу - 2 балла.
Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 6 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и по используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, - 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но не эффективную по памяти, - 3 балла.
Как в варианте А, так и в варианте Б программа должна напечатать одно число - минимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных вами программ.
Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).
Входные данные
Для варианта А на вход программе подаётся 6 строк, каждая из которых содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта А:
1 3
5 12
4 9
5 4
3 3
1 1
Для варианта Б на вход программе в первой строке подаётся количество пар № (1 ⩽ N ⩽ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта Б:
6
1 3
5 12
4 9
5 4
3 3
1 1
Пример выходных данных для приведённых выше примеров входных данных:
19

Задание Б. Сначала рассмотрим решение для более общего задания (вариант Б).

Решение 1
Чтобы получить минимально возможную сумму, будем брать из каждой пары меньшее число. Если полученная при этом сумма будет делиться на 6, ее необходимо увеличить.
Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 6, заменить ранее выбранное число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 6, получить нужную сумму невозможно.

Программа читает все данные один раз. В каждой паре определяется меньшее число Min и разность между большим и меньшим числами пары D. После обработки очередной пары программа хранит два числа: s - сумму всех минимальных элементов прочитанных пар и D_min - наименьшую возможную разность D, не кратную 6. Окончательным ответом будет значение s, если оно не делится на 6, и s+D_min в противном случае. Если s делится на 6, а D_min не определено (разность между числами во всех парах кратна 6), ответ в соответствии с условиями задачи считается равным 0.

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике
Решение 2.
Возможно и решение, основанное на другой идее. А именно, будем хранить для каждого прочитанного набора пар суммы (s0, s1, s2, s3, s4, s5) - минимальные суммы элементов пар, имеющие при делении на 6 соответственно остатки 0, 1, 2, 3, 4 и 5. При обработке очередной пары (a1, a2) эти суммы обновляются. Для этого достаточно рассмотреть суммы sj+ak для j от 0 до 5 и для k от 1 до 2. Для каждого возможного остатка от деления на 6 выбрать в качестве нового значения sj значение наименьшей из указанных сумм, дающей данный остаток. Окончательным ответом будет меньшая из сумм sj для j больших 0.
Эта идея приводит к более громоздкой реализации, но все основные требования по эффективности в ней выполнены, поэтому подобное решение при отсутствии ошибок можно оценить максимальным количеством баллов.
Ниже приводится пример основанной на этом принципе программы на языке Паскаль.
Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике
Задание А. Это задание можно выполнить «в лоб»: сохранить в массиве все исходные данные, перебрать все возможные способы выбора одного элемента из каждой пары и найти минимальную сумму, соответствующую условиям задачи.

Ниже приводится пример такого решения.
Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12443.

12470. Вам предлагается два задания с похожими условиями: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Задание Б более сложное, его решение оценивается выше. Итоговая оценка выставляется как максимальная из оценок за задания А и Б.

Задание А. Имеется набор данных, состоящий из 6 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 4 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
Максимальная оценка за правильную программу - 2 балла.

Задание Б. Имеется набор данных, состоящий из пар положительных целых чисел.
Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 4 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени и по используемой памяти (или хотя бы по одной из этих характеристик).
Программа считается эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, - 4 балла.
Максимальная оценка за правильную программу, эффективную по времени, но не эффективную по памяти, - 3 балла.
Как в варианте А, так. и в варианте Б программа должна напечатать одно число - минимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных вами программ.
Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).

Входные данные
Для варианта А на вход программе подаётся 6 строк, каждая из которых содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта А:
1 3
5 12
6 9
5 4
3 3
1 1

Для варианта Б на вход программе в первой строке подаётся количество пар N (1 ⩽ N ⩽ 100 000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример входных данных для варианта Б:
6
1 3
5 12
6 9
5 4
3 3
1 1

Пример выходных данных для приведённых выше примеров входных данных:
21

Содержание верного ответа (допускаются иные формулировки ответа, не искажающие его смысла)
Задание Б. Сначала рассмотрим решение для более общего задания (вариант Б).

Решение 1
Чтобы получить минимально возможную сумму, будем брать из каждой пары меньшее число. Если полученная при этом сумма будет делиться на 4, ее необходимо увеличить.
Для этого достаточно в одной из пар, где числа имеют разные остатки при делении на 4, заменить ранее выбранное число на другое число из той же пары. При этом разница между числами в паре должна быть минимально возможной. Если во всех парах оба числа имеют одинаковый остаток при делении на 4, получить нужную сумму невозможно.
Программа читает все данные один раз. В каждой паре определяется меньшее число Min и разность между бо́льшим и меньшим числами пары D. После обработки очередной пары программа хранит два числа: s - сумму всех минимальных элементов прочитанных пар и D_min - наименьшую возможную разность D, не кратную 4. Окончательным ответом будет значение s, если оно не делится на 4, и s+D_min в противном случае. Если s делится на 4, а D_min не определено (разность между числами во всех парах кратна 4), ответ в соответствии с условиями задачи считается равным 0.

Задание ЕГЭ по информатикеЗадание ЕГЭ по информатике
Решение 2
Возможно и решение, основанное на другой идее. А именно, будем хранить для каждого прочитанного набора пар суммы (s0, s1, s2, s3) - минимальные суммы элементов пар, имеющие при делении на 4 соответственно остатки 0, 1, 2 и 3. При обработке очередной пары (a1, a2) эти суммы обновляются. Для этого достаточно рассмотреть суммы sj+ ak для j от 0 до 3 и для k от 1 до 2. Для каждого возможного остатка от деления на 4 выбрать в качестве нового значения sj значение наименьшей из указанных сумм, дающей данный остаток. Окончательным ответом будет меньшая из сумм sj для j больших 0.
Эта идея приводит к более громоздкой реализации, но все основные требования по эффективности в ней выполнены, поэтому подобное решение при отсутствии ошибок можно оценить максимальным количеством баллов.
Ниже приводится пример основанной на этом принципе программы на языке Паскаль.
Задание ЕГЭ по информатикеЗадание ЕГЭ по информатикеЗадание ЕГЭ по информатике
Задание А Это задание можно выполнить «в лоб»: сохранить в массиве все исходные данные, перебрать все возможные способы выбора одного элемента из каждой пары и найти минимальную сумму, соответствующую условиям задачи.
Ниже приводится пример такого решения.
Задание ЕГЭ по информатике

P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 12470.

Для вас приятно генерировать тесты, создавайте их почаще