МЕНЮ

 

Гостевая книга

Форум

 

  

RETAINING WATER

            RETAINING WATER - это одна из олимпиад, проводимых Al Zimmermann. Задача в ней следующая - вам дано число z от 4 до 28 (задачу нужно решить для каждого числа - то есть всего 25 задач). Нужно во-первых, построить магический квадрат размера z на z. Магический квадрат - это квадрат, у которого используются все числа от 1 до z2, и во-вторых, суммы чисел по всем горизонталям, вертикалям и диагоналям одинаковы. Вот пример такого квадрата размера 4х4:

712114
213811
163105
96154

            Но таких квадратов довольно много, а нужно выбрать наилучший. Как он выбирается? Все очень просто. Цифра на квадрате представляется как высота стены, находящейся на данной клетке квадрата. Например в левом верхнем углу нашего квадрата будет стена высотой 7. Вокруг квадрата стен нет.
            Далее на квадрат выливается вода - столько, чтобы скрылась даже самая высокая стена (в нашем случае - в третьей строке в первом столбце). Затем вода утекает за пределы квадрата - ведь там нет стен. Но вода может и остаться. В нашем случае вода останется на клетке с высотой 3 - потому что все стены вокруг нее (6-10-13-16) выше нее, следовательно вода там задержится.
            Сколько воды там задержится? В данном случае 3 единицы. Ведь четвертая доведет высоту данной клетки уже до 3+4=7 единиц - и лишняя единица воды утечет вниз на клетку с высотой 6, а с нее - за пределы квадрата. Следовательно данный квадрат сохраняет 3 единицы воды. Чем больше единиц воды сохраняет квадрат тем лучше ваше решение.

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

Назад
Хостинг от uCoz