ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

Nikifor-3
Posted by Petko Minkov 12 Apr 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
Posted by Leonid Volkov 12 Apr 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
Posted by Petko Minkov 12 Apr 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
Posted by Leonid Volkov 12 Apr 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
Posted by Petko Minkov 12 Apr 2001 22:54
thanks for the ideas:). it worked.
Re: Nikifor-3
Posted by Jivko Ganev 14 Apr 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.