На Одесской областной олимпиаде школьников 2018 года мы предложили 12 задач различной степени сложности. Результаты можно найти здесь.
Условия задач, их короткий разбор мы попытались сделать на этой странице.
Решать задачи можно на сайте acm.pp.ua после простой регистрации. Соревнование №12.
Первые три задачи получились разбиением одной задачи, на три этапа для последовательного решения.
Задача A. Секунды
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
На часах сейчас $s$ секунд. Сколько секунд они будут показывать через $t$ секунд?
Входные данные: Два целых числа через пробел – $s \left(0 \le s \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$
Выходные данные: Одно целое число – новые показания секунд на часах.
| Вход |
Выход |
| 2 3 |
4 |
| 25 50 |
15 |
На что обратить внимание
- Значения параметра t выходит за пределы знакового 32-битного числа $\left[-2^{31};2^{31}-1\right]$
. Необходимо знать как кодируются целые числа и выбрать такой тип, чтобы данные и результаты вычислений не выходили за его пределы.
- Нужно заметить, что каждые $60$ секунд показания возвращаются к исходному значению. Значит для решения следует использовать операцию остатка от деления на $60.$
A. Решение на С++
|
|
#include <iostream> int main() { long long s, t; std::cin >> s >> t; std::cout << (s + t) % 60; return 0; } |
A. Решение на Java
|
|
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); long s = in.nextLong(); long t = in.nextLong(); System.out.println((s + t) % 60); } } |
A. Решение на C#
|
|
using System; public class Sum { private static void Main() { string[] tokens = Console.ReadLine().Split(' '); long s = long.Parse(tokens[0]); long t = long.Parse(tokens[1]); Console.WriteLine((s + t) % 60); } } |
Задача B. Минуты и секунды
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
Часы сейчас показывают $s$ секунд и $m$ минут. Сколько они будут показывать через $t$ секунд?
Входные данные: Три целых числа через пробел – $s, m \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$
Выходные данные: Два целых числа через пробел – новые показания минут и секунд.
| Вход |
Выход |
| 44 25 22 |
26 6 |
| 59 58 121 |
1 0 |
На что обратить внимание
- Если предыдущая задача решена, то следует разобраться только с минутами. Нужно разобраться сколько пройдёт минут, если было $s$ секунд и прошло ещё $t$. Для этого придётся суммарное количество секунд разделить на $60$ — число секунд в минуте.
- Поскольку минутная стрелка через $60$ минут вернётся к тем же показаниям, нужно снова взять остаток от деления на $60.$
- Хотя условие задачи укладывается всего в пару строк, читать его нужно внимательно. Небольшое упражнение на внимательность состоит в том, что минуты и секунды на входе и выходе должны следовать в различном порядке.
B. Решение на C++
|
|
#include <iostream> int main() { long long s, m, t; std::cin >> s >> m >> t; std::cout << (m + (s + t) / 60) % 60 << " " << (s + t) % 60; return 0; } |
Задача C. Часы, минуты, секунды
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
На часах сейчас $h$ часов, $m$ минут и $s$ секунд. Сколько они будут показывать через $t$ секунд?
Входные данные: Четыре целых числа через пробел – $h \left(0 \le h \le 23\right), m, s \left(0 \le s, m \le 59\right)$ и $t \left(0 \le t \le 2^{31}\right).$
Выходные данные: Три целых числа через пробел – новые показания часов, минут и секунд.
| Вход |
Выход |
| 23 59 59 66 |
0 1 5 |
На что обратить внимание
- Кроме того, что период повторения часов составляет $24 \times 60 \times 60$ секунд особенно добавлять здесь нечего.
C. Решение на C++
В решении предлагается другой подход решения задачи. Предлагается перевести текущие показания часов в секунды. После этого увеличим текущее время на требуемое число секунд. Полученный результат можно будет снова перевести в часы, минуты и секунды. такой подход работает для самых разных задач в которых данные задаются в сложной системе единиц. Например, фунт стерлингов, шиллинг, пенс, фартинг, гинея, крона. Достаточно перевести все в наименьшие единицы, если все остальные соответствуют их целому числу. В общем случае, такой универсальной единицей может стать наибольший общий делитель всех используемых единиц.
|
|
#include <iostream> int main() { long long s, m, h, t; std::cin >> h >> m >> s >> t; t = (t % (60*60*24) + s + m*60 + h*60*60) % (60*60*24); std::cout << t / 60 / 60 << " " << (t / 60) % 60 << " " << t % 60; return 0; } |
Следующие две задачи также укладываются в некоторую цепочку. Вторая задача отличается от первой снятием ограничения на направление вырезания и это делает ее гораздо более сложной.
Задача D. Вырезаем прямоугольник в клеточку
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
Имеется лист из тетради в клеточку размером $H \times W$ клеток. Определите, можно ли из него вырезать прямоугольник размером $h \times w$. Резать можно только по линиям.
Входные данные: Четыре целых числа через пробел – $H, W, h, w$. Все числа положительные и меньше $2^{31}.$
Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.
| Вход |
Выход |
| 5 8 10 1 |
0 |
| 5 8 6 4 |
1 |
На что обратить внимание
- Вырезать можно двумя способами — вдоль листа или поперек. Нужно убедиться, что в каком-то из этих положений все поместится.
D. Решение на C++
|
|
#include <iostream> #include <cmath> using namespace std; int main() { int H, W, h, w; cin >> H >> W >> h >> w; cout << (max(H,W) >= max(h,w) and min(H,W) >= min(h,w)); return 0; } |
Задача E. Вырезаем прямоугольник снова
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
Имеется лист бумаги размером $H \times W$ миллиметров. Определите, можно ли из него вырезать прямоугольник размером $h \times w$ миллиметров.
Входные данные: Четыре целых числа через пробел – $H, W, h, w.$ Все числа не превышают $500$.
Выходные данные: Выведите $1$ если требуемый прямоугольник вырезать можно или $0$ если нельзя.
| Вход |
Выход |
| 5 8 7 7 |
0 |
| 8 8 10 1 |
1 |
На что обратить внимание
- Конечно главное отличие задачи от предыдущей совсем не в том, что клеточки заменили на миллиметры.
- В этой задаче вырезать можно не только вдоль сторон листа, но и под любым углом к ним.
- Если Вы уже знаете тригонометрию, то вам достаточно разместить прямоугольник под некоторым углом $\alpha$ и просчитать ширину и высоту охватывающего его листа. Останется только подобрать правильный угол. Недостаток этого способа состоит в том, что необходимо уметь пользоваться тригонометрическими функциями и обратными к ним.
- Школьники в 8-м классе ещё не знают тригонометрических функций. Но есть возможность получить более изящное решение, без их использования. Это решение приводится под спойлером, но лучше попытайтесь найти его самостоятельно.
E. Решение на C++
|
|
#include <iostream> #include <cmath> using namespace std; int main() { double H, W, h, w; cin >> H >> W >> h >> w; if (H > W) swap(H,W); if (h > w) swap(h,w); double d2 = w*w + h*h; cout << ((h <= H) and (w <= W) or H*sqrt(d2-W*W) + W*sqrt(d2-H*H) <= w*w - h*h); return 0; }<pre class="lang:c++ decode:true " > |
И снова две задачи, вторая из которых лишена одного из ограничений. И снова, снятие ограничения делает вторую задачу более сложной. Точнее менее очевидной.
Задача F. Режем масло
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной $1.$
Какое минимальное число разрезов нужно будет сделать если каждый из полученных при разрезании кусочков нужно резать отдельно от остальных?
Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$
Выходные данные: Одно целое число — минимальное количество разрезов.
| Вход |
Выход |
| 1 1 2 |
1 |
| 3 2 5 |
29 |
На что обратить внимание
- Я сторонник аналитического подхода к этой задаче. Рассуждаем так. У нас один кусочек. Каждый разрез добавляет ещё один кусочек. Т.е. кусочков получается на $1$ больше, чем разрезов. Но мы легко можем вычислить сколько должно получиться кусочков — мы ведь знаем размеры.
F. Решение на C++
|
|
#include <iostream> using namespace std; int main() { long long X, Y, Z; cin >> X >> Y >> Z; cout << X * Y * Z - 1; return 0; } |
Задача G. Режем масло снова
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
Имеется прямоугольный брусок масла размером $X \times Y \times Z.$ Плоскими разрезами его нужно разделить на кубики со стороной 1.
Какое минимальное число разрезов нужно будет сделать если разрезать можно сразу стопку из любого количества кусочков?
Входные данные: Три целых положительных числа через пробел – $X, Y$ и $Z$ каждое из которых не превышает $2^{21}.$
Выходные данные: Одно целое число — минимальное количество разрезов.
| Вход |
Выход |
| 1 1 2 |
1 |
| 3 2 5 |
6 |
На что обратить внимание
- Теперь можно резать по несколько кусков сразу. Если не знаете как это, понаблюдайте как мама нарезает картошку маленькими кубиками. Она ведь режет сразу несколько пластинок, а не по одной?
- Представьте, что у на некоторой стадии у Вас получилось два кусочка и один из них больше другого по всем размерам. Если Вы будете резать больший из них, то при этом заодно разрежется и второй.
Это справедливо для любого числа кусков. Значит стоит рассматривать только самый большой кусок.
- Стоит резать так, чтобы больший из кусков был поменьше. Т.е. примерно пополам (с округлением вверх).
- Делим на два каждую из сторон до тех пор пока не получим единицу. Количество делений и есть ответ.
G. Решение на C++
Я привожу решение, которое использует логарифм по основанию два. Логарифмы изучаются только в конце выпускного класса. Если вы еще не добрались до логарифмов в школе, не беда. Просто напишите функцию
f() при помощи цикла деления пополам с округлением в большую сторону и сосчитайте сколько раз придется делить. Код от этого не станет намного длиннее и работать будет также с близкой скоростью.
|
|
#include <iostream> #include <cmath> using namespace std; int f(int n) { return (int)(ceil(log((long double)n)/log(2.L))); } int main() { long long X, Y, Z; cin >> X >> Y >> Z; cout << f(X) + f(Y) + f(Z); return 0; } |
Задача H. Ибн аль-Хайсам задумался!
Лимит времени: 0.5 сек
Лимит памяти: 128MiB
Дано целое число $n$. Вычислите остаток от деления на $n$ произведение всех чисел от $1$ до $n-1.$
Входные данные: Целое число $n \left( 1 \lt n \lt 2^{31}\right).$
Выходные данные: Выведите значение выражения, требуемое в условии.
На что обратить внимание
- Если $n$ не является простым, то все его делители обязательно встретятся в качестве сомножителей при вычислении этого длинного произведения. Значит остаток будет равен нулю.
- Ой! Число $4$ явно исключение из этого правила. Добавим для него условный оператор.
- Остались простые числа. Понаблюдаем за ними написав цикл вычисления требуемого значения.
Везде получается $n-1$? Попробуем отправить решение.
- Если Вас заинтересовал последний факт и Вы хотите доказать его (хотя на соревновании достаточно простого удачного наблюдения), то Вы повторяете путь, который проделал в своё время Ибн аль-Хайсам. Сейчас этот результат принято называть теоремой Вильсона. Для неё напридумывали много простых и изящных доказательств. Даже геометрических. Но гораздо интереснее попытаться доказать ее самому. Там совсем не сложно догадаться.
H. Решение на C++
Функция
prime() осуществляет прямую проверку числа на простоту. Т.е. просто перебираются все возможные нетривиальные делители. В приведенной ниже реализации сделаны некоторые весьма наивные попытки ускорить работу. Например, сразу исключены числа десятичная запись которых заканчивается на 0, 2, 4, 5, 6 или 8. Конечно, кроме самих чисел 2 и 5, которые являются простыми. Далее в цикле проверяются все возможные нечетные делители, т.к. чётные уже исключены. Перебор ведётся до $\sqrt{n}$. Из-за погрешности вычислений может быть пропущен делитель в точности равный $\sqrt{n}$. Чтобы избежать этой ситуации проверка ведется до $\sqrt{n+1}$. Задание единицы в виде
1.L приводит к тому, что вычисления выполняются с повышенной точностью (
long double). В данном случае эта перестраховка используется только как повод упомянуть этот полезный иногда тип данных.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <cmath> using namespace std; bool prime(long long n) { if (n == 2 or n == 5) return true; int last = n % 10; if (last == 0 or last == 2 or last == 4 or last == 5 or last == 6 or last == 8) return false; for (long long i = 3; i <= sqrt(n + 1.L); i+=2) { if (n % i == 0) return false; } return true; } int main() { long long p; cin >> p; if (p == 4) cout << 2; else if (prime(p)) cout << p - 1; else cout << 0; return 0; } |
Задача I. Настолько ли просты эти числа?
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
Число называется простым если оно делится только на 1 и на само себя. Найдите наибольший общий делитель всех введенных простых чисел.
Входные данные: В первой строке указывается количество простых чисел 1 < n < 10000. Во второй строке через пробел следуют n простых чисел меньших 231.
Выходные данные: Одно целое число — наибольший общий делитель всех введенных простых чисел.
На что обратить внимание
- В предыдущей задаче пришлось поработать с простыми числами. В этой почти тривиальной задаче мы закрепляем понимание их определения. Те участники, которые не смогли справится с предыдущей задачей получают эту в качестве некоторого утешительного приза.
- Простые числа делятся только на 1 и на само себя. Значит наибольшим общим делителем может быть только один из этих двух вариантов.
- Типичная ошибка — всегда выводить 1. Правильно было бы заметить, что если все числа одинаковы, то НОД всё же не 1, а само число.
I. Решение на C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <iostream> #include <cmath> using namespace std; int main() { int n; cin >> n; long long a, b; cin >> a; for (int i = 1; i < n; ++i) { cin >> b; if (a != b) { cout << 1; return 0; } } cout << a; return 0; } |
Задача J. Деньги
Лимит времени: 0.4 сек
Лимит памяти: 128MiB
В стране выпущены банкноты номиналом 500, 200, 100, 50, 20, 10, 5 и 1 гривну. А также монеты достоинством 0.5, 0.25, 0.1, 0.05, 0.02 и 0.01 гривны. Требуется найти способ выдать сумму в n гривен, используя наименьшее количество банкнот и монет.
Входные данные: Одно положительное действительное число n, не превышающее 1010, которое задаёт сумму с точностью до копеек.
Выходные данные: В одной строке следует вывести пары чисел через пробел — номинал банкноты (или монеты) и количество банкнот (или монет) этого номинала к выдаче. Значения следует перечислять в порядке увеличения номиналов денежных знаков.
| Вход |
Выход |
| 436.24 |
0.02 2 0.1 2 1 1 5 1 10 1 20 1 200 2 |
На что обратить внимание
- Задача и простая и глубокая одновременно. Простая, поскольку решается интуитивно понятным жадным методом. Глубокая, поскольку может (и должна!) навести на мысли о поисках условия при которых этот жадный метод действительно даёт решение задачи. Т.е. каким условиям должны удовлетворять номиналы монет, чтобы жадный выбор давал оптимальное решение? Речь идёт о так называемых канонических монетных системах.
- Жадный принцип требует начинать выдавать сумму с самых крупных купюр. Условие требует печатать ответ с самых мелких монет. Автор вредничает. Что делать? Конечно можно записать все количества в массив и напечатать его с конца. В приведенном ниже авторском решение используется другой подход — формируется строка ответа в которой новые данные вставляются в начало. Т.е. для формирования ответа можно использовать массивы или строки.
J. Решение на C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <sstream> #include <string> using namespace std; int main() { double sum; cin >> sum; long long n = (long long) (sum * 100); int b[] ={50000, 20000, 10000, 5000, 2000, 1000, 500, 100, 50, 25, 10, 5, 2, 1}; string s; for (int i = 0; i < sizeof(b) / sizeof(b[0]) and n > 0; ++i) { if (n >= b[i]) { ostringstream os; os << b[i]/100. << " " << n / b[i] << " "; s.insert(0, os.str()); n %= b[i]; } } cout << s; return 0; } |
Задача K. Одни плюсы
Лимит времени: 2 сек
Лимит памяти: 128MiB
Для заданного целого положительного числа n составьте равное ему арифметическое выражение, используя только операции сложения, умножения, скобки и число 1, содержащее минимально возможное число единиц.
Например, 7 = (1 + 1 + 1) * (1 + 1) + 1.
Входные данные: Одно целое положительное число n ≤ 104.
Выходные данные: Минимально возможное количество единиц.
На что обратить внимание
- Планировалась как самая сложная задача соревнования. Решение занимает целых 18 строк.
- Задача относится к одному из самых красивых и популярных направлений в олимпиадном программировании. Имеется в виду так называемая «динамика» — динамическое программирование. Конечно, для решения задачи совсем не обязательно об этом знать, можно и так догадаться. Но знания и тренировка лучший помощник природной смекалке и сообразительности.
- Для каждого числа есть возможность либо представить его в виде суммы единицы и числа на единицу меньшего, либо в виде произведения двух других чисел. Из этих двух вариантов выбираем тот в котором меньше единиц. А как узнать количество единиц в этих новых числах? Рекурсивным применением этого подхода. Рано или поздно мы получим просто 1 и процесс завершится.
- Меморизация! Т.е. запоминание полученных результатов. Если мы уже вычислили кратчайшее представление некоторого числа (например, 2=1+1 или 5=(1+1)(1+1)+1), то это нужно запомнить и когда это число встретится в вычислениях снова, без повторных вычислений сразу использовать ранее полученный результат.
K. Решение на C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include <iostream> #include <vector> using namespace std; vector < int > a; int main() { int n, m; cin >> n; a.push_back(1); a.push_back(2); for (int i = 2; i < n; i++) { m = a[i - 1] + 1; for (int j = 2; j * j <= i + 1; j++) if ((i + 1) % j == 0 and (a[j - 1] + a[(i + 1) / j - 1] < m)) m = a[j - 1] + a[(i + 1) / j - 1]; a.push_back(m); } cout << a[n - 1] << endl; } |
Задача L. Комплексный обед
Лимит времени: 0.3 сек
Лимит памяти: 128MiB
В меню столовой имеется n блюд. Стоимость каждого блюда известна. Комплексный обед с точки зрения администрации должен состоять из двух блюд, имеющих общую стоимость не более k. Какое максимальное количество вариантов комплексных обедов можно составить если каждое блюдо может входить только в один комплексный обед.
Входные данные: В первой строке заданы два целых положительных числа n ≤ 105 и k ≤ 109. Во второй строке следуют через пробел целые положительные числа задающие стоимости каждого из этих n блюд.
Выходные данные: Максимально возможное количество вариантов комплексных обедов.
| Вход |
Выход |
5 8
1 9 7 2 4 |
2 |
На что обратить внимание
- Задача «на сортировку» или «на жадные алгоритмы».
- Если расположить все блюда по возрастанию (или убыванию) цены, то нам останется найти для каждого блюда из числа более дорогих парное из числа более дешевых.
- Логика решения такова. Каждое блюдо из числа более дешевых (в порядке увеличения цены) должно найти себе пару из числа более дорогих. Если какое-то не нашло, то дальше нечего и пытаться — будет только дороже. Дорогие блюда просматриваем в порядке уменьшения цены. Если не подошло для данного блюда, то и для более дорогого тоже не подойдёт.
- Никакого перебора не понадобится. Просто движемся по отсортированному массиву с двух сторон на встречу друг другу. Если текущее дорого блюдо образует с текущим дешевым пару, то увеличиваем счётчик комплексных обедов и переходим к следующему дорогому и следующему дешевому. Если цена этой пары блюд слишком велика, переходим к следующему блюду из числа дорогих.
L. Решение на C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios::sync_with_stdio(false); int n, k, b; cin >> n >> k; vector<int> w(n); for (int i = 0; i < n; ++i) cin >> w[i]; sort(w.begin(), w.end()); int ans = 0, i1 = 0, i2 = n - 1; while (i1 < i2) { if (w[i1] + w[i2] <= k) { ++i1; --i2; ++ans; } else --i2; } cout << ans << endl; } |
В завершение вставим таблицу результатов соревнования:
Related Images:
Будем предполагать, что Ваша цель не просто изучить программирование, но и научиться решать задачи. Это означает, что Вы вероятно хотите получить в дальнейшем какую-то пользу от своих новых знаний и навыков, а не просто убиваете время. Сразу должен предупредить, что это потребует во много раз больше усилий, чем простое изучение синтаксиса и лексики 
Для отправки комментария необходимо войти на сайт.