Вход   →

Задание 27 :: Информатика

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

За правильное выполненное задание получишь 4 балла. На решение отводится примерно 55 минут.

Задачи для тренировки

  1. В фи­зи­че­ской ла­бо­ра­то­рии про­во­дит­ся дол­го­вре­мен­ный экс­пе­ри­мент по изу­че­нию гра­ви­та­ци­он­но­го поля Земли. По ка­на­лу связи каж­дую ми­ну­ту в ла­бо­ра­то­рию пе­ре­даётся по­ло­жи­тель­ное целое число – те­ку­щее по­ка­за­ние при­бо­ра «Сигма 2019». Ко­ли­че­ство пе­ре­да­ва­е­мых чисел в серии из­вест­но и не пре­вы­ша­ет 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

  2. По ка­на­лу связи пе­ре­даётся по­сле­до­ва­тель­ность по­ло­жи­тель­ных целых чисел, все числа не пре­вы­ша­ют 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
    Кон­троль прой­ден

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

    За­да­ние А. Име­ет­ся набор дан­ных, со­сто­я­щий из 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 

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

     

    Описание входных и выходных данных

    В первой строке входных данных задаётся количество чисел N (4 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.

    В качестве результата программа должна вывести одно число: количество пар элементов, находящихся в последовательности на расстоянии не меньше чем 4, в которых произведение элементов кратно 29.

     

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

    7

    58

    2

    3

    5

    4

    1

    29

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

    5

     

    Пояснение. Из 7 заданных элементов с учётом допустимых расстояний между ними можно составить 6 произведений: 58 · 4, 58 · 1, 58 · 29, 2 · 1, 2 · 29, 3 · 29. Из них на 29 делятся 5 произведений.

     

    Требуется написать эффективную по времени и по памяти программу для решения описанной задачи.

     

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

     

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

     

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

     

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

     

    Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.

     

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

     

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


    Решение
    Авторизуйтесь, чтобы увидеть решение.
Задание 1. Системы счисления и операции над числами в разных системах счисления Задание 2. Построение и анализ таблиц истинности логических выражений Задание 3. Анализ информационных моделей (таблицы, диаграммы, графики) Задание 4. Поиск информации в базах данных. Файловая система Задание 5. Кодирование и декодирование информации Задание 6. Выполнение, анализ и поиск алгоритмов Задание 7. Электронные таблицы, диаграммы и графики Задание 8. Анализ программ Задание 9. Кодирование и декодирование информации. Передача информации Задание 10. Перебор слов и системы счисления Задание 11. Рекурсивные алгоритмы Задание 12. Компьютерные сети. Адресация в Интернете Задание 13. Вычисление количества информации Задание 14. Выполнение алгоритмов для исполнителя Задание 15. Графы. Поиск количества путей Задание 16. Кодирование чисел. Системы счисления Задание 17. Составление запросов для поисковых систем с использованием логических выражений Задание 18. Преобразование логических выражений Задание 19. Работа с массивами и матрицами в языке программирования Задание 20. Анализ программы, содержащей циклы и ветвления Задание 21. Анализ программы с подпрограммами Задание 22. Оператор присваивания и ветвления. Перебор вариантов Задание 23. Логические уравнения Задание 24. Поиск и исправление ошибок в программе Задание 25. Алгоритмы обработки массивов Задание 26. Выигрышная стратегия Задание 27. Обработка символьных строк, массивов и последовательностей

Еще нет аккаунта?

Пользователям Бингоскул доступна бесплатная подготовка к ЕГЭ по всем видам ФИПИ, просмотр решений и отслеживание статистики
Регистрация

Уже зарегистрированы?

Авторизуйтесь в своей учетной записи, чтобы получить доступ к расширенным возможностям функционала сайта
Вход

Вход в систему

Регистрация

Регистрируясь, я подтверждаю своё согласие с условиями пользовательского соглашения

Активация аккаунта

Спасибо за регистрацию
Мы отправили письмо на указанный электронный адрес.
Чтобы завершить регистрацию, проверьте почтовый ящик и перейдите по ссылке в письме.