 |
|
|
|
Олимпиада по программированию: разбираем задачу, выбираем подход и язык для решения
Олимпиада по программированию:
|
ОКСАНА СЕЛЕНДЕЕВА, основатель Международной школы программирования для детей CODDY
АНДРЕЙ ЛОЗИЦКИЙ, преподавателем курса «Олимпиадное программирование» Школы CODDY
Олимпиадные задачи делятся на классические и конструктивные. Классические задачи составляют по темам: динамическое программирование, алгоритмы на графах или на строках, теоретико-числовые алгоритмы и подобные, поэтому для решения необходимо свести задачу к известному алгоритму. Решение конструктивных задач не сводится к написанию общеизвестного алгоритма – его нужно «увидеть»| Многие работодатели предлагают на собеседованиях решать именно алгоритмические задачи |
Таким образом, на данный момент ваша доля успешных попыток на Codeforces составляет x/y.
Ваше любимое рациональное число в диапазоне [0;1] – это p/q.
Теперь вам интересно: какое минимальное количество попыток вам придется сделать, если вы зададитесь целью сделать долю успешных попыток равной p/q?
Входные данные
Первая строка содержит одно целое число t (l <= t <= 1000) – количество тестов.
Каждая из следующих t строк содержит четыре целых числа x, y, p и q (0 <= x + y <= 109; 0 <= p <= q <= 109; y > 0; q > 0).
Гарантируется, что p/q – несократимая дробь.
Выходные данные
Для каждого теста выведите одно целое число – минимальное количество попыток, которое вам придется сделать, чтобы ваша доля успешных попыток стала равна вашему любимому рациональному числу, либо минус 1, если добиться желаемого невозможно.
Пример
| Входные данные | Выходные данные |
| 4 | 4 |
| 3 10 1 1 | 10 |
| 7 14 3 8 | 0 |
| 20 70 2 7 | -1 |
| 5 6 1 1 |
Предварительный анализ
Обычно условие задачи написано в виде жизненной истории, потому что писать четкую математическую формулировку не принято. Поэтому сначала выделите математическую формулировку задачи. Затем разберитесь с примерами к ней.
- В первом тесте нужно совершить 4 удачные попытки, тогда доля успешных попыток будет 7/14 или 1/2.
- Во втором тесте – 2 удачные и 8 провальных попыток, тогда доля успешных попыток будет 9/24 или 3/8.
- В третьем тесте доля успешных попыток уже равна 2/7.
- В четвертом тесте доли успешных попыток 1/1 нельзя добиться ни при каких условиях.
Затем посмотрите на ограничения, которые написаны в условии задачи: программа должна работать не более 2 секунд и использовать не более 256 Мб памяти.
Все данные ограничены числом 109. Также определитесь, на каком языке станете писать решение и какова будет сложность алгоритма.
Сложность алгоритма – зависимость объема работы, которая выполняется алгоритмом от размера входных данных. Обозначается O(f(n)).
Например, если сложность алгоритма будет O(n2), а входные данные примерно равны 109, то решение не сможет пройти такой тест. Алгоритму потребуется примерно 1018 операций, а самый быстрый язык программирования может выполнять максимум 109 операций в секунду. Поэтому сложность алгоритма должна зависеть от другой функции, которая растет медленнее, чем f(n) = n2.
Еще обращайте внимание на ввод/вывод данных. Программа должна выдавать такой же результат, как и в примере, с точностью до пробелов и перевода строк.
Также смотрите, какой ввод/вывод нужен: стандартный или файловый. При стандартном вводе/выводе программа должна вывести результат на экран, а при файловом – записать его в текстовый файл.
Решение
Исходно мы имеем x успешных и (y – x) неуспешных попыток. Так как p/q – несократимая дробь, то в конце мы должны иметь p*r успешных и (q*r – p*r) неуспешных попыток, где r – некоторое натуральное число.
Понятно, что количество успешных и неуспешных попыток может только увеличиваться, тогда в конечном счете должны быть верны неравенства p*r >= x и q*r – p*r >= y – x.
Заметим, что правая часть неравенств всегда остается постоянной, а левая часть растет при возрастании t. Следовательно, если эти неравенства будут верны при каком-нибудь r, то они будут так же верны при более больших r.
Так как по условию задачи нам нужно найти минимальное количество попыток, при котором доля успешных попыток станет равной p/q, то нам нужно найти минимальное r, при котором равенства станут верными, а ответом на задачу будет q*r – y.
Переменную r нужно искать на отрезке [1;109], так как y <= 109. Если для r = 109 данные неравенства не будут выполнены, то такого r не существует, и в этом случае выведем минус 1.
Искать r можно разными способами:
- Подставлять поочередно числа из отрезка [1;109]. Сложность алгоритма будет O(n*t). Но тогда для самого худшего случая потребуется сделать 1012 операций за 2 секунды. На это не способен ни один язык программирования.
- Использовать бинарный поиск на отрезке [1;109]. Тогда сложность алгоритма будет O(log(n)*t), и нам потребуется в самом худшем случае совершить примерно 30 000 операций за 2 секунды. На это уже способен любой язык программирования.
- Решить эффективнее: неравенства p*r >= x и q*r – p*r> = y – x решаемы. Из первого неравенства получаем, что r >= x/p, из второго: r >= (y – x)/(q – p). Для того чтобы оба неравенства выполнялись, r должно удовлетворять условию r >= max((x/p); (y – x)/(q – p)). Минимальное r ищется из соотношения max((x/p); (y – x)/(q – p)) с округлением вверх. Нужно учесть два частных случая, когда q и p равны 1 и 1 или 0 и 1. В этом случае нужно вывести минус 1. Данное решение является самым эффективным – оно не зависит от входных параметров. Сложность таких алгоритмов обозначается O(1).
Код решения с линейным поиском
#include <iostream>
using namespace std;
bool neravenstvo(long long x, long long y, long long p, long long q, long long r)
{
return (p*r >= x) && (q*r - p*r >= y - x);
}
int main()
{
long long x, y, p, q, t;
cin >> t;
for(int i = 0; i < t; ++i)
{
cin >> x >> y >> p >> q;
if(!neravenstvo(x, y, p, q, 1e9))
{
cout << -1 << endl;
continue;
}
for(long long r = 1; r <= 1e9; ++r)
{
if(neravenstvo(x, y, p, q, r))
{
cout << q*r – y << endl;
break;
}
}
}
}Код решения с бинарным поиском
#include <iostream>
using namespace std;
bool neravenstvo(long long x, long long y, long long p, long long q, long long r) {
return p * r >= x && q * r - p * r >= y - x;
}
int main() {
int t;
cin >> t;
for(int i = 0; i < t; ++i)
{
long long x, y, p, q;
cin >> x >> y >> p >> q;
long long l = -1;
long long r = 1e9;
if (!neravenstvo(x, y, p, q, r)) {
cout << -1 << endl;
continue;
}
while (r - l > 1) {
ll m = (l + r) / 2;
if (neravenstvo(x, y, p, q, m)) {
r = m;
} else {
l = m;
}
}
cin << r * q - y << endl;
}
return 0;
}Код решения с формулой
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
for(int i = 0; i < t; ++i){
int x, y, p, q;
cin >> x >> y >> p >> q;
if (p == 0) {
cout << (x == 0 ? 0 : -1) << endl;
continue;
}
if (p == q) {
cout << (x == y ? 0 : -1) << endl;
continue;
}
int r1 = (x + p - 1) / p;
int r2 = ((y - x) + (q - p) - 1) / (q - p);
cout << (q * max(t1, t2) - y) << endl;
}
}Язык для решения задач
После того как придумали решение задачи, определитесь с языком программирования. Далеко не на каждой олимпиаде разрешают выбрать любой язык. Самые популярные – Python, C++, C#, Java, Pascal.
Лучше освоить как минимум два языка программирования, так как бывают задачки, в которых решение простое, но громоздкое, поэтому требуется язык, на котором быстро пишут.
Бывают, наоборот, ресурсоемкие задачи, для решения которых необходимо придумать оптимальный алгоритм, имеющий наименьшую сложность, и использовать быстродействующий язык.
В первом случае лучше использовать Python, во втором – C++. Python – один из самых простых языков, но он довольно медленный. В зависимости от задачи Python работает в 100, а то и в 1000 раз медленнее, чем С++. Наоборот, С++ – один из самых быстрых языков программирования, но при написании кода можно наделать ошибок, на исправление которых уйдет времени больше, чем на подготовку самого решения.
Основная проблема не в том, что для работы на языке С++ необходимо быть аккуратным: после каждой команды ставить «;», объявлять тип переменной, ставить фигурные скобки. Проблема в том, что если программист допустил ошибку в алгоритме, например в результате работы программы он выходит за пределы массива, то Python сообщит об этом, а С++ – нет.
Тренировки перед олимпиадами
Чтобы научиться решать олимпиадные задачи, нужно много практиковаться. Для самостоятельного изучения теории советуем книги Томаса Кормена «Алгоритмы. Построение и анализ» и Дональда Кнута «Искусство программирования» в четырех томах. Подробный справочник по алгоритмам также есть на сайте MAXimal (http://e-maxx.ru). Там разобраны алгоритмы на языке С++, которые применяют на олимпиадах.
Для практики рекомендуем ресурсы с архивами олимпиадных задач: HackerRank (https://www.hackerrank.com), AtCoder (http://atcoder.jp), Codeforces (http://codeforces.com). На этих сайтах вы сможете решать задачи, сразу тестировать их и изучать подробные разборы. Также каждую неделю проходят тренировочные соревнования. Чтобы принять участие, необходимо только зарегистрироваться.
Участие в олимпиадах помогает не только обзавестись полезными знакомствами и с пользой провести время, но и устроиться в ведущие ИТ-компании. Многие работодатели предлагают на собеседованиях решать именно алгоритмические задачи.
Чтобы натренироваться, участвуйте в олимпиадах Яндекс.Алгоритм, Google Code Jam, Facebook Hacker Jam и подобных. Призеры и победители получают ценные призы, а участников с интересными решениями приглашают на работу.
1 Задача из третьего раунда Олимпиады VK CUP 2017 – Международного чемпионата по программированию для участников от 14 до 23 лет.
Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
