10826 - Hot or Cold?

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

Moderator: Board moderators

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Hot and Cold - Problem G in recent contest (10826)

Post by Observer » Wed Mar 09, 2005 6:56 am

Hi,

I've read problem G in the recent contest, and I find it quite interesting. Although I haven't attempted this task, I would like to know whether there exists a greedy solution. This is because I'm writing a number-guessing task similar to this (not a decision-making one though), and I want to make sure that the "guessing method" stated in that doesn't solve this task. :P

Thanks in advance. :wink:

- EDIT -

Since no one replies, I assume that there aren't any greedy / trivial solutions to this task. Should that be true, I'll continue writing my task. :wink:

Bye~
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Mar 11, 2005 8:38 am

I believe there is greedy or some other kind of deterministic method to make correct guesses for this problem. Since, the performance the of the code of the top solvers is incredibly fast. They take only 0s. For the rest who solve the problem in standard way (well.. I believe we all solve it in pretty much the same way) take more than 1s. It's a huge gap.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Mar 11, 2005 1:39 pm

Well.... I would guess they are sending a table....Just 300 numbers
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Mar 11, 2005 3:43 pm

I see.
I've forgot this option...

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

10826 - Hot or Cold?

Post by Dreamer#1 » Sun Mar 13, 2005 7:23 pm

can someone please verify the following intput/outputs. thanks.

Code: Select all


Intput:

1
2
3
4
5
6
7
8
9

Output:

1
3
4
5
5
6
6
6
7


User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sun Mar 13, 2005 8:18 pm

My output:

Code: Select all

1 guess(es) required.
3 guess(es) required.
4 guess(es) required.
5 guess(es) required.
5 guess(es) required.
5 guess(es) required.
6 guess(es) required.
6 guess(es) required.
6 guess(es) required.

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Mar 13, 2005 9:02 pm

thanks bro got AC :)

but what a stupid copy-pasting error i made :(

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » Sun Mar 13, 2005 9:47 pm

Can you please give me some hints. :)

Ibrahim

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Sun Mar 13, 2005 10:18 pm

if i'm not wrong you are from Bd, the truck behind you in the pic tells me that and most probably you are new to problem solving.
i'm sorry but i think the best hint i can give you is try the other problems first. its not a very easy problem as you might have thought at the first look. never mind may be someday you will solve even tougher problems than this one so be patient and keep solving.

best of luck

User avatar
ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim » Mon Mar 14, 2005 3:40 am

Dreamer#1 wrote:if i'm not wrong you are from Bd, the truck behind you in the pic tells me that and most probably you are new to problem solving.
i'm sorry but i think the best hint i can give you is try the other problems first. its not a very easy problem as you might have thought at the first look. never mind may be someday you will solve even tougher problems than this one so be patient and keep solving.

best of luck
Thanks Dreamer. You are right, I am from bd.:D And i will try to follow your hints. :wink:

DreamLinuxer
New poster
Posts: 8
Joined: Tue Oct 01, 2002 3:22 pm

Post by DreamLinuxer » Sat Apr 09, 2005 10:07 am

Could someone give me some hint please.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » Tue Apr 12, 2005 8:47 pm

only hint that I wish to give is that the problem says n <=300, think about this!!

galkovsk
New poster
Posts: 3
Joined: Fri Apr 08, 2005 9:15 am

Post by galkovsk » Wed Apr 20, 2005 3:33 pm

Hm. I can't find an explanation, why my program gets WA. Maybe, someone can verify my output? Everything, posted on this forum is as mine ouput.

Here is input:

Code: Select all

9
10
17
18
27
28
60
65
68
70
73
75
300
0
MY output:

Code: Select all

6
7
7
8
8
9
10
10
10
10
10
10
13
Thanks, for your help.

ranjit
New poster
Posts: 34
Joined: Fri Jan 30, 2004 11:22 am
Location: india

Hi

Post by ranjit » Tue Jul 26, 2005 10:03 am

This is my output.

Code: Select all

6 guess(es) required.
7 guess(es) required.
7 guess(es) required.
7 guess(es) required.
8 guess(es) required.
8 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
10 guess(es) required.
13 guess(es) required.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Aug 10, 2005 2:16 pm

In which catagorie does this problem fall into ?

Is this some sort of DP..
.. doesn't look so.

Post Reply

Return to “Volume 108 (10800-10899)”