Олимпиадные задачи по программированию

[still_alive]

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

Вот задачка, так задачка:
http://files.rsdn.ru/14399/math_putin.jpg
Не по информатике правда, а по математике (всё равно эти две науки тесно связаны)

Ага) Я недавно этот способ использовал в перегрузке оператора < своего класса для std::set, чтобы эквивалентность была более-менее адекватной.

Недавно была необходимость решить такие задачи.
http://ipicture.ru/uploads/20101117/4c8T4Z3J.png
Маленький спойлер:
Левая - ничего сложного: вывод простейшей формулы и использование длинной арифметики. Правая - небольшая трудность уложиться в 1с при 10000х10000.

[LeBron]

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

Ага) Я недавно этот способ использовал в перегрузке оператора < своего класса для std::set, чтобы эквивалентность была более-менее адекватной.

Недавно была необходимость решить такие задачи.
http://ipicture.ru/uploads/20101117/4c8T4Z3J.png

А меня недавно попросили помочь с правой. Она в России на онлайн-олимпиаде проскочила)
Я там одну маленькую хитрость придумал, так как лень было решать алгоритмически. Если поле достаточно широкое и достаточно длинное (от 5 в каждую сторону), то можно к конечной точке подобраться достаточно близко, используя алгоритм, как в примере (который не меняет положение экрана и передвигает телевизор на 2 поля), повторенный нужное количество раз в нужных направлениях. А дальше БФСить, там уже мелочь останется. Если же поле узкое или короткое, или конечная точка близко (имею ввиду Манхэттенское) к начальной, то можно и так БФС пускать.

[still_alive]

Да.
Если генерить граф, а потом пускать бфс, то это самоубийство (5х10000х10000 вершин и минимум О(MN)). Если генерить граф на ходу, то все равно не успеваем, секунды примерно на 2 на тесте 10000 10000 1 10000 10000.
У меня что-то в духе такой хитрости и вышло, но не в точности) Бфс с самого начала, но я для каждой вершины запоминал, как мы в нее пришли, а потом, доставая ее из очереди, первым делом шел по этому направлению. Если удавалось приблизиться к цели, то остальные не рассматривал и очередь очищал. Вот когда подходил совсем близко, то уже рассматривал все. В 1с уложился.

[_-Re@l-_]

Интересно, какой результат...

Вот, стали известны результаты....
Как оказалось, общий зачёт идёт по командам школ, т.е. берётся сумма всех учеников от школы и сравнивается с суммами других школ.
Ну и вот: у нашей школы 4 место, и то такое высокое чисто моя заслуга(у меня много баллов, а у остальных не более 40 из 500), как оказалось. Все остальные из нашей школы плохо написали олимпиаду.
Но, как выяснилось, мы ещё можем поехать на городскую олимпиаду...

http://files.rsdn.ru/14399/math_putin.jpg

Так тут же перебором...Вроде бы Особо не думал, уже ухожу просто

[pu4koff]

Сообщение от _-Re@l-_

Так тут же перебором...Вроде бы Особо не думал, уже ухожу просто

Нет. Не перебором. Чтобы решить задачу, нужно вспомнить про разряды чисел. Вовка Путин называет два двузначных числа, нужно Димке назвать такие числа, чтобы исходные двузначные числа разлеглись по разным разрядам и тогда премьер-министр по сути сам назовёт свои числа.

[artli]

acm.timus.ru
Очень даже неплохая система университета УрГУ. Сейчас там 809 задач (некоторые на английском) и четыре языка (C++, C#, Java, Pascal). Проходят онлайн-соревнования параллельно с университетскими олимпиадами (с некоторой задержкой), добавляются задания с олимпиад УрГУ.
Кстати, у меня в районной 500 из 500 (8 класс)

[LeBron]

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

Да.
Если генерить граф, а потом пускать бфс, то это самоубийство (5х10000х10000 вершин и минимум О(MN)).

Откуда М*N? Там с каждой вершини графа всего 4 перехода) Т.е. получается нечто вроде N*4. Другое дело, что оно по памяти абсолютно не катит)

[_-Re@l-_]

Кстати, у меня в районной 500 из 500 (8 класс)

Неудивительно. Видал я тамошние задачи.

Нет. Не перебором. Чтобы решить задачу, нужно вспомнить про разряды чисел. Вовка Путин называет два двузначных числа, нужно Димке назвать такие числа, чтобы исходные двузначные числа разлеглись по разным разрядам и тогда премьер-министр по сути сам назовёт свои числа.

Ну да, точно

Проходят онлайн-соревнования параллельно с университетскими олимпиадами (с некоторой задержкой), добавляются задания с олимпиад УрГУ.

Хм...Не люблю УрГУ. Я УрФУ(бывш. УГТУ-УПИ) люблю.

[artli]

Неудивительно. Видал я тамошние задачи.

Согласен

Хм...Не люблю УрГУ. Я УрФУ(бывш. УГТУ-УПИ) люблю.

Не изволите? А почему?

[_-Re@l-_]

Не изволите? А почему?

1. Мне не нравится вид здания УрГУ.
2. Там нет приличных факультетов.
3. Я буду поступать в УрФУ на ФИМТЭМ(Факультет Информационно-математических технологий и экономического моделирования, на ИИТ)
4. Вот здесь можно увидеть список предметов изучаемых там: ссылка
Неплохой списочек?