10217  A Dinner with Schwarzenegger!!!
Moderator: Board moderators

 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..
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..
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...
Meanwhile check your program ...
Maybe I am wrong but I think that my solution is correct..
Good Luck
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
Hi!
Hi!
I think that the problem is in the task descripcion it is written there :
Maybe this is this problem ??
I think that the problem is in the task descripcion it is written there :
But the question is: for the second guy in this queue should we compare his date with ticket seller's ??. To give the guy at the front of the queue some chance, his birthday will be compared with the ticket seller’s birthday.
Maybe this is this problem ??
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 ticketseller'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 * (ni) / 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]
[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 * (ni) / 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]

 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:
Output:
mafattah: we differ in the last case. The actual number I got is 255.4985, which rounds to 255..
Input:
Code: Select all
30
50
60
1000
961
962
970
100000
51252
7245
65736
65535
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

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Perhaps my output will help you:
Good luck!
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

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
Hey, I don't quite understand what the problem is about......
e.g.::::::
[quote]"If someone
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
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
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 noninteger 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.
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 noninteger 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.

 Experienced poster
 Posts: 147
 Joined: Fri Jun 13, 2003 10:46 pm
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)=(1p(1))*(2/N) to win, p(3)=(1p(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.
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)=(1p(1))*(2/N) to win, p(3)=(1p(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.
Can anyone tell some more hint on this problem?
As dumb dan say, p(2)=(1p(1))*(2/N) to win, p(3)=(1p(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
As dumb dan say, p(2)=(1p(1))*(2/N) to win, p(3)=(1p(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.