799 - Safari Holiday

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

799 - Safari Holiday

Post by jingye » Sat Oct 26, 2002 7:24 am

What should I output for n=1?

Should I observe English grammar?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Oct 26, 2002 11:22 am

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:

Post by Caesum » Fri Jan 31, 2003 7:51 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 02, 2003 5:18 pm

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:

Post by Caesum » Sun Feb 02, 2003 5:26 pm

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

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sun Feb 02, 2003 8:00 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 02, 2003 8:12 pm

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 :wink:
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:

Post by Caesum » Sun Feb 02, 2003 8:29 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 02, 2003 8:38 pm

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

Post by Emilio » Mon Sep 12, 2005 2:50 am

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:

Post by mf » Mon Sep 12, 2005 3:26 am

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

Post by Emilio » Tue Sep 13, 2005 1:38 am

Why do you think it's a necessary condition?
The reason is that I thought too quickly :D

I got AC.

Thanks mf!

User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa » Fri Aug 25, 2006 4:54 am

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! 

:D
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
Location: Bangladesh(CSE DU)
Contact:

Post by abdullah<cse du> » Fri Aug 24, 2007 5:59 pm

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
We were in past, we are in past and we will go in past.

Post Reply

Return to “Volume 7 (700-799)”