Этапы решения программистских задач олимпиадного т

Этапы решения программистских задач олимпиадного типа

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

Первое, с чего хочу начать, что такое программистская задача олимпиадного типа?
Программистская задача олимпиадного типа (ПЗОТ) предназначена для проведения алгоритмической подготовки учащихся и подготовки к участию в программистских олимпиадах. К ПЗОТ относятся как, собственно, олимпиадные задачи, так и задачи для решения на занятиях и самостоятельной работы. Очевидно, что граница между ними весьма условная.
Решением ПЗОТ является компьютерная программа, созданная на одном из языков программирования.

Правильность решения определяется тестированием программы, сданной учеником, по авторским тестам (прошу прощения за тавтологию).
ПЗОТ состоит из следующих составных частей:

1. Условие задачи.
Текст, в случае необходимости снабжённый рисунками.
 
2. Формат входных данных, выходных данных и их ограничения.
Надо внимательно смотреть, сколько данных, в каком порядке они вводятся и выводятся данные, каким интервалам принадлежат.

3. Один или несколько авторских тестов.
Тест состоит из 2-х разделов: входные данные и выходные данные.

4. Предельное время на прохождение одного теста.

Ниже приведён алгоритм работы ученика, решающего ПЗОТ:

1. Внимательно прочесть условие и постараться понять. Перечитать повторно.
Это кажется простым только с первого раза. Чтению текстов и их пониманию нужно всерьёз учиться.

2. Письменно (!) проверить авторские тесты и убедиться в их правильности.
Это очень важный этап. Проверка тестов ведёт к пониманию алгоритма решения.
(Для работы с ПЗОТ совершенно необходимы бумага и ручка. Если это происходит на занятии, лучше работать с тетрадью, где копится много полезной информации. На олимпиаде дают листы бумаги, но ручку надо иметь свою. Отсутствие этого важного инструмента может помешать успешному решению).

3. Составить свою полную систему тестов, которой должно быть достаточно для проверки ПЗОТ.
Ни в коем случае нельзя полагаться лишь на авторские тесты. Они не обязаны покрывать все возможные частные алгоритмические случаи.
Система тестов, составленная учеником, должна быть, с одной стороны, как можно меньше, но, с другой стороны, учитывать все возможные случаи. В том числе и по размеру входных данных. Часто длинные данные требуют более совершенного алгоритма.
Часто именно во время составления тестов приходит идея решения задачи!

4. Создать (написать и отладить) программу.
Напомню, что в случае ПЗОТ, в отличие от проектной работы, гарантируются корректные входные данные. Не надо делать то, что называется «защитой от дурака», это будет лишней тратой времени.
Также обратить внимание на правильный порядок входных и выходных данных.
Ни в коем случае не писать подсказки при вводе данных!!! Это сразу обнулит результаты при автоматическом тестировании.

5. Проверить получившуюся программу по авторским и своим тестам.
Любое изменение кода требует полного тестирования заново!

6. В случае прохождения всех тестов сдать программу, иначе вернуться к предыдущим пунктам.
Философское замечание. Лучше всего решить задачу полностью. Но это не всегда получается, и лучше решить задачу частично (за это на школьных соревнованиях начисляются баллы), чем не решить вовсе.
Также на большинстве олимпиад разрешается несколько раз сдавать одну и ту же задачу с целью повышения оценки.

Приложение. 4 нетрудных задачи с разбором.

Задача 1.

У пяти девочек было по некоторому количеству яблок. Первая съела одно своё яблоко, вторая отдала половину своих яблок третьей, четвёртая и пятая поделили свои яблоки поровну. Сделать программу для определения у кого сколько осталось.

Формат входных данных: одна строка из 5-ти целых положительных чисел, разделённых пробелами. Все числа <100. Второе число обязательно должно быть чётным, четвёртое и пятое должны в сумме давать чётное число.

Формат выходных данных: одна строка из 5-ти целых чисел, разделённых пробелами.

Примерный тест:

Входные данные:   Выходные данные:
10 20 30 40 50            9 10 40 45 45

Предельное время на прохождение одного теста 1 секунда.

Решаем задачу:

1. Внимательно читаем условие задачи.

2. Проверяем авторский тест.
Вначале 10 20 30 40 50
Первая съела одно своё яблоко 9 20 30 40 50
Вторая отдала третьей половину 9 10 40 40 50
Четвёртая и пятая сложили свои яблоки и поделили поровну 9 10 40 45 45

3. Составляем свой тест
Можно заметить, что авторский тест довольно каверзный. То, что входные данные представляют собой арифметическую прогрессию, случайно. Если это вовремя не заметить, то можно пойти по неверному пути. На этом ни в коем случае нельзя строить алгоритм! Свой тест должен преодолеть эту каверзу.
Вначале 20 32 13 27 15
Первая съела одно своё яблоко 19 32 13 27 15
Вторая отдала третьей половину 19 16 29 27 15
Четвёртая и пятая сложили свои яблоки и поделили поровну 19 16 29 21 21

Наш тест:
Входные данные:   Выходные данные:
20 32 13 27 15       19 16 29 21 21

4. Создаём программу с комментариями (Python).

# Задача 1 из приложения к статье
# "Этапы решения программистских задач олимпиадного типа"
# Для решения этой задачи достаточно уметь работать с переменными,
# обладать здравым смыслом и знать математику в объёме 3-х классов.
# Для правильного ввода данных нужно владеть функцией map

a1, a2, a3, a4, a5 = map(int, input().split()) # Ввод ВХОДНЫХ данных
           # В данной программе ВХОДНЫЕ данные совпадают с ВЫХОДНЫМИ!
           # Обратите внимание на удобные имена переменных/

a1 = a1 - 1  # 1-я съела одно своё яблоко

a2 = a2 // 2 # Вычисление того, сколько осталось у 2-й и
             # одновременно сколько она должна отдать первой.
             # Если бы надо было отдать не половину, а другую долю,
             # то понадобилась бы отдельная вспомогательная   
             # переменная, а так программа обошлась без
             # вспомогательных переменных, что говорит о её простоте.

a3 = a3 + a2 # 3-я получает яблоки от 2-й.
             # Не все начинающие ученики сразу понимают
             # почему тут не надо делить.

a4 = (a4 + a5)// 2 # Вычисление того, сколько должно остаться у 4-й и
                # 5-й. Деление нацело сделано потому что сумма
                # гарантировано чётная и в ответе ожидается целое
                # число.

a5 = a4     # 5-я получает свою долю. Этот момент порой вызывает
            # трудность у начинающих учеников.

print(a1, a2, a3, a4, a5) # Вывод Выходных данных

5. Проверяем программу по тестам и убеждаемся, что всё правильно.




Задача 2.

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

Формат входных данных: одна строка из 3-х целых чисел, разделённых пробелами. Все числа <100.

Формат выходных данных: одно целое число.

Примерные тесты:

Входные данные: Выходные данные:
10 30 20                2
20 10 30                3

Предельное время на прохождение одного теста 1 секунда.

Решаем задачу:

1. Внимательно читаем условие задачи. Тут надо понять, что надо вычислить не наибольшее значение, а позицию, на котором оно стоит.

2. Проверяем авторские тесты. Тут всё очевидно

3. Составляем свои тесты. Тут требуется полная система.
Три разных числа могут быть записаны одно за другим 6-ю разными способами.
Входные данные:    Выходные данные:
10 20 30                3
10 30 20                2
20 10 30                3
20 30 10                2
30 10 20                1
30 20 10                1

4. Создаём программу с комментариями (Python).

# Задача 2 из приложения к статье
# "Этапы решения программистских задач олимпиадного типа"
# Для решения этой задачи достаточно уметь работать с
# переменными, ветвлениями, обладать здравым смыслом
# и знать математику в объёме 3-х классов.
# Для правильного ввода данных нужно владеть
# функцией map

a1, a2, a3 = map(int, input().split()) # Ввод ВХОДНЫХ данных

nm = 1      # Предположение, что самое большое число стоит
            # на 1-й позиции
me = a1     # nm, me - номер и значение максимального числа

if a2 > me: # Если 2-е больше, то переприсваиваем 
me = a2     # номер и значение
nm = 2

if a3 > me: # Если 3-е больше, то переприсваиваем
            # номер и значение
me = a3     # Строго говоря, это можно и не делать, так как
            # это ветвление последнее.
nm = 3   

print(nm)   # Вывод Выходных данных


5. Проверяем программу по тестам и убеждаемся, что всё правильно.


Задача 3.

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

Формат входных данных: одно целое положительное число <=10000000000.

Формат выходных данных: две строки. В первой одно целое число, во второй столько целых чисел через пробел, каково число в первой строке.

Примерные тесты:

Входные данные:                Выходные данные:
36                9
                1 2 3 4 6 9 12 18 36
15                4
                1 3 5 15

Предельное время на прохождение одного теста 1 секунда

Решаем задачу:

1. Внимательно читаем условие задачи.

2. Проверяем авторские тесты. Тут всё очевидно

3. Составляем свои тесты. Тут требуется полная система.

Перед этим убедимся, что все делители можно разделить на пары, таким образом, что произведение чисел из каждой пары равно исходному числу:

36, делители: 1 2 3 4 6 9 12 18 36 (число 6 выделено так как оно не имеет пары!)
15, делители: 1 3 5 15

Также обратим внимание, что большей частью у чисел имеется чётное количество делителей. Исключения составляют полные квадраты.

Тесты для проверки:
№ Входные данные:        Выходные данные:        Комментарий
1 1                1                1
                Единица, уникальный тест
2 20                6
                1 2 4 5 10 20       Небольшое число с чётным количеством
3 36                9
                1 2 3 4 6 9 12 18 36   Небольшое число с нечётным количеством делителей
4 9999999999        48
                1 3 9 11 33 41 99 123 271 369 451 813 1353 2439 2981 4059 8943 9091 1     1111 26829 27273 33333 81819 99999 100001 122221 300003 366663 372731 900009 1099989 1118193 2463661 3354579 4100041 7390983 12300123 22172949 27100271 36900369 81300813 101010101 243902439 303030303  909090909 1111111111 3333333333 9999999999 Большое число с чётным количеством делителей.

Получилась очень длинная строка.
10000000000 121
1 2 4 5 8 10 16 20 25 32 40 50 64 80 100 125 128 160 200 250 256 320 400 500 512 625 640 800 1000 1024 1250 1280 1600 2000 2500 2560 3125 3200 4000 5000 5120 6250 6400 8000 10000 12500 12800 15625 16000 20000 25000 25600 31250 32000 40000 50000 62500 64000 78125 80000 100000 125000 128000 156250 160000 200000 250000 312500 320000 390625 400000 500000 625000 640000 781250 800000 1000000 1250000 1562500 1600000 1953125 2000000 2500000 3125000 3200000 3906250 4000000 5000000 6250000 7812500 8000000 9765625 10000000 12500000 15625000 16000000 19531250 20000000 25000000 31250000 39062500 40000000 50000000 62500000 78125000 80000000 100000000 125000000 156250000 200000000 250000000 312500000 400000000 500000000 625000000 1000000000 1250000000 2000000000 2500000000 5000000000 10000000000 Большое число с нечётным количеством делителей.
Получилась очень длинная строка.

4. Создаём программу с комментариями (Python).


# Задача 3 из приложения к статье
# "Этапы решения программистских задач
# олимпиадного типа"
# Нахождение всех делителей и их количества
# Для решения этой задачи достаточно уметь работать с
# переменными, ветвлениями, циклами, списками,
# обладать здравым смыслом,
# и знать математику в объёме 6-ти классов.

a = int(input()) # Ввод исходного числа
d = [1] # Список делителей
        # Это на случай, если число равно 1

if a > 1: #
    d = []  # Список делителей, сперва пустой
    i = 1   # потенциальный делитель
    while i <= a**0.5: # Для экономии времени идём
                # до квадратного корня.
        if a % i == 0: # Проверка на делимость
            d.append(i)    # Добавка к списку делителей
            d.append(a//i) # парных элементов
        i += 1 # увеличение потенциального делителя
    if a**0.5 == int(a**0.5): # В случае если исходное
                # число полный квадрат
               
        d.pop()         # удаляется последний элемент
                # по причине его непарности

    d.sort() # Сортировка

print(len(d)) # Вывод количества
print(*d)     # Вывод списка делителей без скобок
                # и запятых

5. Проверяем программу по тестам и убеждаемся, что всё правильно.


;
Задача 4. Очень простая
Имеется арифметическое выражение, записанное следующим образом:
• Целое число
• Пробел
• Знак операции («+» или «-»)
• Пробел
• Целое число

Требуется сделать программу для вычисления значения этого выражения.

Формат входных данных: одна строка, в которой через пробелы записаны первое целое число, знак операции («+» или «-»), второе целое число. Все числа <=1000 и >=-1000.

Формат выходных данных: одна строка, в которой через пробелы записаны первое целое число, знак операции, второе целое число, знак «=», третье целое число.

Примерные тесты:

Входные данные: Выходные данные:
36 + 5         36 + 5 = 41
36 - 5         36 - 5 = 31

Предельное время на прохождение одного теста 1 секунда

Решаем задачу:

1. Внимательно читаем условие задачи.

2. Проверяем авторские тесты. Тут всё очевидно

3. Составляем свои тесты.
Строго говоря, это задача очень простая, и можно было сделать тестов меньше.
Тесты для проверки:
№ Входные данные: Выходные данные: Комментарий
1 25 + 35         25 + 35 = 60
2 543 - 43 543 - 43 = 500
3 57 + 0         57 + 0 = 57
4 39 - 0         39 - 0 = 39
5 -23 + 88 -23 + 88 = 65
6 -23 + 12 -23 + 12 = -11
7 -43 + -55 -43 + -55 = -98
8 555 + -788 555 + -788 = -233
9 787 + -23 787 + -23 = 764
10 545 - -45 545 - -45 = 590
11 565 - -656 565 - -656 = 1221
12 -656 - -767 -656 - -767 = 111

4. Создаём программу с комментариями (Python).


# Задача 4 из приложения к статье
# "Этапы решения программистских задач олимпиадного типа"
# Для решения этой задачи достаточно уметь работать с переменными,
# уметь переводить их из одного типа в другой,
# уметь работать с ветвлением,
# обладать здравым смыслом и знать математику в объёме 5-ти классов.
# Для правильного ввода данных нужно владеть функцией map.

a1, a2, a3 = map(str, input().split()) # Ввод ВХОДНЫХ данных
# Все данные вводим в строковом виде, так как среди
# них находится символ действия.
# Это, пожалуй, главная сложность задачи.
a1 = int(a1) #  Преобразования в числовой вид.
a3 = int(a3) # /

if a2 == '+':      # В зависимости от знака операции
    a4 = a1 + a3   # выполняется то или иное действие. 
elif a2 == '-':
    a4 = a1 - a3

print(a1, a2, a3, '=', a4)
# Вывод данных. Не забыть знак "="!

5. Проверяем программу по тестам и убеждаемся, что всё правильно.