Олимпиады по программированию.

[vovken1997]

Доброго времени суток!!!
Предлагаю всем участникам олимпиад, выкладывать задания.
Начну с себя:
Районный этап олимпиады Санкт-Петербупга по информатике(27,11,2011)

Задача 1 Квадратное уравнение
В квадратном уравнении ax^2 +bx+c=0 заданы коэффициенты a,b , значение с не задано. Известно, что у уравнения ровно один корень.
Например, если a=1,b=-2, то искомое значение c=1
Требуется написать программу, которая по заданым целым числам a и b найдёт целое число с, такое что приведённое уравнение имеет ровно один корень, либо выяснит, что это невозможно.
-----------------------------------------------------
Задача 2 Седловая точка
Рассмотрим таблицу размером n*n, заполненную целыми числами. Седловой точкой в такой таблице называется число, которое является минимальным в своей строке и одновременно максимальным в своём столбце.
Например, в таблице
9 1 2
4 3 6
5 3 8
оба числа 3 являются седловыми точками. Других седловых точек в данной таблице нет.
Требуется написать программу, которая по числу n и таблице размером n*n найдёт колличество в ней седловых точек.
--------------------------------------------------------
Задача 3 Размещения
Размещения из n по k- это набор из k различных чисел, каждое из которых принимает значение от 1 до n. При этом размещения, отличающиеся порядком входящих в них чисел, считаются различными.
Например, сусществует 6 размещений из 3 по 2:
(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)
В приведённом примере сочетания упорядочены по сумме входящих в них чисел, а затем лексикографически - сначала по первому числу, затем по второму, и так далее.
Требуется написать программу, которая по заданным n и k выведет все размещения из n по k, упорядоченные указаным образом.
------------------------------------------------------------
Задача 4 Упаковка рюкзака
Группа школьников собирается в поход и собирается закупить продукты. В магазине есть n типов продуктов, про каждый продукт известна его цена pi, вес wi и питательность ci. Каждого типа продуктов можно купить неограниченное колличество.
Продукты складываются в рюкзак, который выдержит не больше W. Общий бюджет, выделенный на продукты, равен P. Школьники хотят купить продукты с максимальной суммарной питательностью.
Например, если есть 2 типа продуктов: p1=2 w1=2 c1=5 ; p2=1 w2=3 c2=3 P=5 W=7, то оптимально купить два продукта первого типа и один - второго.
Требуется написать программу, которая по заданному целому числу n, числам P,W, а также информации о прдуктах - целым pi, wi ,ci находит максимальную суммарную питательность продуктов, которые можно взять в поход.
-----------------------------------------------------------
Задача 5 Подготовка отчёта
Для подготовки отчёта о проведении олимпиады жюри необходимо разработать n документов. Для каждого документа известен список документов, которые необходимо подготовить перед этим. Жюри хочет выяснить, в каком порядке необходимо готовить документы.
Например, пусть n=4 , перед документом 1 необходимо подготовить документы 2 и 4, перед 2-документ 3, а перед документом 4 - документы 2 и 3 . Тогда документы можно готовить в следующем порядке: 3,2,4,1.
Требуется написать программу, которая по n и списку зависимостей находит порядок, в котором следует разрабатывать документы.


Кто участвовал в подобных олимпиадах, просьба выложить задания сюда, но без ответов и указать когда и где проводилась олимпиада.
Буду очень блогадарен.
Хочу собрать олимпиадные задания, чтоб знать чего ждать в следующий раз на олимпиадах. Заранее СПАСИБО!!!!

[Somebody]

Олимпиадных задач в инете тьма, ещё и с тестирующими системами. Например
http://acm.timus.ru/?locale=ru

[BDA]

Или http://informatics.mccme.ru/moodle/.

[Poma][a]

Сообщение от BDA

Или http://informatics.mccme.ru/moodle/.

Вот она моя любовь!
Или acmp.ru
или тыц

Задания не только не повторяются, НО так же каждый год серьезно меняются.
Так что заходите на любой из выше представленных сайтов и решаете и решаете и решаете, тогда возможно Вам попадется что-то знакомое, хотя бы отдалено напоминающие решение какой-то задачи, которую Вы точно знаете как решать.

А так могу сказать, что очень часто при полном не понимании задачи и отсутствии идей, спасает рекурсия, так же перед походом на олимпиаду желательно знать : 1) пузырек 2) метод бинарного деления 3) и QuickSort.

P.S. Опыт участия олимпиад, увы, только 1 год...
Но готовлюсь супер серьезно...
P.P.S. Так же если Вы пройдете школьный этап, то на районе будет и теория - без неё на 2 этап(практику) не пройти (теория = решения, в основном, логических задач, придумывание алгоритмов, и т.п.)

[New man]

[QUOTE='Poma][a;1114951'] 1) пузырек[QUOTE]
Зачем вам пузырек?!
ЗЫ, два года участвовал в олимпиадах
В прошлом году на районном этапе вообще было такое:
Олимпиаду проводили в единственной школе, где не распилили деньги, которые выделены были под Windows(в остальных школах Linux, и среда программирования паскаль, которую так любят наши учителя и множество учеников(которых другому и не учат), не работает), и, ВНИМАНИЕ, в этой школе не было установлено ничего, кроме Винды - голая ось и больше ничего! Писал программы в блокноте.

[Poma][a]

Зачем вам пузырек?!

Иногда встречаются программы с сортировкой чего-либо по какому-то правилу, и в пузырьке очень просто изменить условие на нужное и успешно сдать программу.

У нас всегда (насколько мне известно) практика происходит в ПЕДе, компьютеры там старые ОСь загружается около 10 минут, но все-таки там паскаль, но увы только старичек Турбо, и псевдопаскаль АВС оба без справки.

[New man]

Да, это вообще раздражает, когда справку срезают, умение производить RTFM - одно из важнейших достоинств хорошего программиста

[vovken1997]

В прошлый год дошёл до региона, но там завалили. Задачи на районе примерно на одно и тоже, задача на графы, задача на рекурсию, только формулировки меняют. Вот я и хочу увидеть как можно больше задач, глядишь еще два года буду участвовать в олимпиадах и что нибудь из того что решал, попадётся.

[Somebody]

Сообщение от Poma][a

так же перед походом на олимпиаду желательно знать : 1) пузырек 2) метод бинарного деления 3) и QuickSort.

Сортировки достаточно одной. И надо помнить, что у QuickSort'а худший случай - n^2, а на олимпиадах любят тесты с худшими случаями. Правда, для этого надо знать, как выбирается опорный элемент. Но можно, например, предположить, что опорным будет центральный.
В общем неплохо бы сортировку слиянием ещё знать.

Сообщение от Poma][a

[COLOR="Silver"]P.P.S. Так же если Вы пройдете школьный этап, то на районе будет и теория - без неё на 2 этап(практику) не пройти (теория = решения, в основном, логических задач, придумывание алгоритмов, и т.п.)

Никогда не слышал про теорию на олимпиадах по информатике. Это где так?

Сообщение от Poma][a

Иногда встречаются программы с сортировкой чего-либо по какому-то правилу, и в пузырьке очень просто изменить условие на нужное и успешно сдать программу.

Условие в любой сортировке сменить легко. Даже если оно в нескольких местах, достаточно вынести в функцию.

Вообще неплохо знать основы геометрии: параметрическое уравнение прямой, уравнение окружности (и уметь находить их пересечения), скалярное и векторное произведения. Производные могут пригодиться. Алгоритмы на графах - хотя бы поиск в глубину и алгоритм Дейкстры. Динамическое программирование.
Если ввод/вывод из файла/в файл - внимательнее с именами файлов, если из стандартного ввода, то после отладки не забыть убрать в конце ReadLn или аналоги.
Если где-то будет Free pascal - надо помнить, что глобальные переменные нулями не инициализируются.
Если Turbo Pascal - неплохо знать о SetTextBuf, директивах компилятора ($M - увеличение стека при необходимости, $R-, $Q-, $N+); никаких real, так как double намного быстрее; память придётся динамически выделять во многих задачах.
И стандартный олимпиадный хак - "заглушки": допустим, есть задача, ответ - координаты точки, как решить - не знаешь. Тогда можно написать прогу, которая сравнивает ввод с примером из условия и, если это тот самый тест, выводит известный ответ. Если тест другой, можно, например, вывести 0 0 - так как есть повышенная вероятность, что в одном из простых тестов, составленных вручную, это будет правильным ответом.

[Poma][a]

Никогда не слышал про теорию на олимпиадах по информатике. Это где так?

Хм.. странно.. У нас (в Ярославле) 1 тур городской олимпиады - теория (решение задач (например что делает этот алгоритм? придумайте алгоритм решающий данную задачу? как можно с 100% уверенностью сказать что ... ? и т.п.))