10217 - A Dinner with Schwarzenegger!!!

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

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

10217 - A Dinner with Schwarzenegger!!!

Post by soyoja » Mon Mar 04, 2002 11:17 pm

It's so strange..

I don't know why I got wrong answer.

If someone have accepted solution, please some output for these input data.

Here is my testing result...

100001
315.73 316
100000
315.73 316
10000
99.50 100
5000
70.21 70
1000
31.13 31
100
9.51 10
333
17.75 18
999
31.11 31
9999
99.50 99

Help me plz. And may god bless your problem solving.. :smile:

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

Post by cyfra » Mon Jun 17, 2002 3:19 pm

Hi!

I am just writing this task...

And my program now counts only the integer number and you have got some different answers than mine...

Look at these examples:
input yours mine

1000 31 32
999 31 32
9999 99 100


when I finish my program I will check the floating point answers...

Meanwhile check your program ...

Maybe I am wrong but I think that my solution is correct..


Good Luck :wink:

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Mon Jun 17, 2002 4:25 pm

your output ... if all numbers +1, then all match with mine,

eg.
100
10.51 11

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Hi!

Post by cyfra » Tue Jun 18, 2002 8:11 am

Hi!

I think that the problem is in the task descripcion it is written there :
. To give the guy at the front of the queue some chance, his birthday will be compared with the ticket seller’s birthday.
But the question is: for the second guy in this queue should we compare his date with ticket seller's ??

Maybe this is this problem ??

mafattah
New poster
Posts: 23
Joined: Fri Apr 26, 2002 1:00 am
Location: Cairo, Egypt

10217 - A Dinner with Schwarzenegger

Post by mafattah » Wed Oct 23, 2002 8:42 pm

I do not know how this code can ever generate wrong answer. I have written the code assuming that each person's birthdate is also compared with the ticket-seller's birthdate, but the program genrates just the right numbers with the test cases, and it fails if I assume anything else. Any help?
[cpp]
#include <iostream.h>
#include <math.h>
#include <iomanip.h>

double prob(int x, int n) {
double temp = x;
for (int i = 0; i < x; i++) {
temp = temp * (n-i) / n;
}
temp /= n;
return temp;
}

void main() {
cout << setprecision(2) << setiosflags(ios::fixed);
int n;
double x;
int intx;
while (cin >> n) {
x = -0.5 + sqrt(0.25+n);
intx = prob(floor(x), n) < prob(ceil(x), n) ? ceil(x) : floor(x);
cout << x << " " << intx << endl;
}
}
[/cpp]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Mon Nov 25, 2002 2:59 am

Can someone post some inputs/outputs? I think I have a close precision error..:

Input:

Code: Select all

30
50
60
1000
961
962
970
100000
51252
7245
65736
65535
Output:

Code: Select all

5.00 5
6.59 7
7.26 7
31.13 31
30.50 31
30.52 31
30.65 31
315.73 316
225.89 226
84.62 85
255.89 256
255.50 255
mafattah: we differ in the last case. The actual number I got is 255.4985, which rounds to 255..

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Mon Dec 02, 2002 10:10 am

Perhaps my output will help you:

Code: Select all

5.00 6
6.59 7
7.26 8
31.13 32
30.50 31
30.52 31
30.65 31
315.73 316
225.89 226
84.62 85
255.89 256
255.50 256
Good luck!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue Dec 03, 2002 5:47 pm

Thanks, got it AC after some very minor changes.

Why is that though? Wouldn't you want to round it?

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sat Dec 07, 2002 10:12 am

Yes, I wanted just to round it, but after some WA's I tried floor(x)+1 and got AC. Perhaps I don't understand smth, but it seems to be strange. :(

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

Post by Observer » Wed May 14, 2003 1:33 pm

Hey, I don't quite understand what the problem is about......

e.g.::::::
[quote]"If someone
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Wed Oct 08, 2003 6:19 pm

I may be dumb, but I have 2 major problems with the problem statement:

1) The theoretical value should be 0.5 more than the values given by the problemsetter in the sample output (this is also the reason why you have to use floor(x)+1 instead of round(x))

2) It doesn't say in the problem what to do if two integer values for x generate the same probability p(x) even though you need to pick the higher x value to get AC.

As a note, this is the third problem I noticed by Shahriar Manzoor that has major mathematical faults (10323 is one of the others).

As an actual answer doesn't exist for non-integer values for x, you can't really say that he is wrong. But I think everyone gets the idea that something is amiss when 5.00 (actually exactly the integer 5) is rounded to the integer value 6.

That's just my two cents.

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Wed Oct 08, 2003 7:44 pm

I want to know the theory behind this problem. Someone please help.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Wed Oct 08, 2003 10:46 pm

congrats to Schwarzenegger for winning the election thing :lol:

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Fri Oct 10, 2003 6:48 am

To clarify the problem:

Exactly one person in the ticket queue will win. A person will win if no person in front of him has won AND his/her birthday is the same as ANY one of the people in front of him.

So if there are N days in the year the first person will have a probability p(1)=1/N to win, second person will have probability p(2)=(1-p(1))*(2/N) to win, p(3)=(1-p(1)-p(2))*(3/N) and so on... and you need to find the highest p(x). (Just calculating the values for p will obviously lead to rounding errors for large N, hence the problem).

As for the part where you are asked to find the theoretical floating point value (this is actually a clue for finding the correct integer value without getting those rounding errors). Too bad though there are infinite ways to produce a floating point value from which you could derive the best integer value. As there is no explaination in the problem statement how we are to produce this value we can only ask ourselves: what formula do I have to apply to N to get x? Finding the formula is trivial, understanding why the problem setter picked that perticular formula (of an infinite number of possible formulas) is less trivial.

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

Post by .. » Tue Feb 24, 2004 3:08 pm

Can anyone tell some more hint on this problem?

As dumb dan say, p(2)=(1-p(1))*(2/N) to win, p(3)=(1-p(1)-p(2))*(3/N), etc.
I have no idea how to extend the idea to define the probability for a "floating point position". I think that ths problem only tells use how to define the probability on the integer posiition ONLY :(
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.

Post Reply

Return to “Volume 102 (10200-10299)”