1
0

tanks_2.cpp 2.5 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <memory.h>
  4. #include <math.h>
  5. #define Eps 1e-10
  6. #define MAXN 100
  7. #define oo 1990518000
  8. double H[MAXN], hi[MAXN], sum[MAXN];
  9. double nowh[MAXN];
  10. int testID, N;
  11. double ans;
  12. int work2(int pos, double V, double P) {
  13. double a, b, c, t1, t2, delta;
  14. // V * P / (V - x) - 1 = 0.097 * (H[0] - nowh[pos] - x);
  15. a = 0.097;
  16. b = - (1 + 0.097 * (H[0] - nowh[pos])) - 0.097 * V;
  17. c = (1 + 0.097 * (H[0] - nowh[pos]) - P) * V;
  18. delta = sqrt(b * b - a * c * 4);
  19. t1 = (-b - delta) / (a * 2);
  20. t2 = (-b + delta) / (a * 2);
  21. if (t1 > -Eps) nowh[pos] += t1;
  22. else nowh[pos] += t2;
  23. return 0;
  24. }
  25. int work(int left, double P) {
  26. double rest, V, t;
  27. int k;
  28. work2(left, sum[left] - nowh[left], P);
  29. if (nowh[left] < hi[left + 1]) return 0;
  30. nowh[left] = hi[left + 1];
  31. P = P * (sum[left] - hi[left]) / (sum[left] - nowh[left]);
  32. V = sum[left] - nowh[left];
  33. rest = V - P * V / (1 + 0.097 * (H[0] - nowh[left]));
  34. for (int i = left + 1; i < N; i ++) {
  35. if (rest < hi[i] && rest < hi[i + 1]) {
  36. nowh[i] = rest; return 0;
  37. }
  38. if (hi[i + 1] <= hi[i]) {
  39. nowh[i] = hi[i + 1];
  40. P = P * V / (V - nowh[i]);
  41. V -= nowh[i];
  42. rest -= nowh[i];
  43. } else {
  44. nowh[i] = hi[i];
  45. P = P * V / (V - nowh[i]);
  46. V -= sum[i];
  47. work(i, P);
  48. k = i;
  49. break;
  50. }
  51. }
  52. for (int i = k - 1; i >= left + 1; i --) {
  53. t = V - P * V / (1 + 0.097 * (H[0] - nowh[left]));
  54. if (nowh[i] + t < hi[i]) {
  55. nowh[i] += t; return 0;
  56. }
  57. P = P * V / (V - hi[i] + nowh[i]);
  58. V -= H[i] - nowh[i];
  59. nowh[i] = hi[i];
  60. work2(i, H[i] - nowh[i], P);
  61. }
  62. work2(left, V, P);
  63. }
  64. int main() {
  65. freopen("tanks.in", "r", stdin);
  66. freopen("tanks.out", "w", stdout);
  67. while (scanf("%d", &N) && N) {
  68. for (int i = 0; i < N; i ++) {
  69. scanf("%lf", &H[i]);
  70. }
  71. sum[N] = 0;
  72. for (int i = N - 1; i >= 0; i --) {
  73. sum[i] = H[i] + sum[i + 1];
  74. }
  75. for (int i = 1; i < N; i ++) {
  76. scanf("%lf", &hi[i]);
  77. }
  78. hi[N] = 0;
  79. memset(nowh, 0, sizeof(nowh));
  80. nowh[0] = H[0];
  81. for (int i = 1; i < N; i ++) {
  82. nowh[i] = hi[i];
  83. if (hi[i] >= hi[i + 1]) {
  84. work2(i, H[i] - nowh[i], 1);
  85. } else {
  86. hi[N] = oo;
  87. work(i, 1);
  88. break;
  89. }
  90. }
  91. ans = 0;
  92. for (int i = 0; i < N; i ++) {
  93. ans += nowh[i];
  94. }
  95. printf("Case %d: %.3lf\n\n", ++ testID, ans);
  96. }
  97. return 0;
  98. }