Олимпиада по программированию: разбираем задачу, выбираем подход и язык для решения::Журнал СА 10.2018
www.samag.ru
     
Поиск   
              
 www.samag.ru    Web  0 товаров , сумма 0 руб.
E-mail
Пароль  
 Запомнить меня
Регистрация | Забыли пароль?
Журнал "Системный администратор"
Журнал «БИТ»
Наука и технологии
Подписка
Где купить
Авторам
Рекламодателям
Магазин
Архив номеров
Вакансии
Контакты
   

  Опросы
1001 и 1 книга  
12.02.2021г.
Просмотров: 8288
Комментарии: 1
Коротко о корпусе. Как выбрать системный блок под конкретные задачи

 Читать далее...

11.02.2021г.
Просмотров: 8598
Комментарии: 0
Василий Севостьянов: «Как безболезненно перейти с одного продукта на другой»

 Читать далее...

20.12.2019г.
Просмотров: 15795
Комментарии: 0
Dr.Web: всё под контролем

 Читать далее...

04.12.2019г.
Просмотров: 14977
Комментарии: 12
Особенности сертификаций по этичному хакингу

 Читать далее...

28.05.2019г.
Просмотров: 16143
Комментарии: 3
Анализ вредоносных программ

 Читать далее...

Друзья сайта  

Форум системных администраторов  

sysadmins.ru

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

Архив номеров / 2018 / Выпуск №10 (191) / Олимпиада по программированию: разбираем задачу, выбираем подход и язык для решения

Рубрика: Карьера/Образование /  Кафедра

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

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

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

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

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

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

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

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

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

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

Многие работодатели предлагают на собеседованиях решать именно алгоритмические задачи

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

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

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

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

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

Каждая из следующих t строк содержит четыре целых числа xyp и q (0 <= x + y <= 1090 <= p <= q <= 109y > 0q > 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 успешных и (– x) неуспешных попыток. Так как p/q – несократимая дробь, то в конце мы должны иметь p*r успешных и (q*– p*r) неуспешных попыток, где r – некоторое натуральное число.

Понятно, что количество успешных и неуспешных попыток может только увеличиваться, тогда в конечном счете должны быть верны неравенства p*>= x и q*– p*>= – x.

Заметим, что правая часть неравенств всегда остается постоянной, а левая часть растет при возрастании t. Следовательно, если эти неравенства будут верны при каком-нибудь r, то они будут так же верны при более больших r.

Так как по условию задачи нам нужно найти минимальное количество попыток, при котором доля успешных попыток станет равной p/q, то нам нужно найти минимальное r, при котором равенства станут верными, а ответом на задачу будет q*– 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 решаемы. Из первого неравенства получаем, что >= x/p, из второго: >= (– x)/(– p). Для того чтобы оба неравенства выполнялись, r должно удовлетворять условию >= max((x/p); (– x)/(– p)). Минимальное r ищется из соотношения max((x/p); (– x)/(– 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 лет.


Комментарии отсутствуют

Добавить комментарий

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

               Copyright © Системный администратор

Яндекс.Метрика
Tel.: (499) 277-12-41
Fax: (499) 277-12-45
E-mail: sa@samag.ru