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

Общий форум

Nikifor-3
Послано Petko Minkov 12 апр 2001 00:08
How can i solve this task? Give me a hint.
Seems like it's quite easy. Is there any divisibility
rule for seven?
Re: Nikifor-3
Послано Leonid Volkov 12 апр 2001 09:23
> How can i solve this task? Give me a hint.
> Seems like it's quite easy. Is there any divisibility
> rule for seven?
>

It doesn't have to use the divisibility by 7.
The hint is as follows:
 from all the variety of 24 numbers, consisting of
permutations of digits 1,2,3,4, there should be probably
exist 7 numbers, giving all distinct remainders from
division by 7. Good luck!
Re: Nikifor-3
Послано Petko Minkov 12 апр 2001 11:05
> > How can i solve this task? Give me a hint.
> > Seems like it's quite easy. Is there any divisibility
> > rule for seven?
> >
>
> It doesn't have to use the divisibility by 7.
> The hint is as follows:
>  from all the variety of 24 numbers, consisting of
> permutations of digits 1,2,3,4, there should be probably
> exist 7 numbers, giving all distinct remainders from
> division by 7. Good luck!

You mean I mark the 1,2,3 and 4 numbers in my given number
which consists of also 5..9 and permute the digits at the
1,2,3,4 marked positions.
Re: Nikifor-3
Послано Leonid Volkov 12 апр 2001 12:15
> > > How can i solve this task? Give me a hint.
> > > Seems like it's quite easy. Is there any divisibility
> > > rule for seven?
> > >
> >
> > It doesn't have to use the divisibility by 7.
> > The hint is as follows:
> >  from all the variety of 24 numbers, consisting of
> > permutations of digits 1,2,3,4, there should be
probably
> > exist 7 numbers, giving all distinct remainders from
> > division by 7. Good luck!
>
> You mean I mark the 1,2,3 and 4 numbers in my given
number
> which consists of also 5..9 and permute the digits at the
> 1,2,3,4 marked positions.
>

The idea is a bit simplier. Consider all the 1234
permutations. Select those 7 of them giving distinct
remainders from division by 7. Ok, if all the numbers
a_0...a_6 give distinct remainders, then also all of the
numbers 10000*N+a_0...10000*N+a_6 do. Thus, you just print
out all the 5...9 digits, and all the 1...4 digits, except
for one 1, one 2, one 3 and one 4 in whatever order, add 4
zeroes to this number. You calculate the remainder this
number gives when you divide it by 7 and then you simply
finish this numbers by one of the a_0...a_6 permutations -
done! A bit special approach is to be applied to zeroes, it
is also simple.
Re: Nikifor-3
Послано Petko Minkov 12 апр 2001 22:54
thanks for the ideas:). it worked.
Re: Nikifor-3
Послано Jivko Ganev 14 апр 2001 15:32
I think this is not needed at all - even the 1 2 3 4
constraint, because the probability one arangment will get
evenly divided by 7 is 1 / 7. My program doesn't make any
special stuff for 1 2 3 4 and it still solves the problem
in 0.23 sec. I think it would be impossible to think of a
case that has many possible combinations and there is no
solution.