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

Обсуждение задачи 1144. The Emperor's Riddle

Does this problem has a deterministic polynomial solution? If such solution exists, can anybody send it to me (ioi@list.ru)
Послано Antonina Baskova 29 ноя 2002 19:11
No, combination of deterministics and NP is one solution, but the algorithm is elementary greedy (-)
Послано Miguel Angel 1 дек 2002 05:26
>
Re: No, combination of deterministics and NP is one solution, but the algorithm is elementary greedy (-)
Послано Mephistos 2 дек 2002 15:49
I can't understand how the solution can be greedy :). If we take M =
2, we'll get problem about stones and two piles, which is NP-hard.

Maybe I misunderstood the problem? And I can realize WHAT IS K :)