Этот документ был составлен в эпоху, когда на ACMP было 700 задач. Уже не 500, но ещё не 1000.

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

Оставляю его здесь для истории.

Как выбрать задачу на acmp.ru

Более тонкая классификация первых задач с https://acmp.ru, чем представлена у них. Больше нужна преподавателям, чем детям.

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

Начиная с задач второй полусотни, я мог ошибаться, так что замечания приветствуются. На данный момент последняя разобранная задача — «Турист».

1. Задачи для начинающих.

1.1 До циклов

Ввод-вывод и чуть-чуть арифметики

Задачи, где не нужно зать if, while, for и деление с остатком. Умеем только немножко считать и выводить всякие-разные ответы.

• A+B, Эния, Два бандита, Журавлики,

Неглухой телефон, Игра.

• Бисер, Следующее и предыдущее.

Хитрая арифметика

Задачи которые решаются чистой арифметикой, но по сложности идут с большим отрывом. Ученикам 4-7 класса эти задачи могут показаться трудными.

Арифметическая прогрессия, Головоломка про ферзей, Болты и гайки, Сумма, Пицца

Одно условие и больше ничего

Больше-меньше, Арифметика, Баскетбол

Переполнение типа

Пять ю пять

Остатки и одно условие

Торт, Цветочки

Если предыдущие две задачи идут туго, то можно начать с Остатки 2 и Остатки 3.

Четырёхзначный палиндром, Счастливый билет

Если палиндром и счастливый билет вызывают только вопрос «А чё ваще», то можно начать с Цифры-1, Цифры-2 и Цифры-3.

Целочисленное деление

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

Ремонт, Лиса Алиса и кот Базилио, Принц и дракон

Арифметика + геометрия + простые условия

Внеземные гости, Длина отрезка, Количество участников олмпиады, Метро

Несколько условий или составные условия

Зарплата, Золотой песок, День программиста, Коробки, Симметрия, Очередь, Турист

Геометрия Две окружности, Треугольник 3

Конечно, деление на геометрию и не-геометрию весьма условное. Вот Коробки — это геометрия или нет?

Квадратные уравнения

К сведению преподавателей, квадратные уравнения изучают где-то в конце первого семестра восьмого класса. Загадка, Лестница

1.2 Циклы и массивы

Циклы (или рекурсия) без массивов

Решение по сути получается за O (1), но на вывод нужен цикл.

Разбиение на части

Решение получается в один проход, сохранять входные данные в памяти не нужно. Сами догадайтесь, где O (N), а где O (logN).

Конечные автоматы, Бинарные числа, НОД, Монетки, Автобусная экскурсия, Единицы, Кругляши, Числа Фибоначчи, Дороги, Временной ключ, Числа Фибоначчи — 2, Делимость на 11, Постоянная Капрекара, Последняя цифра A^B

В задаче Последняя цифра A^B содержится глубокая идея, отличающая эту задачу от остальных в этом ряду. Возможно её нужно будет вынести в отдельный раздел. Может показаться, что тут нужно быстрое возведение в степень, но мне кажется, что быстрое возведение тут не требуется.

Посики максимума и минимума поставлю пока отдельно, хотя они ничем не отличаются кроме того, что про них можно сказать, что это задача на поиск максимума или минимума.

Арбузы, Перепись, Сбор черники, Лентяй

Задачи на поиск самых длинных цепочек.

Оттепель

Геометрия

Суслик и собака

Поиск делителей

Гадание, Преобразование многоклеточных

Циклы O (N) + массив

Разворот, NEERC, Налоги

Следующие задачи — это O (N * M), где N — длина массива, а M — размер других данных, поданных на вход. Я их перечисляю здесь, потому что они по своей сути являются задачами на O (N), а не на O (N^2).

Подмассив массива

Строки на выход O (1)

Можно поспорить, конечно, константно ли решение Числа Е и Клавиатуры. Здесь я считаю, что 26 — это не 100, и если заведомо известно что N < 26, значит O (N<26) превращается в O (1).

Число E, Клавиатура

Строки на вход

O (1): Клетки, В одном шаге от счастья, Номера автобусов, Нули.

O (1) с отрывом: Шахматы, Дом — Школа — Дом

O (N): Напёрстки, Детали, Левая рекурсия, Лифт, Стрелки, Табло

Различные манипуляции со строками

O (N): ACM World Finals

Цикл в цикле

Переборные задачи:

Уравнение

2. N^2-сортировки и другие O (N^2) операции на массивах

N^2 задачи

Кризисный бизнес, Задача Иосифа Флавия

Посложнее

Сортировка времени

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

O (N*M)

Морской бой — 2

Дополнение

Остатки

Остатки 2

На вход даётся целое число. Нужно написать YES, если оно чётное, и NO, если оно нечётное.

Остатки 3

На вход даётся целое число. Нужно написать YES, если оно делится на 3, и NO, если оно не делится на 3.

Цифры 1

На вход даётся натуральное число. Нужно вывести его последнюю цифру.

Например:

1234 -> 4
23   -> 3
5    -> 5

Цифры 2

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

Например:

1234 -> 123
23   -> 2
5    -> 0

Цифры 3

На вход даётся натуральное число. Нужно вывести его предпоследнюю цифру

Например:

1234 -> 3
23   -> 2
5    -> 0