799 - Safari Holiday

[jingye]

What should I output for n=1?

Should I observe English grammar?

[Adrian Kuegel]

In all cases print persons (for example 1 persons/group), but when day is 1, print 1 day.

[Caesum]

does this need bigint ? (and hence rethink of my algorithm too) or is long long enough ? (and hence my algorithm is just wrong)

[Adrian Kuegel]

long long is enough (I used unsigned int).
There is one special case.
If kmax>=n use something like:
printf("%u persons/group, 1 day\n",n);

[Caesum]

thanks, i must be doing some other thing wrong then...... by the way, congratulations on 1000

[Caesum]

I thought this was a relatively easy looking question, involving finding possible solutions to two simple mod equations however I have ended up trying to look for the existence of an (n,k,1)-design and have two mod equations, one inequality (fishers inequality) and a headache.... am I on the right lines with this question, it is about the existence of certain designs like steiner triple systems ?

[Adrian Kuegel]

Two simple mod equations sounds good. But I can't understand the other things you are speaking of. I simply tried to find some k that
(... two mod equations)
spoiler deleted

[Caesum]

Yes...... I am ac now, I guess I was trying to make this too difficult however it seems to me that these conditions are not sufficient for the existence of a solution and it is a much deeper problem than that. See 'the 15 schoolgirls problem' by Thomas Kirkman which is essentially the problem presented here. It appears to me that any solution to this question forms what is known as a (v,k,1)-design however the existence of solutions for given v and k (or n and k as in 799) is not a simple question to answer and the two mods do not appear to be sufficient conditions - sure you can find a k which solves the mods but does this guarantee some possible solution exists ? In fact http://www.designtheory.org/library/enc ... cs/pbd.pdf states that there can be exceptions to this.

[Adrian Kuegel]

It seems this problem is not one of these with original judge input/output, since 798 for example has no input/output yet. The one who created the input/output could have made a mistake. If you are sure about your solution, you can make a new input/output and send them to the admins.

[Emilio]

Hi there!

First, this is the problem where I have obtained more WA and RE.
I'm really desperate.

I describe my algorithm here:

Code: Select all

    for each case
        if kmax >= n => solution found, next case;
        for k=kmax to 2
            if n mod k == 0
                if combinations_n_elements_k_at_time mod (n/k) == 0 => solution found, next case;
        No solution, next case;

I think that the problem is that exists in the problem input some case where combinations_n_elements_k_at_time is really big.

Now the questions:
Is my algorithm correct?
If someone have used the same algorithm, Could say me how have he/she solved the trouble with combinations?
Any hint about another algorithm is welcome.

Thanks!

[mf]

if combinations_n_elements_k_at_time mod (n/k) == 0

Why do you think it's a necessary condition?
My accepted program is basically the same, except that instead I test whether k-1 divides n-1 (because the number of days equals (n-1)/(k-1), and it must be an integer.)

[Emilio]

Why do you think it's a necessary condition?

The reason is that I thought too quickly

I got AC.

Thanks mf!

[joeluchoa]

I've got WA and I'm not see the what is wrong in my solution!
Can Somebody help me?

Code: Select all

Remove, I've got AC now! 

[abdullah<cse du>]

Hi all,

If anyone get accepted this problem please give me some i/o. I got several wrong ans. Please help me quickly.

Thanks
Abdullah