Page 1 of 2

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

Posted: Wed Mar 09, 2005 6:56 am
by Observer
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~

Posted: Fri Mar 11, 2005 8:38 am
by Cho
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.

Posted: Fri Mar 11, 2005 1:39 pm
by ..
Well.... I would guess they are sending a table....Just 300 numbers

Posted: Fri Mar 11, 2005 3:43 pm
by Cho
I see.
I've forgot this option...

10826 - Hot or Cold?

Posted: Sun Mar 13, 2005 7:23 pm
by Dreamer#1
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


Posted: Sun Mar 13, 2005 8:18 pm
by Cho
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.

Posted: Sun Mar 13, 2005 9:02 pm
by Dreamer#1
thanks bro got AC :)

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

Posted: Sun Mar 13, 2005 9:47 pm
by ibrahim
Can you please give me some hints. :)

Ibrahim

Posted: Sun Mar 13, 2005 10:18 pm
by Dreamer#1
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

Posted: Mon Mar 14, 2005 3:40 am
by ibrahim
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:

Posted: Sat Apr 09, 2005 10:07 am
by DreamLinuxer
Could someone give me some hint please.

Posted: Tue Apr 12, 2005 8:47 pm
by abishek
only hint that I wish to give is that the problem says n <=300, think about this!!

Posted: Wed Apr 20, 2005 3:33 pm
by galkovsk
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.

Hi

Posted: Tue Jul 26, 2005 10:03 am
by ranjit
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.

Posted: Wed Aug 10, 2005 2:16 pm
by sohel
In which catagorie does this problem fall into ?

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