ТВОЙ BZFAR
Главная » Статьи » Algorithms & Programming » Algorithms
Введение в олимпиадное программирование
← К списку тем Глава 01 · Начните с основы

Введение: что такое олимпиадная задача?

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

  • 01 Понять условие
  • 02 Придумать алгоритм
  • 03 Написать и проверить код

В решении есть две части

Алгоритм

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

Программа

Точная реализация этих шагов: читает данные, вычисляет ответ и выводит его в нужном формате.

На проверке обычно оценивают именно отправленную программу, а не описание идеи.

Как читать условие

Найдите четыре вещи: входные данные, что вывести, ограничения и пример.

Учебная задача

Сколько чётных чисел?

Входные данные

Сначала число n, затем n целых чисел.

Выходные данные

Одно число: сколько среди них чётных.

Ограничения

1 ≤ n ≤ 100 000; каждое число от 0 до 1 000 000 000.

Что важно заметить

n сообщает количество чисел. Само n в подсчёт не входит.

Ввод 
4
2 7 8 9
Вывод 
2

Идея решения: пройдите по всем n числам, подсчитайте те, что делятся на 2 без остатка, и выведите счётчик.

Проверь себя

Два коротких вопроса. Ответы можно менять и проверять повторно.

1. Какой ответ нужно вывести для этих данных? 5 4 7 2 9 6

 

2. Программа прошла пример из условия. Этого достаточно для принятия решения?

 

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

1. Ответ: 3 (числа 4, 2 и 6). 2. Нет: пример — лишь один из тестов.

Задача CSES · № 1068

Странный алгоритм

Оригинальное название на CSES: Weird Algorithm

Дано положительное целое число n. Постройте последовательность: если текущее число чётное, разделите его на 2; если нечётное, умножьте на 3 и прибавьте 1.

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

Ввод

В единственной строке записано число n.

Вывод

Напечатайте в одной строке последовательность через пробел: от исходного n до 1 включительно.

  • 1 ≤ n ≤ 10⁶
  • Время: 1 с
  • Память: 512 МБ

Пример

Ввод 
3
Вывод 
3 10 5 16 8 4 2 1

Русский пересказ условия. Источник: CSES Problem Set, Weird Algorithm ↗; лицензия сборника CC BY-NC-SA 4.0 ↗.

Готовы отправить решение?

Откройте эту же задачу на CSES и отправьте свой код на проверку.

Сдать задачу на CSES ↗

Основа урока: Антти Лааксонен, «Олимпиадное программирование» (2018), глава 1, разделы 1.1 и 1.3. 

Категория: Algorithms | Добавил: bzfar77 (Вчера)
Просмотров: 11 | Теги: введение, cses, олимпиадное программирование, алгоритмы, задачи | Рейтинг: 0.0/0
Всего комментариев: 0
Войдите:
avatar