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

1. ФИПИ № 028200

   Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на k=109 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно.
   Даны два входных файла — файл A и файл B. Каждый файл содержит в первой строке количество троек N (1≤N≤1 000 000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 12 000.
   Для обработки файла B нельзя использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку такая программа будет выполняться слишком долго.

   

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 028200.

2. ФИПИ № 04D7CD

   Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на p=33. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар нет, нужно вывести два нуля.
   В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
   Напишите эффективную по времени и памяти программу для решения задачи. Эффективная по времени программа должна работать за время, не превышающее линейное относительно N. Эффективная по памяти программа должна использовать не более 1 Кбайт памяти, причём объём памяти не должен увеличиваться с ростом N.
   Перед текстом программы кратко опишите алгоритм решения, укажите использованный язык программирования и его версию.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 04D7CD.

3. ФИПИ № 0B12A6

   Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d=120, и по крайней мере одно из чисел пары делится на p=7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
   В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
   Напишите эффективную по времени и памяти программу для решения этой задачи. Опишите алгоритм решения перед текстом программы и укажите использованный язык программирования и его версию. Программа должна использовать не более 1 Кбайт памяти, а её время работы не должно зависеть от параметра d.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 0B12A6.

4. ФИПИ № 195BE6

   На вход программы поступает последовательность из n целых положительных чисел. Рассматриваются все пары элементов последовательности a_i и a_j, такие что i<j и a_i>a_j. Среди пар, удовлетворяющих этому условию, необходимо найти и напечатать пару с максимальной суммой элементов, которая делится на m=120. Если среди найденных пар максимальную сумму имеют несколько, то можно напечатать любую из них.
   В первой строке входных данных задаётся количество чисел n (2≤n≤12 000). В каждой из последующих n строк записано одно целое положительное число, не превышающее 10 000.
   В качестве результата программа должна напечатать элементы искомой пары. Если таких пар несколько, можно вывести любую из них. Гарантируется, что хотя бы одна такая пара в последовательности есть.
   Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при одновременном увеличении количества элементов последовательности n и параметра m в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 килобайта и не увеличивается с ростом n.
   Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 195BE6.

5. ФИПИ № 233FD1

   На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 11.
   В первой строке входных данных задаётся количество чисел N (4≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. В качестве результата программа должна вывести одно число — количество пар элементов, находящихся в последовательности на расстоянии не меньше 4, в которых произведение элементов кратно 11.
   Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
   Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 233FD1.

6. ФИПИ № 267752

   Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d=160, и по крайней мере одно из чисел пары делится на p=7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
   В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
   Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз, а при увеличении параметра d в k раз время работы программы не увеличивается. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N и d.
   Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 267752.

7. ФИПИ № 2931D9

   Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на p=21. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
   В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
   Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время O(N) и использовать объём памяти, не зависящий от N и не превышающий 1 Кбайт.
   Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 2931D9.

8. ФИПИ № 29FE86

   На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 3: разница в индексах элементов пары должна быть 3 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 23.
   В первой строке входных данных задаётся количество чисел N (3≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000. Программа должна вывести одно число — количество подходящих пар.
   Требуется написать эффективную по времени и памяти программу. Программа считается эффективной по времени, если при увеличении N в k раз время её работы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает 1 килобайта и не увеличивается с ростом N.
   Перед текстом программы кратко опишите алгоритм решения, укажите использованный язык программирования и его версию.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 29FE86.

9. ФИПИ № 2C4C01

   На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или больше, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 29.
   В первой строке входных данных задаётся количество чисел N (4≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
   В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше 4, в которых произведение элементов кратно 29.
   Требуется написать эффективную по времени и памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
   Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

   Без автопроверки: ответ проверяет репетитор.

   Источник: ФИПИ, открытый банк, код 2C4C01.

10. ФИПИ № 335BFF

    Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, удовлетворяющие следующим условиям: числа в паре имеют различные остатки от деления на d=200, и по крайней мере одно из чисел пары делится на p=7. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
    В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
    Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время O(N) и использовать объём памяти, не зависящий от N и d. Перед текстом программы кратко опишите алгоритм решения и укажите использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 335BFF.

11. ФИПИ № 37B022

    На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 4: разница в индексах элементов пары должна быть 4 или более, порядок элементов в паре неважен. Необходимо определить количество таких пар, для которых произведение элементов делится на 19.
    В первой строке входных данных задаётся количество чисел N (4≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000.
    В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 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. Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 37B022.

12. ФИПИ № 391438

    На спутнике «Восход» установлен прибор, предназначенный для измерения солнечной активности. В течение времени эксперимента прибор каждую минуту передаёт в обсерваторию положительное целое число, не превышающее 1000, — количество энергии солнечного излучения, полученной за последнюю минуту, измеренное в условных единицах.
    После окончания эксперимента передаётся контрольное значение — наибольшее число R, удовлетворяющее следующим условиям: R — произведение двух чисел, переданных в разные минуты; R делится на 26.
    Предполагается, что удовлетворяющее условиям контрольное значение существовало в момент передачи. В результате помех при передаче как сами числа, так и контрольное значение могут быть искажены.
    Напишите эффективную по времени и используемой памяти программу, которая будет проверять правильность контрольного значения. Программа эффективна по времени, если время её работы пропорционально количеству полученных показаний прибора N. Программа эффективна по памяти, если размер памяти, использованной для хранения данных, не зависит от N и не превышает 1 килобайта.
    Если вычисленное контрольное значение существует, программа должна вывести его и сообщить, пройден ли контроль. Если определить удовлетворяющее условию контрольное значение невозможно, выводится только фраза «Контроль не пройден».
    На вход программе в первой строке подаётся количество чисел N≤100 000. В каждой из последующих N строк записано одно положительное целое число, не превышающее 1000. В последней строке записано переданное контрольное значение.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 391438.

13. ФИПИ № 559E69

    На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на 74.
    В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10000.
    В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 74.
    Пример входных данных:
    4
    2
    6
    37
    111
    Пример выходных данных для приведённого выше примера входных данных:
    4
    Из четырёх заданных чисел можно составить 6 попарных произведений: 2⋅6, 2⋅37, 2⋅111, 6⋅37, 6⋅111, 37⋅111. Из них на 74 делятся 4 произведения: 2⋅37=74, 2⋅111=222, 6⋅37=222, 6⋅111=666.
    Требуется написать эффективную по времени и по памяти программу. При увеличении количества исходных чисел N в k раз время работы программы должно увеличиваться не более чем в k раз. Память, необходимая для хранения всех переменных программы, не должна превышать 1 килобайта и не должна увеличиваться с ростом N.
    Перед текстом программы необходимо кратко описать алгоритм решения, указать использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 559E69.

14. ФИПИ № 5D03DA

    Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна и, по крайней мере, один из элементов делится на p=27. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
    В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
    Напишите эффективную по времени и памяти программу для решения этой задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
    Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 5D03DA.

15. ФИПИ № 6A6558

    На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности, находящихся на расстоянии не меньше чем 5 (разница в индексах элементов пары должна быть 5 или более, порядок элементов в паре неважен). Необходимо определить количество таких пар, для которых произведение элементов делится на 17.
    В первой строке входных данных задаётся количество чисел N (5≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
    В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 5, в которых произведение элементов кратно 17.
    Пример входных данных:
    8
    34
    2
    3
    5
    4
    6
    7
    17
    Пример выходных данных для приведённого выше примера входных данных:
    5
    Пояснение: из восьми заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 34⋅6, 34⋅7, 34⋅17, 2⋅7, 2⋅17, 3⋅17. Из них на 17 делятся 5 произведений.
    Требуется написать эффективную по времени и памяти программу. Время работы должно быть не более линейным по N, а память для хранения переменных не должна превышать 1 килобайта и не должна увеличиваться с ростом N.
    Перед текстом программы обязательно кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 6A6558.

16. ФИПИ № 6FF647

    На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100. Каждая из следующих N строк имеет формат: <Фамилия> <Имя> <оценки>, где <Фамилия> — строка длиной не более 20 символов, <Имя> — строка длиной не более 15 символов, а <оценки> — три целых числа, соответствующие оценкам по пятибалльной системе. Все части строки разделены одним пробелом. Требуется написать программу, которая выводит фамилии и имена трёх лучших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трёх лучших, следует вывести также их фамилии и имена. Требуемые имена и фамилии можно выводить в произвольном порядке.
    Пример входной строки: Иванов Петр 4 5 4

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 6FF647.

17. ФИПИ № 7BD738

    Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах по крайней мере одно из чисел пары делится на 17. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
    В первой строке входных данных задаётся количество чисел N (2≤N≤10000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10000.
    Напишите эффективную по времени и памяти программу для решения этой задачи. Программа должна работать за время O(N) и использовать объём памяти, не зависящий от N и не превышающий 1 Кбайт. Перед текстом программы кратко опишите алгоритм решения и укажите использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 7BD738.

18. ФИПИ № 8180D7

    На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на 6.
    В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
    Программа должна вывести одно число — количество пар, в которых произведение элементов кратно 6.
    Пример входных данных:
    4
    2
    10
    3
    15
    Пример выходных данных: 4.
    Из четырёх заданных чисел можно составить 6 попарных произведений. На 6 делятся произведения 2⋅3, 2⋅15, 10⋅3 и 10⋅15.
    Требуется написать эффективную по времени и по памяти программу. Программа считается эффективной по времени, если при увеличении N в k раз время её работы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память для хранения всех переменных не превышает 1 килобайта и не увеличивается с ростом N.
    Перед текстом программы необходимо кратко описать алгоритм решения и указать использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 8180D7.

19. ФИПИ № 8F1330

    Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах хотя бы одно из чисел делится на 19. Порядок элементов в паре неважен. Среди всех таких пар требуется найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар нет, необходимо вывести два нуля.
    В первой строке входных данных задаётся количество чисел N (2≤N≤10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
    Напишите эффективную по времени и памяти программу для решения задачи. Эффективная по времени программа должна работать за время, не превышающее линейное относительно N. Память, необходимая для хранения всех переменных программы, не должна превышать 1 Кбайт и не должна увеличиваться с ростом N.
    Перед текстом программы кратко опишите алгоритм решения и укажите использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 8F1330.

20. ФИПИ № 902B84

    На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности: элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен. Необходимо определить количество пар, для которых произведение элементов делится на 26.
    В первой строке входных данных задаётся количество чисел N (1≤N≤1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
    В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
    Пример входных данных:
    4
    2
    6
    13
    39
    Пример выходных данных для приведённого выше примера входных данных:
    4
    Из четырёх заданных чисел можно составить 6 попарных произведений: 2⋅6, 2⋅13, 2⋅39, 6⋅13, 6⋅39, 13⋅39. Из них на 26 делятся 4 произведения: 2⋅13=26, 2⋅39=78, 6⋅13=78, 6⋅39=234.
    Требуется написать эффективную по времени и по памяти программу для решения описанной задачи. Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз. Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
    Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.

    Без автопроверки: ответ проверяет репетитор.

    Источник: ФИПИ, открытый банк, код 902B84.

Темы номера

• Алгоритмы и исполнители — 17 заданий
• Массивы и строки — 9 заданий