10217 - A Dinner with Schwarzenegger!!!

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!!!

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..

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

Hi!

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...

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

Good Luck

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
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!

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&#8217;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

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

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

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am
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
Contact:

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm
congrats to Schwarzenegger for winning the election thing

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 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
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: