ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1480. Талоны

How to solve this problem?
Послано Aram Shatakhtsyan 18 апр 2007 15:11
Someone who solved this problem, give some ideas, please.
Re: How to solve this problem?
Послано Denis Koshman 24 июл 2008 14:51
The answer is n^2 + floor(n/2) + 1. Place n^2 in top-left corner and proceed row-by-row, column-by-column. For every cell choose maximal unused value, such that its sum with left and upper numbers is <= that minimal sum.

I have no idea why that works. The formula above was found empirically - these are minimal values when this greedy algorithm converges.

Edited by author 24.07.2008 15:00
Re: How to solve this problem?
Послано Alexander Samal 5 авг 2010 02:32
Real cheat! With this formula the problem is VERY easy! IMHO, without it - it would take much more time and efforts to get AC.