27. Обработка массивов, символьных строк и последовательностей

Демонстрационный вариант ЕГЭ 2018 – задание №27 На вход программы поступает последовательность из 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 (результаты: 12, 26, 78, 78, 234, 507). Из них на 26 делятся 4 произведения (2·13=26; 2·39=78; 6·13=78; 6·39=234).
Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну программу или две программы решения задачи (например, одна из программ может быть менее эффективна). Если Вы сдадите две программы, то каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы обязательно кратко опишите алгоритм решения.
Укажите использованный язык программирования и его версию.


Демонстрационный вариант ЕГЭ 2017 г. – задание №27

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

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

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

Как в варианте А, так и в варианте Б программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).
НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

Перед текстом программы кратко опишите Ваш алгоритм решения, укажите использованный язык программирования и его версию (например, Free Pascal 2.6.4).

Входные данные
Для варианта А на вход программе подаётся шесть строк, каждая из которых содержит два натуральных числа, не превышающих 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
Пример выходных данных для приведённых выше примеров входных данных:
32


Демонстрационный вариант ЕГЭ 2016 г. – задание №27

В фи­зи­че­ской ла­бо­ра­то­рии про­во­дит­ся дол­го­вре­мен­ный экс­пе­ри­мент по изу­че­нию гра­ви­та­ци­он­но­го поля Земли. По ка­на­лу связи каж­дую ми­ну­ту в ла­бо­ра­то­рию пе­ре­даётся по­ло­жи­тель­ное целое число – те­ку­щее по­ка­за­ние при­бо­ра «Сигма 2015». Ко­ли­че­ство пе­ре­да­ва­е­мых чисел в серии из­вест­но и не пре­вы­ша­ет 10 000. Все числа не пре­вы­ша­ют 1000. Вре­ме­нем, в те­че­ние ко­то­ро­го про­ис­хо­дит пе­ре­да­ча, можно пре­не­бречь.

Не­об­хо­ди­мо вы­чис­лить «бета-зна­че­ние» серии по­ка­за­ний при­бо­ра – ми­ни­маль­ное чётное про­из­ве­де­ние двух по­ка­за­ний, между мо­мен­та­ми пе­ре­да­чи ко­то­рых про­шло не менее 6 минут. Если по­лу­чить такое про­из­ве­де­ние не удаётся, ответ счи­та­ет­ся рав­ным –1.

Вам пред­ла­га­ет­ся два за­да­ния, свя­зан­ных с этой за­да­чей: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру.

Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние – 0 бал­лов.

За­да­ние Б яв­ля­ет­ся усложнённым ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме.

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

ОБЯ­ЗА­ТЕЛЬ­НО ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем ЗА­ДА­НИЯ А. Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А – 2 балла.

Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты

про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству по­лу­чен­ных по­ка­за­ний при­бо­ра N, т.е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз.

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.

Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния и крат­ко опи­ши­те ис­поль­зо­ван­ный ал­го­ритм.

ОБЯ­ЗА­ТЕЛЬ­НО ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем ЗА­ДА­НИЯ Б. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти, – 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти, – 3 балла. НА­ПО­МИ­НА­ЕМ! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.

Вход­ные дан­ные пред­став­ле­ны сле­ду­ю­щим об­ра­зом. В пер­вой стро­ке задаётся число N – общее ко­ли­че­ство по­ка­за­ний при­бо­ра. Га­ран­ти­ру­ет­ся, что N > 6. В каж­дой из сле­ду­ю­щих N строк задаётся одно по­ло­жи­тель­ное целое число – оче­ред­ное по­ка­за­ние при­бо­ра.

При­мер вход­ных дан­ных:
11
12
45
5
3
17
23
21
20
19
18
17

Про­грам­ма долж­на вы­ве­сти одно число – опи­сан­ное в усло­вии про­из­ве­де­ние либо –1, если по­лу­чить такое про­из­ве­де­ние не удаётся.

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


ЕГЭ 16.06.2016 по информатике. Основная волна. Вариант 41 (Часть С)

На вход даны пары чисел. Нужно вы­брать из каж­дой пары по од­но­му числу так, чтобы сумма всех вы­бран­ных чисел не была крат­на 6 и при этом была ми­ни­маль­но воз­мож­ной. На­пи­ши­те про­грам­му, вы­во­дя­щую такую сумму на экран. Если же ее не­воз­мож­но по­лу­чить, вы­ве­ди­те 0.

Вам пред­ла­га­ет­ся два за­да­ния, свя­зан­ных с этой за­да­чей: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б. Если ре­ше­ние од­но­го из за­да­ний не пред­став­ле­но, то счи­та­ет­ся, что оцен­ка за это за­да­ние — 0 бал­лов.

За­да­ние Б яв­ля­ет­ся усложнённым ва­ри­ан­том за­да­ния А, оно со­дер­жит до­пол­ни­тель­ные тре­бо­ва­ния к про­грам­ме.

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

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния А. Мак­си­маль­ная оцен­ка за вы­пол­не­ние за­да­ния А — 2 балла.

Б. На­пи­ши­те про­грам­му для ре­ше­ния по­став­лен­ной за­да­чи, ко­то­рая будет эф­фек­тив­на как по вре­ме­ни, так и по па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик). Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству по­лу­чен­ных по­ка­за­ний при­бо­ра N, т.е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если раз­мер па­мя­ти, ис­поль­зо­ван­ной в про­грам­ме для хра­не­ния дан­ных, не за­ви­сит от числа N и не пре­вы­ша­ет 1 ки­ло­бай­та.

Перед про­грам­мой ука­жи­те вер­сию языка про­грам­ми­ро­ва­ния и крат­ко опи­ши­те ис­поль­зо­ван­ный ал­го­ритм.

Обя­за­тель­но ука­жи­те, что про­грам­ма яв­ля­ет­ся ре­ше­ни­ем за­да­ния Б. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти, — 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти, — 3 балла.

На­по­ми­на­ем! Не за­будь­те ука­зать, к ка­ко­му за­да­нию от­но­сит­ся каж­дая из пред­став­лен­ных Вами про­грамм.

За­да­ча А. Ко­ли­че­ство пар из­вест­но за­ра­нее и равно 6. Числа не пре­вы­ша­ют 30 000.

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

5 4

3 2

1 1

18 3

11 12

2 5

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

23

За­да­ча Б. Ко­ли­че­ство пар N не из­вест­но за­ра­нее и может при­ни­мать зна­че­ния 2 <= N <= 200 000. На вход по­да­ет­ся сна­ча­ла ко­ли­че­ство пар, затем сами пары. Числа по мо­ду­лю не пре­вы­ша­ют 30 000.

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

6

5 4

3 2

1 1

18 3

11 12

2 5

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

23


В некотором вузе абитуриенты проходили предварительное тестирование, по результатам которого они могут быть допущены к сдаче вступительных экзаменов в первом потоке. Тестирование проводится по трём предметам, по каждому предмету абитуриент может набрать от 0 100 баллов. При этом к сдаче экзаменов в первом потоке допускаются абитуриенты, набравшие по результатам тестирования не менее 30 баллов по каждому из трёх предметов, причём сумма баллов должна быть не менее 140. На вход программы подаются сведения о результатах предварительного тестирования. Известно, что общее количество участников тестирования не превосходит 500.

В первой строке вводится количество абитуриентов, принимавших участие в тестировании, N. Далее следуют N строк, имеющих следующий формат:

<Фамилия> <Имя> <Баллы>

Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов, <Баллы> – строка, содержащая два целых числа, разделенных пробелом – баллы, полученные на тестировании по каждому из трёх предметов. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом. Пример входной строки:

Романов Вельямин 48 39 55

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


В соревнованиях по многоборью (из M видов спорта) участвуют N спортсменов (N < 1000) . На вход программе в первой строке подается число спортсменов N, во второй – число видов спорта M. В каждой из последующих N строк находится информация в следующем формате:

<Фамилия> <Имя> <Баллы>

где <Фамилия> – строка, состоящая не более, чем из 20 символов без пробелов, <Имя> – строка, состоящая не более, чем из 12 символов без пробелов, <Баллы> – M целых чисел, обозначающие количество баллов, набранных спортсменом в каждом из видов многоборья.

<Фамилия> и <Имя>, <Имя> и <Баллы>, а также отдельные числа в поле <Баллы> разделены ровно одним пробелом. Пример входных строк:

3

4

Иванов Сергей 100 30 78 13

Петров Антон 90 16 98 14

Сидоров Юрий 100 70 30 21

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

В данном случае программа должна вывести

Иванов Сергей 221 1

Сидоров Юрий 221 1

Петров Антон 218 2


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

Каждая стро­ка файла ко­ди­ру­ет­ся отдельно.

В каж­дой стро­ке ищут­ся от­дель­ные слова, и все сим­во­лы слова сдви­га­ют­ся по ал­фа­ви­ту цик­ли­че­ски впра­во на длину слова.

Словом счи­та­ет­ся любая по­сле­до­ва­тель­ность под­ряд иду­щих сим­во­лов ла­тин­ско­го алфавита, строч­ных и прописных.

Циклический сдвиг сим­во­ла по ал­фа­ви­ту впра­во на X — за­ме­на сим­во­ла на символ, сто­я­щий в ал­фа­ви­те на X по­зи­ций дальше. Если при этом про­ис­хо­дит выход за пре­де­лы алфавита, счёт на­чи­на­ет­ся с на­ча­ла алфавита.

Пример цик­ли­че­ско­го сдви­га сим­во­лов на 3 позиции: буква «Е» пре­вра­ща­ет­ся в букву «Н», буква «t» — в букву «w» буква «Y» — в букву «В».

Напишите эффективную, в том числе и по ис­поль­зу­е­мой памяти, про­грам­му (укажите ис­поль­зу­е­мую вер­сию языка программирования, на­при­мер Borland Pascal 7.0), ко­то­рая долж­на за­ко­ди­ро­вать стро­ку по ука­зан­но­му алгоритму.

На вход про­грам­ме по­да­ет­ся строка, со­сто­я­щая из не более чем 250 сим­во­лов ла­тин­ско­го алфавита, пробелов, зна­ков препинания, раз­но­го рода скобок, ка­вы­чек и дру­гих символов. Стро­ка за­кан­чи­ва­ет­ся сим­во­лом «#». Дру­гих сим­во­лов «#» в стро­ке нет.

Программа долж­на вы­ве­сти за­ко­ди­ро­ван­ную по ука­зан­но­му ал­го­рит­му строку.

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

Day, mice. «Year» — a mistake#

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

Gdb, qmgi. «Ciev» — b tpzahrl#

3304 просмотров