Лицей ФТШ > Задания по программированию для 2025a

Задания по программированию для 2025a

Дополнительные задачи

Алгоритм Евклида и вокруг него.

И ещё задачи для тех, кто всё решил.

Задачи на «условный оператор».

А ещё линейные алгоритмы на массивах

Жадность навсегда

Дополнительные задачи по массивам (контест 152), условия задач

Критерии: задачи A-F (2/4/6), дата сдачи: 13.02.2024

Критерии: задачи G-K (2/3/5), дата сдачи: 20.02.2024

Критерии: задачи L-M (1/1/2), дата сдачи: 05.03.2024 (тройка ставится, если в решении любой из задач используется вещественная арифметика)

Критерии: задачи N-W (4/6/8 из которых обязательно V), дата сдачи: 09.04.2024

Критерии: задачи X-ZN (6/8/11 из которых обязательны ZJ, ZK), дата сдачи: 23.04.2024

37. Динамическое программирование

Вход в контест (контест 179)

Условия задач. Во всех задачах обязательно писать комментарий с описанием того, что хранится в массиве (массивах), использующихся в "динамике" (см. пример).

Критерии: задачи A-D (2/3/4), дата сдачи: 09.01.2024

Критерии: задачи E-I (2/3/4), дата сдачи: 16.01.2024

За решение задач J, K, L – отдельные оценки.

Критерии: задачи M-R (2/3/4), дата сдачи: 31.01.2024

За решение задач S, T, U – отдельные оценки.

36. Решение задач: разные темы

Вход в контест (контест 178)

Условия внутри контеста (ссылка "Statement" или "Условия"), вопросы по условиям задач можно задавать в контесте.

35. Игра Letter-Boxed

Правила игры и что надо сделать.

До 19.12.2023 прислать (tg, почта) программу, которая умеет решать игру для длины слов не менее 4 и длины последовательности слов не более 5.

34. Рекурсивный перебор

Вход в контест (контест 177)

Условия задач.

Критерии: задачи A, C, E, F, G, R, любая из JKLM (2/4/6), дата сдачи: 31.10.2023

Прежде чем приступать к решению задачи Letter-Boxed очень полезно написать программу для задачи перебора всех позиций ферзей, не бьющих друг друга на квадратной доске.

33. Бинарный (двоичный) поиск

Вход в контест (контест 173)

Условия задач.

Критерии: Задачи A-F (3/4/5), дата сдачи: 28.09.2023

Критерии: Задачи G-M (2/3/4), дата сдачи: 28.09.2023

33. Решение задач

Вход в контест (решение задач) (контест 175)

ОГЭ по информатике

Тем, кто собирается сдавать ОГЭ по информатике предлагаю изучить демонстрационнный вариант.

Вариант задания (pdf, 747 KB), файлы для выполнения заданий 11-14 (zip, 87.6 MB).

Инструкция по использованию:

прочтите текст заданий, убедитесь, что вы понимаете все слова;
попробуйте выполнить задания;
найдите в файле таблицу с верными ответами и проверьте свои результаты;
найдите в файле критерии оценивания задач с развёрнутым ответом и проверьте свои ответы по этим критериям

Правила проведения экзамена: ссылка

Сайт с официальными материалами.

32. Решение задач: массивы и рекурсия

Вход в контест (решение задач: массивы и рекурсия) (контест 174)

31. Новая игра

Правила игры и полезная информация

Файл содержит описание игры и то, что от вас ожидается. Файл получен из pdf прибавлением к каждому байту единицы по модулю 256.

Разберитесь, как устроено чтение и запись бинарных (binary) файлов. Напишите программу, которая восстанавливает pdf-файл и выполните задание.

Обратите внимание, что в файле две страницы. Имеет смысл посмотреть сразу обе.

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

До 18 мая надо написать первую стратегию, которая способна играть и почти никогда не проигрывать заведомо нелогичному игроку.

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

Почитать про случайность и алгоритмы: В.А. Успенский "Четыре алгоритмических лица случайности"

30. Игра "Быки и коровы"

Правила игры и полезная информация

К 13.04.2023 напишите базовые версии обеих вариантов игры. Лучше в двух разных файлах.

29. Классы (рациональные числа)

Вход в контест (контест 172)

Условия задач.

Критерии: Задачи A-F (3/4/6), дата сдачи: 09.03.2023 21:59:59

Критерии: Задачи G-M (3/4/5), дата сдачи: 23.03.2023 21:59:59

Пример нулевой задачи с методом __str__ и заготовками конструктора и перегрузки (overload) арифметических операций.

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

(для кругозора) John Horton Conway, разное

John Horton Conway, Look-and-Say последовательность (осторожно, спойлеры!).

28. Перебор (без рекурсии)

Вход в контест (контест 171)

Условия задач.

Критерии (часть 1, задачи A-E) 2/3/5, дата сдачи: 02.02.2023 21:59:59

Пример решения задачи A.
Обратите внимание — код самой программы для многих задач почти не меняется. Цикл, перебирающий последовательности один и тот же, только функции find() и next() разные.

Критерии (часть 2, задачи F-H) 1/2/3, дата сдачи: 09.02.2023 21:59:59

Критерии (часть 3, задачи I-M) 1/2/3, дата сдачи: 16.02.2023 21:59:59

Критерии (часть 4, задачи N-Q) 1/2/3, дата сдачи: 23.02.2023 21:59:59

Дополнительно (часть 5, задачи R-W), хорошие оценки за решения с комментариями, дата сдачи: когда угодно

27. Морской бой

Вход в контест (контест 170)

Условия задач.

Критерии: 5/10/12, дата сдачи: 25.01.2023 21:59:59

26. Нетранзитивные игры: Penney game

Правила игры и что писать.

25. Решение задач: функции, функции, функции

Вход в контест (python) (контест 168)

Тексты программ для скачивания: A, B, C, D, E

Вход в контест (cpp) (контест 169)

Тексты программ для скачивания: A, B, C, D, E

Как можно смотреть содержимое сложных структур данных.

Для этого есть библиотека pprint (Pretty Printing). Она входит в стандартный комплект при инсталляции Python. В этой библиотеке есть одноимённая функция (pprint). Использовать её очень просто:

from pprint import pprint # пусть у вас есть словарь d, достаточно большой и в одну строчку при обычном print всё не влезает pprint(d)

24. Частотный анализ английского текста

Скачайте файлы:

shakespeare.txt (5459 kB)
scott.txt (1127 kB)
dickens.txt (1946 kB)
joyce.txt (1537 kB)
melville.txt (1247 kB)
churchill.txt (954 kB)
conan_doyle.txt (594 kB)

Инструкция
Решение (copy/paste вашего кода) сдавать сюда (контест 167).
За работу будет две оценки: за сделанное на уроке и за доделанное к вечеру 04.12.2022.

23. Решение задач: строки, файлы, сортировка, множества

Вход в контест (контест 166)

22. Множества, словари

Вход в контест по множествам и словарям (контест 165)

Условия задач.

Критерии: часть 1 (A-J) 3/5/8, дата сдачи: 23:59:59 23.10.2022

Критерии: часть 2 (K-Z) 5/9/12, дата сдачи: 23:59:59 27.11.2022

21. Использование сортировки, встроенная сортировка

Вход в контест по сортировкам (контест 163)

Условия задач.

Критерии: часть 1 (A-J) 3/5/8, дата сдачи: 23:59:59 29.09.2022

Критерии: часть 2 (K-U) 3/5/8, дата сдачи: 23:59:59 23.10.2022 (обратите внимание — срок сдачи по второй части продлён).

20. Вспомнить всё.

Вход в контест (контест 164)

Условия задач.

Критерии следующие: 3/4/5, дата сдачи: 23:59:59 14.09.2022

19. Выигрыватель в Wordle

Код написанный на уроке.

18. List comprehension (генераторы массивов)

Вход в контест по массивам (пишем коротко) (контест 162)

Условия задач.

Критерии следующие:

3/5/8, дата сдачи: 24.05.2022 23:59:59

17. Прикручиваем генерацию комбинаторных объектов к игре nerdle

Изучите пример кода, разберитесь что выводят и как работают обе функции.

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

16. Слова, числа, операции...

Напишите одну из игр:

wordle - программа загадывает слово, предлагает ввести попытку (слово из словаря) и пишет её результат (придумайте удобный формат записи результата);
nerdle - то же самое, но загадывается корректное арифметическое выражение из (например) 7 символов, содержащее цифры и знаки операций +, - и * (можно не поддерживать ввод унарных "+" и "-");
nerdle, но не разрешаются незначащие нули;
nerdle, но со скобками;
nerdle, но известен также результат вычислений этого выражения и в качестве попыток принимаются только строки, при вычислении которых получается нужный результат;
nerdle, но после выражения следует знак равенства и результат вычисления арифметического выражения.

Если вы написали игру, в которую понятно как играть, пришлите по почте файл с программой Михаилу Эдуардовичу и Роману Валерьевичу.

Письмо должно быть выслано обоим адресатам. Файл с программой должен быть приложен к письму.

Только 5-буквенные слова из Wordle (eng) (74 kB)

Существительные (eng) (54 kB)

Все слова (eng) (4750 kB)

15. Самостоятельная работа (19.04.2022)

Вход в контест (контест 154)

14. Вещественная арифметика

Вход в контест по вещественной арифметике (контест 161)

Условия задач.

Критерии следующие:

задачи A-J, 4/6/8, дата сдачи: 12.04.2022 23:59:59

задачи K-R, 3/5/8, дата сдачи: 19.04.2022 23:59:59

13. Двумерные массивы

Вход в контест по двумерным массивам (контест 160)

Условия задач.

Критерии следующие (обновлено!): 9/14/18, дата сдачи: 05.04.2022 23:59:59

12. Рекурсия

Вход в контест по рекурсии (контест 159)

Условия задач.

Критерии следующие: 5/7/10, дата сдачи: 22.02.2022 23:59:59

Материалы online-урока 01.02.2022:

Ученики ФТШ (сейчас)

Ученики ФТШ (за все годы)

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

Заготовка программы для кодирования шифром Цезаря

11. Работа с файлами

Вход в контест по файлам (контест 153)

Условия задач.

Задач сдаются в два этапа. Критерии следующие:

Задачи A-L: 5/6/9, дата сдачи: 01.02.2022 23:59:59

Задачи M-X: 4/6/8, дата сдачи: 08.02.2022 23:59:59

10. КР по циклам

Вход в контест (контест 155)

9. Сортировки (продолжение)

Вход в контест по сортировкам (контест 158)

Условия задач. На этой неделе вам предлагается решать только задачи I, J.

Критерии следующие: J/I,J/I,J (чисто сделанные)

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

Если вы не сдали ни одной задачи, вы получаете 2.
Если вы сдали только задачу J (разобранную на уроке), вы получаете 3.
Если вы сдали задачи I и J, вы получаете 4. Решение задачи I это тоже сортировка. Она так же, как и shaker-sort умеет сортировать за линейное время, используя особенности хранящихся в массиве данных. Придумайте алгоритм сами, это несложно.
Самое интересное: за что же ставят 5? В этом ДЗ оценка 5 ставится за обе задачи (I, J), решённые достаточно "чисто". Не должно быть лишних переменных. Те, что используются, должны быть понятно названы. Не пишите if flag == True (лучше дайте ей понятное название и пишите if smth_happened:).
Посылки можно делать, как обычно, много раз. Проверять ваши решения на стиль мы будем в конце недели. Решайте задачи самостоятельно! Напишите код, за который не будет стыдно!
Если у вас есть вопросы по стилю, обращайтесь к преподавателям.

Дата сдачи: 23:59:59 19.01.2022

8. Сортировки

Вход в контест по сортировкам (контест 158)

Условия задач. Пока вам предлагается решать только задачи A-E.

Критерии следующие: 2/3/5

Дата сдачи: 23:59:59 12.01.2022

7. Массивы

Вход в контест по массивам (контест 151)

Условия задач

Критерии следующие: 5/7/10

Дата сдачи (1 часть, задачи A-M): 23:59:59 23.12.2021

Пример кода, иллюстрирующего разницу во времени работы методов insert и append. Полезно подумать, что и как там работает, вы уже почти всё знаете. А можно просто запустить.

6.5. Задачи из пройденных тем, для ознакомления с тестирующей системой

Этот контест не на оценку! Это просто милые задачи, не только из контестов, которые вы уже решали на informatics.mccme.ru.

Вход в контест "Вспомнить всё" (контест 150)

Условия задач

Для общего развития (1)

Обзорное видео, посвящённое клеточным автоматам. Самый известный клеточный автомат — игру "Жизнь" придумал американский математик Джон Конвей, про которого вообще полезно почитать.

6. Строки и циклы

Вход в контест по строкам.

Критерии следующие: 5/7/10

Дата сдачи: 23:59:59 08.12.2021

Разные замечания:

В приведённом примере кода показано, как проверять функции на затрачиваемое время работы.
Задача такая: в строке надо посчитать сумму натуральных чисел, которые там встречаются. Например, в строке "следующее число после 7 это 8" сумма равна 15, а для строки "45pwd27" сумма равна 72.
В файле есть две функции: f_fast() и f_slow(). Код ниже "гоняет" эти функции на тестовых строках разной длины и измеряет время запуска.
Медленная функция работает за время, пропорциональное квадрату длины строки.

5. Функции

Вход в контест по функциям.

Критерии следующие: 5/7/10

Дата сдачи: ~~23:59:59 25.11.2021~~ продлено до 23:59:59 27.11.2021

Разные замечания:

Считать действительное число можно так:
x = float(input())
А, например, пару действительных чисел вот так:
x, y = map(float, input().split())
Уравнение окружности с центром в точке с координатами (A, B) и радиусом, равным R выглядит так:
(x - A)² + (y - B)² = R²
Если в этом выражении заменить знак равенства на знак "<" или ">", то получится условие того, что точка лежит внутри или снаружи окружности соответственно.
Логические функции (т.е. возвращающие логическое значение True или False) должны возвращать именно логическое значение, а не строку "YES"/"NO". Даже если именно такую строку надо вывести в качестве ответа.
Пишите так:
def is_negative(x):
    return x < 0

x = int(input())
if is_negative(x):
    print("YES")
else:
    print("NO")
"Функция, возвращающая кортеж" — это функция, возвращающая два значения (например, return a, b). В задаче H это просто числитель и знаменатель сокращённой дроби.
В той же задаче для эффективного вычисления НОД стоит воспользоваться таким его свойством: НОД(a, b) = НОД(b, a % b)

4. Задание на строки, срезы и методы строк

Вход в контест по строкам.

ВНИМАНИЕ: во всех задачах этого контеста нельзя использовать циклы. Также обращайте внимание на ограничения, указанные в условии некоторых задач, например запрет на использование метода count.

Если вы сделали задачу, она прошла все тесты, но вместо статуса OK вы сейчас видите "Ошибка оформления кода", это означает, что вы:

Невнимательно прочитали условие задачи
Не прочитали два предложения парой строчек выше (после неприметного слова ВНИМАНИЕ)

Критерии следующие: 5/9/11

Дата сдачи: 23:59:59 18.11.2021

Документация по методам строк

3. Задание по циклу while

Вот.

Критерии следующие: 6/9/12

Дата сдачи: 23:59:59 11.11.2021

2. Задание по условному оператору и циклу for

Вход в контест по if и for.

Критерии следующие: 5/7/10 из задач A-L (условный оператор) и 2/3/6 из задач M-S (цикл for)

Дата сдачи: 23:59:59 27.10.2021

С жутким опозданием и извинениями выкладываем "секретный" способ прочитать несколько (на самом деле совершенно неважно сколько именно) целых чисел, записанных в одну строку через пробел.

Например, в задаче про прямоугольники (задача I) это делается так:

	x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())

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

1. Задание по целочисленной арифметике

Вход в контест по целочисленной арифметике.

Внимание! Все задачи решаются только с использованием ввода/вывода и целочисленных операций +, -, *, //, % и **. Решения, нарушающие это ограничение, приниматься не будут.

Критерии следующие: 6/9/14 задач на 3/4/5 соответственно. Дата сдачи: 23:59:59 14.10.2021 (то есть у вас есть пара в школе, чтобы порешать и позадавать вопросы и время дома).

Тестирующая система и вердикты

Описание вердиктов тестирующей системы

Что ставить и в чём писать программы

Для установки Python и сред программирования (выбирайте нужный вариант для вашей версии операционной системы):

Интерпретатор Python — нужен, чтобы вы могли запускать программы на Python. Вам нужна версия 3, из Stable releases (стабильных), а не pre-releases.

Тепреь программы, которые рекомендуется использовать для набора программ на Python.

VS Code
PyCharm Educational
Sublime Text
Wing IDE
IDLE (Integrated Development and Learning Environment) Python
Thonny (это среда, вместе с которой ставится и сам интерпретатор Python)

VS Code и SublimeText используются не только для набора программ на Python, но и на большинстве современных языков программирования. Преимущество VS Code в том, что он бесплатный. Оба имеют кучу настроек всего чего угодно, при этом есть хорошая документация. Не говоря о том, что ответы на большинство вопросов получаются поиском.

IDLE — это стандартный редактор, поставляемый вместе с Python. Простенький, но надёжный.

Все среды программирования (VS Code, PyCharm, SublimeText и Thonny) умеют запускать код "внутри себя". Но это требует некоторой настройки этой среды.

Вне зависимости от того, в каком редакторе вы пишете текст программы на Python, вы всегда можете запустить её в консоли (на Маке - в терминале) при помощи команды вида

"путь_к_python.exe\python.exe путь_к_вашему_файлу_с_программой\ваш_файл_с_программой"

Например, так:

c:\Python37\python.exe c:\prog\01-int\G.py

Если вы сможете настроить пути для запуска Python из текущей папки, где находится ваша программа, запускать можно будет так:

python G.py

Способ запуска в консоли это самый непосредственный способ "общения" с интерпретатором, без посредников. Если при запуске программы произошла ошибка, её текст будет показан в консоли.

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

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

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

Тестовое задание

Вход в контест.

Домашнее задание по системам счисления (сдать на листочке)

Домашнее задание по системам счисления.

Домашнее задание номер 2 по булевой алгебре (на листочке)

1) Рассмотрим ваш номер мобильного телефона без кода города. Рассмотрим булеву функцию f(a, b, c) со следующей таблицей истинности:

a	b	c	f(a, b, c)
0	0	0	0
0	0	1	остаток 1-й цифры вашего телефона по модулю 2
0	1	0	остаток 2-й цифры вашего телефона по модулю 2
0	1	1	остаток 3-й цифры вашего телефона по модулю 2
1	0	0	остаток 4-й цифры вашего телефона по модулю 2
1	0	1	остаток 5-й цифры вашего телефона по модулю 2
1	1	0	остаток 6-й цифры вашего телефона по модулю 2
1	1	1	остаток 7-й цифры вашего телефона по модулю 2

Запишите эту таблицу истинности на листочек, и запишите функцию f(a, b, c) в виде как можно более короткой формулы, используя любые пройденные нами операторы.

2) Изучите эту таблицу истинности пяти функций f₀, f₁, f₂, f₃, f₄:

a	b	f₀(a, b)	f₁(a, b)	f₂(a, b)	f₃(a, b)	f₄(a, b)
0	0	0	0	0	0	0
0	1	0	0	0	0	1
1	0	0	0	1	1	0
1	1	0	1	0	1	0

Поймите, что теоретически можно выписать всего 16 разных булевых фунций, от f₀ до f₁₅. Сделайте очень широкую таблицу истинности, в которую запишите таким образом все 16 возможных функций.

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

Например, f₃(a, b) = a.

Домашнее задание по булевой алгебре (на листочке)

Домашнее задание по булевой алгебре.

Дополнительные задачи

40. Вращение освещаемого многогранника в трёхмерном пространстве

39. Решение задач

38. Вычислительная геометрия

37. Динамическое программирование

36. Решение задач: разные темы

35. Игра Letter-Boxed

34. Рекурсивный перебор

33. Бинарный (двоичный) поиск

33. Решение задач

ОГЭ по информатике

32. Решение задач: массивы и рекурсия

31. Новая игра

30. Игра "Быки и коровы"

29. Классы (рациональные числа)

(для кругозора) John Horton Conway, разное

28. Перебор (без рекурсии)

27. Морской бой

26. Нетранзитивные игры: Penney game

25. Решение задач: функции, функции, функции

Как можно смотреть содержимое сложных структур данных.

24. Частотный анализ английского текста

23. Решение задач: строки, файлы, сортировка, множества

22. Множества, словари

21. Использование сортировки, встроенная сортировка

20. Вспомнить всё.

19. Выигрыватель в Wordle

18. List comprehension (генераторы массивов)

17. Прикручиваем генерацию комбинаторных объектов к игре nerdle

16. Слова, числа, операции...

15. Самостоятельная работа (19.04.2022)

14. Вещественная арифметика

13. Двумерные массивы

12. Рекурсия

Материалы online-урока 01.02.2022:

11. Работа с файлами

10. КР по циклам

9. Сортировки (продолжение)

8. Сортировки

7. Массивы

6.5. Задачи из пройденных тем, для ознакомления с тестирующей системой

Для общего развития (1)

6. Строки и циклы

Разные замечания:

5. Функции

Разные замечания:

4. Задание на строки, срезы и методы строк

3. Задание по циклу while

2. Задание по условному оператору и циклу for

1. Задание по целочисленной арифметике

Тестирующая система и вердикты

Что ставить и в чём писать программы

Тестовое задание

Домашнее задание по системам счисления (сдать на листочке)

Домашнее задание номер 2 по булевой алгебре (на листочке)

Домашнее задание по булевой алгебре (на листочке)