11843 - Guessing Game

All about problems in Volume 118. 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
suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

11843 - Guessing Game

Post by suneast » Mon Sep 20, 2010 1:05 pm

Hi, everyone

It seams quite a simple problem, but I always got WA.... :cry:
I use dp to solve it? but failed...

My dp format is like

Code: Select all

Accepted :D 
My answer is DP?n?m-1??
anything wrong or there is some tricky input?

any help will do...
Thx in advance.. :wink:
Last edited by suneast on Mon Sep 20, 2010 1:30 pm, edited 1 time in total.

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11843 - Guessing Game

Post by suneast » Mon Sep 20, 2010 1:16 pm

Oh, I think I mistake the problem...

I will try to fix it myself...

Happy solving... :wink:

suneast
New poster
Posts: 49
Joined: Sun Jan 17, 2010 6:25 am
Location: FZU
Contact:

Re: 11843 - Guessing Game

Post by suneast » Mon Sep 20, 2010 1:29 pm

Finally got AC...

I just make a little change of my code ...

It's a silly mistake...

Code: Select all

*
* a strike, if Bob's number is greater than X
* a smile, if Bob's number is less than X
* a stop, if Bob's number is precisely X
*
:wink:

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

Re: 11843 - Guessing Game

Post by Nursoltan_h » Tue Sep 21, 2010 4:11 pm

How to solve using dp? I'm stuck at it.

Khongor_SMCS
New poster
Posts: 15
Joined: Thu Jun 18, 2009 12:01 pm
Contact:

Re: 11843 - Guessing Game

Post by Khongor_SMCS » Wed Sep 22, 2010 10:44 am

Nursoltan_h wrote:How to solve using dp? I'm stuck at it.
dp(i,j) = min guess (i numbers with at most j strikes). Answer is obviously dp(n,m-1).
if our first guess is k then numbers divided to 0..k-1 and k+1..n-1. Numbers in 0 to k-1 need one strike but k+1..n doesn't need.
so dp(i,j) = min ( max( dp(k,j-1) , dp(n-k-1,j) + 1 ) {k=0..i-1}.

You have to consider base cases.
Last edited by Khongor_SMCS on Thu Sep 23, 2010 9:00 am, edited 1 time in total.

Nursoltan_h
New poster
Posts: 9
Joined: Sat Jun 12, 2010 2:11 pm
Location: Ulaanbaatar, Mongolia
Contact:

Re: 11843 - Guessing Game

Post by Nursoltan_h » Wed Sep 22, 2010 4:28 pm

Got it. Thanks hongor ahaa.

pdwd
New poster
Posts: 19
Joined: Sat May 15, 2010 4:35 pm

Re: 11843 - Guessing Game

Post by pdwd » Thu Sep 23, 2010 10:47 pm

It's enough to check k to i/2+1, because dp[k, j-1] >= dp[k, j] and dp[k1, j-1] > dp[k2, j] if k1 > k2. By checking k > i/2+1, you will always get from max dp[k-1, j-1].
I still believe there is a way to ask only 2 or 3 questions and get O(n*s) solution. Does anyone have such idea?

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11843 - Guessing Game

Post by Jehad Uddin » Fri Sep 24, 2010 8:47 am

you can precalculate on ans

Code: Select all

for(i=1;i<21;i++)
 {
        ar[i][1]=1;
        ar[1][i]=i;
 }

    for(i=2;i<21;i++)
    {
        for(j=2;j<=55;j++)
        {
             ar[i][j]=1+ar[i-1][j-1]+ar[i][j-1];
       }
    }
then just chek ar[s][k]>=N then output k

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Re: 11843 - Guessing Game

Post by yatsen » Sat Dec 11, 2010 12:49 pm

Can someone put more test input and output?

dolle39
New poster
Posts: 1
Joined: Thu Mar 28, 2013 5:42 pm

Guessing Game - 11843

Post by dolle39 » Thu Mar 28, 2013 6:04 pm

I am not sure I understand the rules correctly for this problem. The problem talks about strikes. For example for the case N = 7 and S = 2. We first have the numbers;

0 1 2 3 4 5 6

We then of course first guess 3 since this halves the guessing space. In the next step we have S = 1 so then we will not be told if we guessed higher or lower. Thus we guess 2. What happens after this? Do I get new guesses? In the next step I would then perhaps guess 1 and then if necessary we guess 0. Thus to cover all possible numbers we need 4 guesses which agrees with the example output.

What would the result be for N = 15 and S = 2?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: Guessing Game - 11843

Post by brianfry713 » Thu Mar 28, 2013 10:48 pm

Read the problem statement again, a guess results in either a smile, a stop, or a strike.
Also read: http://online-judge.uva.es/board/viewtopic.php?t=50731
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 118 (11800-11899)”