Advertisement
Guest User

Untitled

a guest
May 4th, 2013
130
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.57 KB | None | 0 0
  1. /*
  2. * File:    main.cpp
  3. * Author:  Hrayr [HarHro94]
  4. * Problem:
  5. * IDE:     Visual C++ 2012
  6. */
  7. //#pragma comment(linker, "/STACK:66777216")
  8. #include <functional>
  9. #include <algorithm>
  10. #include <iostream>
  11. #include <sstream>
  12. #include <fstream>
  13. #include <cassert>
  14. #include <iomanip>
  15. #include <cstring>
  16. #include <cstdio>
  17. #include <string>
  18. #include <vector>
  19. #include <ctime>
  20. #include <queue>
  21. #include <stack>
  22. #include <cmath>
  23. #include <set>
  24. #include <map>
  25. using namespace std;
  26.  
  27. #define pb push_back
  28. #define mp make_pair
  29. #define all(v) (v).begin(), (v).end()
  30. #define sz(v) (int)(v).size()
  31. #define LL long long
  32. #define LD long double
  33.  
  34. #define FOR(i, n) for(int i = 0; i < n; ++i)
  35. #define FOR1(i, n) for(int i = 1; i <=n; ++i)
  36. #define FORD(i, n) for(int i = n - 1; i >= 0; --i)
  37. #define FORD1(i, n) for(int i = n; i >= 1; --i)
  38. #define FORA(i, a, b) for(int i = a; i <= b; ++i)
  39. #define FORDA(i, a, b) for(int i = a; i >= b; --i)
  40.  
  41. LD dp[407][407];
  42. int T, n, x, y;
  43.  
  44. int main()
  45. {
  46. #ifdef harhro94
  47.     freopen("input.txt", "r", stdin);
  48.     freopen("output.txt", "w", stdout);
  49. #endif
  50.  
  51.     cin >> T;
  52.     FOR1(test, T)
  53.     {
  54.         cin >> n >> x >> y;
  55.         int sum = 0;
  56.         int cur = 0;
  57.         int rank = 0;
  58.         while (sum + cur + cur + 1 <= n)
  59.         {
  60.             sum += cur + cur + 1;
  61.             rank++;
  62.             cur += 2;
  63.         }
  64.         n -= sum;
  65.         x = abs(x);
  66.         y = abs(y);
  67.         cout << "Case #" << test << ": ";
  68.         if (x + y <= 2 * rank - 2)
  69.         {
  70.             cout << fixed << setprecision(8) << 1.0 << endl;
  71.             continue;
  72.         }
  73.         if (n == 0 || x == 0 ||  x + y > 2 * rank)
  74.         {
  75.             cout << fixed << setprecision(8) << 0.0 << endl;
  76.             continue;
  77.         }
  78.         int need = y + 1;
  79.         int rest =  n - need;
  80.         int can = 2 * rank;
  81.         if (abs(need - rest) > 200)
  82.         {
  83.             cout << fixed << setprecision(8) << 0.0 << endl;
  84.             continue;
  85.         }
  86.         if (n == 2 * can)
  87.         {
  88.             cout << fixed << setprecision(8) << 1.0 << endl;
  89.             continue;
  90.         }
  91.         FOR(i, 407)
  92.         {
  93.             FOR(j, 407)
  94.             {
  95.                 dp[i][j] = 0.0;
  96.             }
  97.         }
  98.         dp[0][0] = 1.0;
  99.         FOR1(i, n)
  100.         {
  101.             FOR(j, can + 1)
  102.             {
  103.                 int ot = i - j;
  104.                 if (ot < 0 || ot > can)
  105.                 {
  106.                     continue;
  107.                 }
  108.                 if (ot == can)
  109.                 {
  110.                     dp[i][j] += 0.5 * dp[i - 1][j];
  111.                     if (j != 0)
  112.                     {
  113.                         dp[i][j] += dp[i - 1][j - 1];
  114.                     }
  115.                 }
  116.                 else if (j == can)
  117.                 {
  118.                     dp[i][j] += 0.5 * dp[i - 1][j - 1];
  119.                     dp[i][j] += dp[i - 1][j];
  120.                 }
  121.                 else
  122.                 {
  123.                     if (j == 0)
  124.                     {
  125.                         dp[i][j] = 0.5 * dp[i - 1][j];
  126.                     }
  127.                     else
  128.                     {
  129.                         dp[i][j] = 0.5 * (dp[i - 1][j - 1] + dp[i - 1][j]);
  130.                     }
  131.                 }
  132.             }
  133.         }
  134.         LD ans = 0.0;
  135.         FORA(i, need, can)
  136.         {
  137.             ans += dp[n][i];
  138.         }
  139.         cout << fixed << setprecision(8) << ans << endl;
  140.     }
  141.  
  142. #ifdef harhro94
  143.     cerr << fixed << setprecision(3) << "\nExecution time = " << clock() / 1000.0 << "s\n";
  144. #endif
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement