|
|
Page 1 So I've made an embarrassingly large number of submissions for this problem. Thing is I submitted in C++ 11 and got WA 1. Afterwards I switched to Visual C++/G++ and got WA 2. Apparently this was caused by asserts that I had left in my program to check if test 1 is actually the example. After I removed them I got Accepted, but still WA 1 in C++11. So my questions would be: 1. Why did it get WA in C++ 11? 2. Why didn't the assert crash the program? Something happened with the checker, probably. Submittal of a correct solution now results in WA 2. Yes. Answers in exponential form are considered to be incorrect in the current moment. We'll investigate this problem. if k < m return 0 else amount of 'good' results is equal to С(m), wher C() - Catalanas number amount of 'bad' results is equal to sum(i = 0.. m, C(i)) for example for m = 3 ( - big brother acts ) - smal brothers acts good results are (independent of k) ((())) (()()) (())() ()(()) ()()() bad results are (()) ) ()() ) () ) ) now we should calculate C(m) / sum(i = 0.. m, C(i)) C(m) / sum(i = 0.. m, C(i)) = 1 / (sum(i = 0.. m, C(i)) / C(m)) = = 1 / sum(i = 0.. m, C(i) / C(m)) = = 1 / sum( i = 0.. m, exp(ln(C(i)) - ln(C(m))) ) We can calculate ln(C(i)) using formula C(i) = F(2 * i) / F(i) / (i + 1), where F(N) = N! ln(C(i)) = ln(F(2 * i)) - ln(F(i)) - ln(i + 1) ln(F(i)) = sum(j = 1.. i, ln(j)) now we can calculate sum( i = 0.. m, exp(ln(C(i)) - ln(C(m))) ) accurate to some EPS, and can calculate answer for the task with some EPS. I tryed to pass this algo, and it doesn't take AC. Does it wrang algorithm? or it is not enought accurate? Edited by author 12.03.2009 17:59 Edited by author 17.08.2008 22:54 I found it in Shen's book (2004, Moscow) on 58 page (exercise 2.7.3). Actually answer is equal to (C^K_(M+K) - C^(K+1)_(M+K)) / C^K_(M+K) = 1 - M / (K+1). Also u should output 0 if M > K + 1 P.S. C^K_N = N!/(N-K)!/K! Edited by author 05.10.2008 14:59 More reach sources: Ballot problem in Internet. More useful information is all about random walking. For example the problem 1148 Building towers very similar but unsolved by many people. I am new here, so i am not understanding the output format of this problem ( how many digit after the decimal point). could anyone please tell me about this........... Edited by author 17.08.2008 16:38 Use printf("%.6lf\n",value); in C See FAQ, there's an entry about that. I don't know whats wrong with it Program b; {$APPTYPE CONSOLE} uses SysUtils; var n,k,i,m:integer; Begin readln(n); for i:=1 to n do begin readln(k,m); if k=m then begin writeln(1/(k+1):0:6); end else if m>k then writeln('0') else writeln(k/(k+m):0:6); end; End. Why do you write : if(k==m) return 1/(k+1) ? if k=m=4, what do you return? Edited by author 17.08.2008 16:52 because if any moment the Bob's money is greater than this of Alex,Alex breaks all the windows. 0 0 0 0 -- Alex's good deeds 1 1 1 1 -- Bob's good deeds if the first time Bob do the good deed (or Mother gives the Bob first 1 euro),at this time Alex breaks all the windows. So first time Alexs deed must be choosen and so on. If you follow to this way you can get this formula for k=m. problablity=1/(k+1); Edited by author 17.08.2008 17:12 Edited by author 17.08.2008 17:13 Your formulae for the case k > m is not right... Can You give an example test void solve (int p) { float q; if (a[p].alex==a[p].bob) q=1.0/(a[p].alex+1.0); else q=a[p].alex/(a[p].bob+a[p].alex); cout<<q<<endl;} Where am I wrong? m>k the answer is 0; Are you sure? thanks Vedernikoff Sergey (HSE: EconomicsForever!). I was wrong for this case. The answer is 0.5 for your test not 3/5. thanks Vedernikoff Sergey (HSE: EconomicsForever!). I was wrong for this case. The answer is 0.5 for your test not 3/5. Why?How? I think that if k>m then the answer doesn`t depend on k, isn`t it? if k>m Probability=(k-m+1)/(k+1) How did you get it? Do you divide nubmer of successive sequences to number of possibe sequences? Yes I have found it by this way You may think of it as of number of paths from (0;0) to (k;m) which do not cross main diagonal. There are a total of C(x, x+y) paths. If you try to find recurrent formula for f(x,x), you'll see that it is some sort of convolution over f(1)...f(x-1) which usually refers to Cathalan numbers (Sk = C(x, 2x) / (x+1)), so they are a good guess. Actually f(x,x) = Sx, it can be proven by induction. So, the probability for f(x,x) is 1/(x+1). Probability for f(x,y), y>x can be guessed and proven by induction as well. The general recurrent formula is: f(x,y) = f(x-1,y) + f(x,y-1) for x>0, y>x f(x, x) = f(x-1, x) for x>0 f(0,y) = 1 for y>=0 Edited by author 08.09.2008 03:58 Take almost any example and explore it. For example, your formula gives wrong answer on the input k=3 and m=2. What`s the right answer? Edited by author 17.08.2008 17:31 Can you tell me the 2nd test Write inefficient (but correct) solution and you will be able to generate tests yourself. #include <iostream> using namespace std; int main() { int n,k,m; cin>>n; while(n) { cin>>k>>m; if(!k && !m) cout<<"1\n"; else if(k<m) cout<<"0\n"; else cout<<(float)k/(k+m)<<endl; n--; } return 0; } Edited by author 17.08.2008 15:09 I have the same problem #include <iostream> using namespace std; struct money { double alex,bob;}; money a[2005]; int n; void solve (int p) { float q; if (a[p].alex==a[p].bob) q=1/(1+a[p].alex); // else if (a[p].bob>a[p].alex) q=0; else q=a[p].alex/(a[p].bob+a[p].alex); cout<<q<<endl;} int main () { cin>>n; for (int i=0;i<n;i++) cin>>a[i].alex>>a[i].bob; for (int i=0;i<n;i++) solve (i); return 0; } Where am I wrong? Edited by author 17.08.2008 16:54 I have got an error --Crash(floating-point invalid operation)-- on the 2nd test. what does this mean? May be, division by zero? I have got WA on test2. Can you tell me what this test is? Pages: 1 |
|
|