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

Обсуждение задачи 1095. Nikifor 3

Any hint, please?
Послано Li Yi 6 окт 2001 13:46
Re: Any hint, please?
Послано Huang Yizheng 1 ноя 2001 17:48
>I think only search is okey.
Re: Any hint, please?
Послано Coldfeel 30 мар 2003 15:07
>I think only search is okey.

ur solution is not good.

the better way is use remainder(mod)
Re: Any hint, please?
Послано Kit 12 апр 2005 00:12
I wanna offer my solution (I think, author had in view same method).
Arrange digits of the number in a such way:
(non-zero digits in arbitrary order)1234(all zeroes).
Then, we can permute only 1234 among them in order to receive a number, dividing by 7 (You can prove it).

Edited by author 12.04.2005 01:20
Re: Any hint, please?
Послано Nickolas 26 фев 2008 18:59
Is anybody willing to tell me why it works?
Re: Any hint, please?
Послано unlucky [Vologda SPU] 23 фев 2010 14:04
Kit писал(a) 12 апреля 2005 00:12
I wanna offer my solution (I think, author had in view same method).
Arrange digits of the number in a such way:
(non-zero digits in arbitrary order)1234(all zeroes).
Then, we can permute only 1234 among them in order to receive a number, dividing by 7 (You can prove it).

Edited by author 12.04.2005 01:20
No sorting, just "cutting" one : 1,2,3,4 from input number; selecting zeros and constructing "possible answer" :)
Re: Any hint, please?
Послано Madhav 23 сен 2010 02:45
cant we use dynamic programming.It is a O(2^numberofdigits) algorithm. Can any one tell me why the other solution works?
Re: Any hint, please?
Послано Artem Khizha [DNU] 21 авг 2011 16:05
@Nickolas

> Is anybody willing to tell me why it works?

You can write a sample program and see, that permutations of 1234 produce all possible remainders in division by 7. So <some non-zero numbers><permutation on 1234><zeros> always fits.
Re: Any hint, please?
Послано Takanashi Rikka 2 мар 2016 11:48
Just use random_shuffle.