ОКСАНА СЕЛЕНДЕЕВА, основатель Международной школы программирования для детей CODDY

 АНДРЕЙ ЛОЗИЦКИЙ, преподавателем курса «Олимпиадное программирование» Школы CODDY

Олимпиада по программированию:
разбираем задачу, выбираем подход и язык для решения

Олимпиадные задачи делятся на классические и конструктивные. Классические задачи составляют по темам: динамическое программирование, алгоритмы на графах или на строках, теоретико-числовые алгоритмы и подобные, поэтому для решения необходимо свести задачу к известному алгоритму. Решение конструктивных задач не сводится к написанию общеизвестного алгоритма – его нужно «увидеть»

Решение олимпиадной задачи

Разберем классическую задачу¹ на алгоритмы вместе с Андреем Лозицким, преподавателем курса «Олимпиадное программирование» Школы CODDY.

Условие задачи

Доля успешных попыток

• Ограничение по времени на тест – 2 секунды.
• Ограничение по памяти на тест – 256 мегабайт.
• Ввод – стандартный ввод.
• Вывод – стандартный вывод.

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

Таким образом, на данный момент ваша доля успешных попыток на Codeforces составляет x/y.

Ваше любимое рациональное число в диапазоне [0;1] – это p/q.

Теперь вам интересно: какое минимальное количество попыток вам придется сделать, если вы зададитесь целью сделать долю успешных попыток равной p/q?

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

Первая строка содержит одно целое число t (l <= t <= 1000) – количество тестов.

Каждая из следующих t строк содержит четыре целых числа x, y, p и q (0 <= x + y <= 10⁹; 0 <= p <= q <= 10⁹; y > 0; q > 0).

Гарантируется, что p/q – несократимая дробь.

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

Для каждого теста выведите одно целое число – минимальное количество попыток, которое вам придется сделать, чтобы ваша доля успешных попыток стала равна вашему любимому рациональному числу, либо минус 1, если добиться желаемого невозможно.

Пример

Предварительный анализ

Обычно условие задачи написано в виде жизненной истории, потому что писать четкую математическую формулировку не принято. Поэтому сначала выделите математическую формулировку задачи. Затем разберитесь с примерами к ней.

• В первом тесте нужно совершить 4 удачные попытки, тогда доля успешных попыток будет 7/14 или 1/2.
• Во втором тесте – 2 удачные и 8 провальных попыток, тогда доля успешных попыток будет 9/24 или 3/8.
• В третьем тесте доля успешных попыток уже равна 2/7.
• В четвертом тесте доли успешных попыток 1/1 нельзя добиться ни при каких условиях.

Затем посмотрите на ограничения, которые написаны в условии задачи: программа должна работать не более 2 секунд и использовать не более 256 Мб памяти.

Все данные ограничены числом 10⁹. Также определитесь, на каком языке станете писать решение и какова будет сложность алгоритма.

Сложность алгоритма – зависимость объема работы, которая выполняется алгоритмом от размера входных данных. Обозначается O(f(n)).

Например, если сложность алгоритма будет O(n²), а входные данные примерно равны 10⁹, то решение не сможет пройти такой тест. Алгоритму потребуется примерно 10¹⁸ операций, а самый быстрый язык программирования может выполнять максимум 10⁹ операций в секунду. Поэтому сложность алгоритма должна зависеть от другой функции, которая растет медленнее, чем f(n) = n².

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

Также смотрите, какой ввод/вывод нужен: стандартный или файловый. При стандартном вводе/выводе программа должна вывести результат на экран, а при файловом – записать его в текстовый файл.

Решение

Исходно мы имеем 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;10⁹], так как y <= 10⁹. Если для r = 10⁹ данные неравенства не будут выполнены, то такого r не существует, и в этом случае выведем минус 1.

Искать r можно разными способами:

• Подставлять поочередно числа из отрезка [1;10⁹]. Сложность алгоритма будет O(n*t). Но тогда для самого худшего случая потребуется сделать 10¹² операций за 2 секунды. На это не способен ни один язык программирования.
• Использовать бинарный поиск на отрезке [1;10⁹]. Тогда сложность алгоритма будет 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 лет.

Комментарии могут оставлять только зарегистрированные пользователи