Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on May 5th, 2012  |  syntax: C++  |  size: 2.82 KB  |  hits: 13  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include <string>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <queue>
  6. #include <stack>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <cassert>
  10. #include <iostream>
  11. #include <sstream>
  12. #include <cstddef>
  13. #include <algorithm>
  14. #include <utility>
  15. #include <iterator>
  16. #include <numeric>
  17. #include <list>
  18. #include <complex>
  19. #include <cstdio>
  20. #include <climits>
  21. #include <fcntl.h>
  22. #include <unistd.h>
  23.  
  24. using namespace std;
  25.  
  26. typedef vector<int> vi;
  27. typedef vector<string> vs;
  28. typedef long long ll;
  29. typedef complex<double> pnt;
  30. typedef pair<int, int> pii;
  31.  
  32. #define RA(x) (x).begin(), (x).end()
  33. #define FE(i, x) for (typeof((x).begin()) i = (x).begin(); i != (x).end(); i++)
  34. #define SZ(x) ((int) (x).size())
  35.  
  36. template<class T>
  37. void splitstr(const string &s, vector<T> &out)
  38. {
  39.     istringstream in(s);
  40.     out.clear();
  41.     copy(istream_iterator<T>(in), istream_iterator<T>(), back_inserter(out));
  42. }
  43.  
  44. template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
  45.  
  46. static void redirect(int argc, const char **argv)
  47. {
  48.     if (argc > 1)
  49.     {
  50.         int fd = open(argv[1], O_RDONLY);
  51.         if (fd == -1) { perror(argv[1]); exit(1); }
  52.         if (-1 == dup2(fd, 0)) { perror(argv[1]); exit(1); }
  53.         if (-1 == close(fd)) { perror(argv[1]); exit(1); }
  54.     }
  55.  
  56.     if (argc > 2)
  57.     {
  58.         int fd = open(argv[2], O_WRONLY | O_CREAT, 0666);
  59.         if (fd == -1) { perror(argv[2]); exit(1); }
  60.         if (-1 == dup2(fd, 1)) { perror(argv[2]); exit(1); }
  61.         if (-1 == close(fd)) { perror(argv[2]); exit(1); }
  62.     }
  63. }
  64.  
  65. int main(int argc, const char **argv)
  66. {
  67.     redirect(argc, argv);
  68.  
  69.     int cases;
  70.     cin >> cases;
  71.     for (int cas = 0; cas < cases; cas++)
  72.     {
  73.         int N;
  74.         cin >> N;
  75.         vector<int> J(N);
  76.         for (int i = 0; i < N; i++)
  77.             cin >> J[i];
  78.         int X = accumulate(RA(J), 0);
  79.         printf("Case #%d:", cas + 1);
  80.         for (int i = 0; i < N; i++)
  81.         {
  82.             double L = 0.0;
  83.             double R = 1.0;
  84.             while (R - L > 1e-9)
  85.             {
  86.                 double Yi = (L + R) / 2.0;
  87.                 double M = Yi;
  88.                 double score = J[i] + X * Yi;
  89.                 double Yt = Yi;
  90.                 for (int j = 0; j < N; j++)
  91.                     if (j != i)
  92.                     {
  93.                         double y = (score - J[j]) / X;
  94.                         if (y > 1.0)
  95.                             goto safe;
  96.                         if (y < 0.0)
  97.                             y = 0.0;
  98.                         Yt += y;
  99.                     }
  100.                 if (Yt > 1.0)
  101.                     goto safe;
  102.                 L = M;
  103.                 continue;
  104. safe:
  105.                 R = M;
  106.             }
  107.             printf(" %.6f", L * 100);
  108.         }
  109.         printf("\n");
  110.     }
  111.     return 0;
  112. }
create a new version of this paste RAW Paste Data