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

  Опросы
  Статьи

День сисадмина  

Учите матчасть! Или как стать системным администратором

Лето – время не только отпусков, но и хорошая возможность определиться с профессией

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

День сисадмина  

Живой айтишник – это всегда движение. Остановка смерти подобна

Наши авторы рассказывают о своем опыте и дают советы начинающим системным администраторам.

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

Виртуализация  

Рынок решений для виртуализации

По данным «Обзора российского рынка инфраструктурного ПО и перспектив его развития», сделанного

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

Книжная полка  

Как стать креативным и востребованным

Издательский дом «Питер» предлагает новинки компьютерной литературы, а также книги по бизнесу

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

Книжная полка  

От создания сайтов до разработки и реализации API

В издательстве «БХВ» недавно вышли книги, которые будут интересны системным администраторам, создателям

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

Разбор полетов  

Ошибок опыт трудный

Как часто мы легко повторяем, что не надо бояться совершать ошибки, мол,

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

Принципы проектирования  

Dependency Inversion Principle. Принцип инверсии зависимостей в разработке

Мы подошли к последнему принципу проектирования приложений из серии SOLID – Dependency

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

Рынок труда  

Вакансия: Администратор 1С

Администратор 1С – это специалист, который необходим любой организации, где установлены программы

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

Книжная полка  

Книги для профессионалов, студентов и пользователей

Книги издательства «БХВ» вышли книги для тех, кто хочет овладеть самыми востребованными

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

Принципы проектирования  

Interface Segregation Principle. Принцип разделения интерфейсов в проектировании приложений

Эта статья из серии «SOLID» посвящена четвертому принципу проектирования приложений – Interface

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

Книжная полка  

Секрет успешных людей

Книги издательства «БХВ» по ИТ рассчитаны на разные категории читателей: от новичков

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

Учебные центры  

Карьерные мечты нужно воплощать! А мы поможем

Школа Bell Integrator открывает свои двери для всех, кто хочет освоить перспективную

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

Гость номера  

Дмитрий Галов: «Нельзя сказать, что люди становятся доверчивее, скорее эволюционирует ландшафт киберугроз»

Использование мобильных устройств растет. А вместе с ними быстро растет количество мобильных

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

Прошу слова  

Твердая рука в бархатной перчатке: принципы soft skills

Лауреат Нобелевской премии, специалист по рынку труда, профессор Лондонской школы экономики Кристофер

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

1001 и 1 книга  
19.03.2018г.
Просмотров: 11274
Комментарии: 0
Потоковая обработка данных

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

19.03.2018г.
Просмотров: 9529
Комментарии: 0
Релевантный поиск с использованием Elasticsearch и Solr

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

19.03.2018г.
Просмотров: 9578
Комментарии: 0
Конкурентное программирование на SCALA

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

19.03.2018г.
Просмотров: 5986
Комментарии: 0
Машинное обучение с использованием библиотеки Н2О

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

12.03.2018г.
Просмотров: 6695
Комментарии: 0
Особенности киберпреступлений в России: инструменты нападения и защита информации

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

12.03.2018г.
Просмотров: 3988
Комментарии: 0
Глубокое обучение с точки зрения практика

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

12.03.2018г.
Просмотров: 2907
Комментарии: 0
Изучаем pandas

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

12.03.2018г.
Просмотров: 3715
Комментарии: 0
Программирование на языке Rust (Цветное издание)

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

19.12.2017г.
Просмотров: 3719
Комментарии: 0
Глубокое обучение

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

19.12.2017г.
Просмотров: 6209
Комментарии: 0
Анализ социальных медиа на Python

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

19.12.2017г.
Просмотров: 3064
Комментарии: 0
Основы блокчейна

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

19.12.2017г.
Просмотров: 3363
Комментарии: 0
Java 9. Полный обзор нововведений

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

16.02.2017г.
Просмотров: 7180
Комментарии: 0
Опоздавших не бывает, или книга о стеке

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

17.05.2016г.
Просмотров: 10558
Комментарии: 0
Теория вычислений для программистов

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

30.03.2015г.
Просмотров: 12274
Комментарии: 0
От математики к обобщенному программированию

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

18.02.2014г.
Просмотров: 13908
Комментарии: 0
Рецензия на книгу «Читаем Тьюринга»

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

13.02.2014г.
Просмотров: 9039
Комментарии: 0
Читайте, размышляйте, действуйте

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

12.02.2014г.
Просмотров: 7000
Комментарии: 0
Рисуем наши мысли

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

10.02.2014г.
Просмотров: 5310
Комментарии: 3
Страна в цифрах

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

18.12.2013г.
Просмотров: 4542
Комментарии: 0
Большие данные меняют нашу жизнь

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

18.12.2013г.
Просмотров: 3350
Комментарии: 0
Компьютерные технологии – корень зла для точки роста

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

Друзья сайта  

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

Архив номеров / 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