Олимпиада по информатике 11-кл

← →
Talvin (2002-11-23 17:54) [0]

Уважаемае мастера, привожу пример задачи олимпиадной работы самой простой:

Сообщесто роботов живёт по следующим законам: один раз в начале года они объеденяются в группы по три или по пять роботов. За год группа из 3 роботов собирает 5 новых, а группа из 5 собирает 9 новых. Роботы собираются так, Роботы собираются так, чтобы собрать за год ниа большее количество. Каждый робот живйт три года после сборки

Задание: Напишите программу на паскале "ROBOT". Которая по известному начальному количеству роботов, которые только что собраны.ю определит сколько роботов буде собрано серез N -лет.

Входные данные: Первая строка входного файла ROBOT.DAT содержит целые чила K и N количество роботов котые только что собраны и число лет, через которые надо определить число роботов.

Выходные данные: Первоя строка выходного файла ROBOT.SOL содержит кол-во начитываемое в сообществе роботов через N лет.

Вопрос: сколько реально требуется времени для решения это задачи, и какого она уровня?

← →
TTCustomDelphiMaster (2002-11-23 18:10) [1]

2 минуты на алгоритм + N минут на написание кода

← →
PaRL (2002-11-23 18:27) [2]

где взял

← →
TMyGroupBox = class(TGroupBox) (2002-11-24 07:59) [3]

Kruto

← →
Anatoly Podgoretsky (2002-11-24 08:54) [4]

На олипиаде задали

← →
Sectey (2002-11-24 09:53) [5]

Забавная задачка, но в принципе простая.
Да действительно как сказа TTCustomDelphiMaster минуты две ушол на разработку алгоритмя. Ни чего сложного, только надо немножко подумать и посчитать.

← →
TTCustomDelphiMaster (2002-11-24 11:10) [6]

> makt_liCh http://www.dago.org (24.11.02 10:52)

Это что было?

← →
makt_liCh http://www.dago.org (2002-11-24 15:07) [7]

Задача решается за пол минуты:
var k,i,n,p:integer;
s,x,y:longint;
r:array [1..3] of longint;
begin
write("Начальное количество роботов k="); readln(k);
write("Число лет n="); readln(n);
r[1]:=k; r[2]:=0; r[3]:=0; s:=k;
for i:=1 to n do
begin
x:=s div 3;
p:=s mod 3;
if p=0 then y:=0
else if p=1 then begin x:=x-3; y:=2 end
else begin x:=x-1; y:=1 end;
r[3]:=r[2]; r[2]:=r[1]; r[1]:=5*x+9*y;
s:=r[1]+r[2]+r[3];
end;
writeln("s=",s)
end.

← →
Sectey (2002-11-24 15:27) [8]

А, я не согласен с makt_liCh.
Четко же сказано наибольшее количество роботов
9/5=1.8
5/3=1.67 1.8 > 1.67 тобиш производительность выше
из этих простеньких расчетов видно что необходимо робатов разбивать в начале не на тройки, а на пятерки.
Спору не простая задача.

← →
TTCustomDelphiMaster (2002-11-24 15:28) [9]

> makt_liCh http://www.dago.org (24.11.02 15:07)

Это же не правильное решение.

← →
Yegor Derevenets (2002-11-24 18:44) [10]

В начале разбивать на пятерки, потом - на тройки, причем желательно задействовать всех роботов. Тут, похоже, понадобиться еще немножко подумать. Или поподбирать. А дальше - только сделать это много раз, храня количества роботов, с момента выпуска которых прошло 0, 1, 2 года в массиве из трех элементов. И здвигаю эти элементы каждый год.
Правда, с известными ограничениями было бы проще.

P.S. Не знаете какую-нибудь олимпиадную конференцию?

← →
Yegor Derevenets (2002-11-24 18:44) [11]

В начале разбивать на пятерки, потом - на тройки, причем желательно задействовать всех роботов. Тут, похоже, понадобиться еще немножко подумать. Или поподбирать. А дальше - только сделать это много раз, храня количества роботов, с момента выпуска которых прошло 0, 1, 2 года в массиве из трех элементов. И cдвигаю эти элементы каждый год.
Правда, с известными ограничениями было бы проще.

P.S. Не знаете какую-нибудь олимпиадную конференцию?

← →
old_monkey (2002-11-25 06:34) [12]

Мне сын ее в прошлом году показывал.
Он не в 11 классе, а в 8, правда с уклоном.
Решения не помню, но спрошу, если не забуду.
Может он помнит, или сохранилось где.
Там все проще, чем кажется на первый взгляд.
По крайней мере к исследованию операций никакого отношения не имеет.

← →
Romchick (2002-11-25 09:22) [13]

НОК(3,5)=15. Собирать больше 4 групп из 3 роботов не имеет смысла, т.к. 5 групп по 3 соберут меньше, чем 3 группы по 5. Т.о., для каждого n есть 5 вариантов - собрать m групп по 3 (0<=m<=4), остальные по 5 роботов. Эти вырианты можно перебрать на бумажке и получить следующее:

Если кол-во роботов меньше 10:
0, 1, 2 - разбивки нет
3, 4 - 1 группа по 3 робота
5 - 1 группа по 5 роботов
6, 7 - 2*3 дают 10 штук
8 - 5+3 дают 14 штук
9 - 3*3 дают 15 штук.

Далее, если в начале года n роботов, то в зависомости от n mod 5:
0 - группы по 5
1 - (n-6) делим по 5 и 2 группы по 3
2 - (n-12) делим по 5 и 4 группы по 3
3 - (n-3) делим по 5 и 1 группы по 3
4 - (n-9) делим по 5 и 3 группы по 3

Действительно, выгодно использовать всех роботов.

PS. Я олимпиадник со стажем, имею высшее образование. На алгоритм у меня ушло примерно 5 мин., на доказательство - 10. Но я давно потерял форму, так что задача вполне по силам 11 классу.

← →
pasha_golub (2002-11-25 10:33) [14]

Примечание,ИМХО:
Задача известная, но не такая легкая. Она помнится даже описана
у Д.Кнутта "Исскуство программирования", а он как Вы знаете в свои книгах всякую ерунду не рассматривал.

← →
Romusyck (2002-11-25 11:09) [15]

Я помню эту задачу, но она была не в 11 классе, а в 9-м на олимпиаде в моем крае (Краснодарском). Реально, у меня ушло минут 15 на алгоритм и минут 10 на набор кода. Но к сожалению она была одной из самых легких. Привожу пример первой (самой сложной; к сожалению дословно не помню):
Дан четырехмерный куб (N,N,N,N), в каждой ячейке цифра от 0 до 9, надо дойти от угла 1,1,1,1 до угла n,n,n,n причем, чтобы сумма чисел была минимальна. Переход осуществляется только между соседними ячейками, т.е. которые соприкосаются гранями.
На нее у меня ушло 2,5 часов.
Проверь мозги!!!

← →
makt_liCh http://www.dago.org (2002-11-25 12:04) [16]

Ах... Пошу прощения.. Не заметил, что нужно максимум роботов.Но это тоже самое решение, только нужно тогда разобрать не остаток от делимости на 3, а на 5. почти тоже самое, только случаев на 2 побольше.
Кстати, Кнут действительно приводил пример почти такой же задачи в первом томе своей книги. Только что посмотрел.
А тем, кто очень любит тяжелые задачи, советую посетить http://www.acm.timus.ru или http://neerc.efmo.ru (yt у всех провов загружается).
Я только сегодня вернулся со всероссийской коммандной. Гы.. Вот твм задачи.....

← →
Romchick (2002-11-25 12:15) [17]

еще один линк на ту же тему - acm.sgu.ru

← →
Romchick (2002-11-25 12:28) [18]

Насчет куба - ничего кроме графа + алгоритм Дейкстры в голову не идет. Сложность - порядка n^5.
Не помнишь, какие были ограничения на n?

← →
makt_liCh http://www.dago.org (2002-11-25 12:34) [19]

Анн, нет. Кнут в приложении приводит следующую задачу:

Сообщесто роботов живёт по следующим законам: один раз в начале года они объеденяются в группы по три, по четыре или по пять роботов. За год группа из 3 роботов собирает 5 новых, группа из четырех собирает 7 новых, а группа из 5 собирает 9 новых. Роботы собираются так, чтобы собрать за год наибольшее количество. Каждый робот живет семь лет после сборки
Задание: Напишите программу, которая по известному начальному количеству роботов N, которы только что собраны, и по известному количеству K -лет, определит разброс между максимальным и минимальным количествам возможных собранных роботов.
Ограничения: 10<=K<=500000, 7<=N<=100, ограничение на время - 15 сек.

Данная задача в 10^32 раз сложнее.

Ни решения, ни пояснений Кнут к ней не приводит.
Мне кажется, что задача сводится к нахождению Эйлерова пути в графе, но при набивании кода, я заглыхаю на подсчете максимального разброса между минимальным и максимальным кол-вом собранных роботов... Там нужно определить максимальную и минимальную ширину ребра графа... Но как это сделать? Сейчас пошлю эту задачку Дмитричеву(четырех кратный победитель всероссийских олимпиад по программингу среди школьников).

← →
makt_liCh http://www.dago.org (2002-11-25 12:35) [20]

Хм... Олимпиадников то тут много бывает. Надо бы свой проект открывать. Кто за??? Было бы круто...

← →
Romchick (2002-11-25 13:51) [21]

Хм... что-то я не пойму условие. Роботы собираются всегда так, чтобы собрать максимальное количество. Т.е. каждый год способ объединения однозначен. Откуда может возникнуть разброс? Если роботы следуют правилам, то через К лет их количество будет однозначным.
И что значит "возможных собранных роботов"

← →
makt_liCh http://www.dago.org (2002-11-25 15:54) [22]

Romysick, да, хорошая задачка, я не писал, но думаю, у меня ушло бы столько же времени.
По принципу дейкстры она решается достаточно "просто". Сначала обрабатываешь алгоритм по нахождению нужного пути на плоскости(N*N), потом ставишь для другой плоскости(вертикальной). Из одной процедуры вызываешь другую и т.д. и т.п., хотя при набивании кода, наверное, есть трудности.
Если time limit<n/10000, то времени может не хватить, тогда надо уже поизвращаться.
P.S. Гы... Эта задачка же есть в книге, которую выдавали участникам зимних сборов 2001-2002 годов. Сразу не припомнил...

← →
makt_liCh http://www.dago.org (2002-11-25 16:05) [23]

Romchick, в условии ошибся...
Они могут следовать по двум правилам: 1)как можно меньше роботов
2)как можно больше роботов.
"Возможных собранных роботов" - не надо считать кол-во роботов, а посчитать разброс между их двуми путями развития: собрать как можно меньше и как можно больше роботов.
Не весело это тем, что нужно совместить сразу три алгоритма, точнее один алгоритм трижды для разных вещей, и все это для разных ситуаций. Маразм в time limit"e!!! Ни перебором, ни числами Фибоначи нет времени(занимает в худшем случае до суток).
Эйлеров путь позволяет работать быстрее time limit"a, но.....

← →
Romchick (2002-11-26 08:38) [24]

По поводу куба - надо сразу представить его в виде графа, а алгоритму Дейкстры все равно, плоский он или нет. А приведенное решение неправильное (если автор не имел в виду рекурсию, но тогда сложность решения 2^n, а не n/10000)

Про роботов. Как можно меньше роботов - это вообще не объединяться. Тогда через 7 лет их будет 0. Возможно пропущено условие, что все роботы должны объединиться. Тогда эта задача сложнее ровно в 2 раза - надо придумать алгоритм для минимального объединения. А потом написать цикл от 1 до K, в котором считается минимальное и максимальное количество роботов (max получается из предыдущего max, min - из предыдущего min). В конце вычислить разность двух чисел. Для современной техники ограничения мелкие, возможно для времен написания книги это лобовое решение не прошло бы.

← →
makt_liCh http://www.dago.org (2002-11-26 14:46) [25]

Romchik, ты еще один попавшийся на этой задачке человек. Прикол в том, что в зависимости от конечного года надо изначально выбирать группы роботов. При разных годах бывает, что нужно было сделать не 3 группы по 5, а три группы по 4 и одну группу по 3(1 год) или наоборот(100 лет). Вот где прикол задачи.

← →
Romchick (2002-11-26 17:36) [26]

mact_liCh, вот как я понял условие:
Есть 2 сообщества роботов. В обоих сначала по N роботов. Первое объединяется в группы, чтобы собрать максимальное количество, второе - чтобы собрать минимальное. Определить максимальную разницу между этими сообществами за период K лет.
Это правильно?

← →
makt_liCh http://www.dago.org (2002-11-29 14:06) [27]

Да

Олимпиада по информатике 11-кл Найти похожие ветки