Очень много сайтов — codeforces, codility, eulerlist, topcoder, и т.д. (habrahabr.ru/post/128108/)
Но везде предлагают только задачи, иногда проверки и образцовое решение.
Но как узнать, как до него дошли? Зачастую неочевидно.
Вроде находил несколько книг по теме. Там, Скиена, Меньшиков — но, во первых, сильно мешает восприятию паскаль — очень тяжело читается, что сил нет осмысливать решение.
Есть ресурсы для обучения, которые сначала дают теорию, потом задачи и к ним хорошо расписанные решения?
- Вопрос задан более трёх лет назад
- 8454 просмотра
Все верно. Без знания некоторых первокирпичиков понять решение олимпиадной задачи по программированию практически невозможно. Поэтому сначала надо бы:
1. Почитать основы теории чисел. (Что-то вроде начальных глав Бухштаба (libgen.org/get.php?md5=83A35FC9F00ACD428657B5472231DA49)) — одна из наиболее дружелюбных книг для самостоятельного изучения или Thomas Koshy Elementary number theory with applications [2nd ed], если можете в английский (libgen.org/get.php?md5=6E32E401931D3721F88A128297D78B0C)
2. Почитать основы теории графов (Емеличев В.А., и др. Лекции по теории графов libgen.org/get.php?md5=BF711CEBD6C94B61AA1203B8F1E931FE)
3. Почитать алгоритмы на строках (Д. Гасфилд Строки, деревья и последовательности в алгоритмах libgen.org/get.php?md5=718B422928CA1DCCAAD9F2AD29359DFE)
4. Почитать Кормена.
Потом пытаться реализовать все вышеперечисленное на Python.
В августе этого года в Казани прошла Международная олимпиада по программированию для школьников — IOI 2016. Российская команда стала второй в общем зачете.
Один из серебряных медалистов, Денис Солонков из г. Мытищи, сделал разбор задачи «Обнаружение молекул», которая предлагалась участникам олимпиады.
Денис Солонков — многократный победитель Всероссийских олимпиад по программированию и Moscow CTF School, выпускник Школы программистов, ныне студент ВШЭ.
Являясь одним из преподавателей Дениса, я попросил его сделать разбор задачи с IOI 2016.
Условие задачи
Петр работает в компании, которая создала прибор для обнаружения молекул. Каждая молекула имеет целый положительный вес. Прибор характеризуется интервалом обнаружения [l, u], где l и u целые положительные числа. Прибор может обнаружить множество молекул тогда и только тогда, когда это множество содержит такое подмножество, что суммарный вес молекул в нем принадлежит интервалу обнаружения прибора.
Более формально, рассмотрим n молекул с весами w0. wn−1. Обнаружение считается успешным, если существует множество различных индексов I = такое, что l ≤ wi1 +. + wim ≤ u.
В силу особенностей работы прибора разница между l и u гарантированно больше либо равна разнице весов между самой тяжелой и самой легкой молекулами. Более формально, u − l ≥ wmax − wmin, где wmax = max(w0 . wn−1) и wmin = min(w0 ,…,wn−1).
Требуется написать программу, которая либо находит любое подмножество молекул с суммарным весом, принадлежащим интервалу обнаружения прибора, либо определяет, что такого подмножества не существует.
Детали реализации
Вам следует реализовать одну функцию (метод):
int[] solve(int l, int u, int[] w)
- l и u: границы интервала обнаружения,
- w: веса молекул.
Если требуемое подмножество существует, то функция должна вернуть массив индексов молекул, которые формируют любое такое подмножество. Если существует несколько правильных ответов, верните любой из них.
Если требуемого подмножества не существует, то функция должна вернуть пустой массив.
Для языка программирования Си сигнатура функции немного отличается:
int solve(int l, int u, int[] w, int n, int[] result)
n: количество элементов в w (то есть число молекул),
остальные параметры такие же, как описано выше.
Вместо того, чтобы возвращать массив состоящий из m индексов (как указано выше), функция должна записать индексы в первые m ячеек массива result и затем вернуть m.
Если требуемого подмножества не существует, то функция должна вернуть 0, не записывая ничего в массив result.
Ваша программа может записывать индексы в возвращаемый массив (или в массив result для языка Си) в любом порядке.
Пожалуйста, используйте предоставленные шаблоны файлов для уточнения реализации на выбранном вами языке программирования.
Примеры
Пример 1
solve(15, 17, [6, 8, 8, 7])
В этом примере есть четыре молекулы с весами 6, 8, 8 и 7. Прибор может обнаружить подмножества молекул с суммарным весом от 15 до 17 включительно. Обратите внимание, что 17 − 15 ≥ 8 − 6. Суммарный вес молекул 1 и 3 равен w1 + w3 = 8 + 7 = 15, таким образом функция может вернуть [1, 3]. Другие возможные правильные ответы: [1, 2] (w1 + w3 = 8 + 8 = 16) и [2, 3] (w1 + w3 = 8 + 7 = 15).
Пример 2
solve(14, 15, [5, 5, 6, 6])
В этом примере есть четыре молекулы с весами 5, 5, 6 и 6. Требуется найти подмножество с суммарным весом от 14 до 15 включительно. Опять же, обратите внимание, что 15 − 14 ≥ 6 − 5. Для данного примера не существует подмножества молекул с суммарным весом от 14 до 15, соответственно функция должна вернуть пустой массив.
Пример 3
solve(10, 20, [15, 17, 16, 18])
В этом примере есть четыре молекулы с весами 15, 17, 16 и 18. Требуется найти подмножество с суммарным весом от 10 до 20 включительно. Вновь, обратите внимание, что 20 − 10 ≥ 18 − 15. Любое подмножество, состоящее из одного элемента, имеет вес от 10 до 20, соответственно возможные правильные ответы это [0], [1], [2] и [3].
Система оценивания
(9 баллов): 1 ≤ n ≤ 100, 1 ≤ wi ≤ 100, 1 ≤ u, l ≤ 1000, все wi равны.
(10 баллов): 1 ≤ n ≤ 100, 1 ≤ wi, u, l ≤ 1000, и max(w0 ,…, wn−1) − min(w0,…, wn−1 ) ≤ 1.
(12 баллов): 1 ≤ n ≤ 100 и 1 ≤ wi,u, l ≤ 1000.
(15 баллов): 1 ≤ n ≤ 10 000 и 1 ≤ wi, u, l ≤ 10 000.
(23 балла): 1 ≤ n ≤ 10 000 и 1 ≤ wi, u, l ≤ 500 000.
(31 балл): 1 ≤ n ≤ 200000 и 1 ≤ wi, u, l #include
#include
#include
#include "molecules.h" //Including grader file
using ll = long long ; //A little alias to save time.
using namespace std ;
vector int > find_subset ( int l, int u, vector int > w ) <
int n = w. size ( ) ;
vector pair int , int > > weight ( n ) ;
for ( int i = 0 ; i n ; i ++ ) <
weight [ i ] = < w [ i ] , i >; //Storing initial index for the output.
>
sort ( weight. begin ( ) , weight. end ( ) ) ;
ll cur_sum = 0 ;
int bad_i ;
for ( bad_i = 0 ; bad_i n ; bad_i ++ ) < //Locating first bad length
cur_sum + = weight [ bad_i ] . first ;
if ( cur_sum > u )
break ;
>
if ( bad_i == 0 ) //no solution
<
return vector int > ( ) ;
>
set pair int , int > > picked, remain ;
ll curpicked = 0 ;
for ( int i = 0 ; i bad_i ; i ++ ) <
picked. insert ( weight [ i ] ) ;
curpicked + = weight [ i ] . first ;
>
for ( int i = bad_i ; i n ; i ++ ) <
remain. insert ( weight [ i ] ) ;
>
while ( curpicked l && ! remain. empty ( ) ) <
if ( picked. begin ( ) — > first >= remain. rbegin ( ) — > first ) //Nothing left to swap
break ;
//Swap the lowest and the highest elements.
curpicked + = remain. rbegin ( ) — > first — picked. begin ( ) — > first ;
auto el1 = * picked. begin ( ) ;
auto el2 = * remain. rbegin ( ) ;
picked. erase ( el1 ) ;
picked. insert ( el2 ) ;
remain. erase ( el2 ) ;
>
if ( curpicked l ) < //no solution
return vector int > ( ) ;
>
vector int > answer ;
for ( auto el : picked )
answer. push_back ( el. second ) ;
return answer ;
>
Решение подобных задач требует серьезной подготовки, которую можно получить в Школе программистов. В этом году ШП открывает новое отделение – в Физтехпарке, IT-парке рядом с МФТИ. Программа обучения усложненная, такая же, как в отделении при Яндексе, включающая в себя изучение высокоуровневых и низкоуровневых языков, дискретную математику, алгоритмику, структуры данных, сети, ОС и прочее.
Набор на 2016/17 учебный год проводится для школьников 6–10 классов по результатам экзамена, который состоится 8 октября 2016 в 14:00. Зарегистрироваться на экзамен и пройти подготовительный онлайн-курс можно здесь.
В Школе программистов также есть Онлайн отделение. Уроки проходят в формате вебинаров, принимаются студенты со всей России, начиная с 13 лет. Ближайший вступительный экзамен пройдет 15 октября в 17:00. Зарегистрироваться на экзамен в Школу программистов Онлайн и пройти подготовительный курс можно здесь.
Дистанционная развивающая олимпиада
Олимпиадные задачи по информатике с решениями
Предлагается более 60 олимпиадных задач, условно разбитых на несколько групп по степени их сложности и тематике. Для каждой из групп предлагаются примеры решения задач, основные идеи их решения, программы на языке Паскаль. Задачи излагаются в порядке нарастания трудности.
Используются следующие обозначения:
Решение — переход к решению задачи;
Подсказка — переход к подсказке по задаче.
Загрузка...
