## 799 - Safari Holiday

Moderator: Board moderators

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

### 799 - Safari Holiday

What should I output for n=1?

Should I observe English grammar?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
In all cases print persons (for example 1 persons/group), but when day is 1, print 1 day.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
does this need bigint ? (and hence rethink of my algorithm too) or is long long enough ? (and hence my algorithm is just wrong)

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
thanks, i must be doing some other thing wrong then...... by the way, congratulations on 1000

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
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 ?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Last edited by Adrian Kuegel on Wed May 12, 2004 10:35 pm, edited 1 time in total.

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
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.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Why do you think it's a necessary condition?
The reason is that I thought too quickly

I got AC.

Thanks mf!

joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil
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!
``````

http://acm.uva.es/problemset/usersnew.php?user=47903

All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:24-25]

abdullah<cse du>
New poster
Posts: 39
Joined: Mon Dec 04, 2006 2:18 pm