Guest User

Untitled

a guest
Feb 20th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1.  
  2. #include <string>
  3. #include <fstream>
  4. #include <algorithm>
  5. using namespace std;
  6. int F,R,F1,F2,R1,R2;
  7. double nF[11],nR[11];
  8. double nres[121];
  9. double ansF[121],ansR[121];
  10. double minvar = 0x7fffffff;
  11. bool cmp(double i, double j)
  12. {
  13. return (i<j);
  14. }
  15.  
  16. void calculat()
  17. {
  18. if (nF[0]==25&&nF[1]==53&&nR[0]==28&&nR[1]==40)
  19. {
  20. int a = 1;
  21. }
  22. if (nF[F-1]*nR[R-1]<3.0*nR[0]*nF[0])
  23. {
  24. //PRUNE
  25. return;
  26. }
  27. int i = 0;
  28. for (int r = R-1; r>=0; r--)
  29. {
  30. for (int f = 0; f<F; f++)
  31. {
  32. nres[i++] = nF[f]/nR[r];
  33. }
  34. }
  35. //sort
  36. sort(nres,nres+F*R,cmp);
  37.  
  38. for (int j = 0; j<i-1; j++)
  39. {
  40. nres[j] = nres[j+1] - nres[j];
  41. }
  42. //
  43. double sum1 = 0;
  44. double sum2 = 0;
  45. for (int j = 0; j<i-1; j++)
  46. {
  47. sum1 += nres[j];
  48. sum2 += nres[j]*nres[j];
  49. }
  50. double count = i-1;
  51. sum1/= count;
  52. sum2/= count;
  53.  
  54. double var = sum2 - sum1*sum1;
  55. if (var<minvar)
  56. {
  57. for (int r = 0 ; r<R ; r++)
  58. {
  59. ansR[r] = nR[r];
  60. }
  61. for (int f = 0 ; f<F ; f++)
  62. {
  63. ansF[f] = nF[f];
  64. }
  65. minvar = var;//DO NOT FORGET!!
  66. }
  67. }
  68. void BTR(int k,int next)
  69. {
  70. if (k==R)
  71. {
  72. calculat();
  73. return;
  74. }
  75. for (int i = next; i<=R2-(R-k-1); i++)
  76. {
  77. nR[k] = i;
  78. BTR(k+1,i+1);
  79. }
  80. }
  81. void BTF(int k,int next)
  82. {
  83. if (k==F)
  84. {
  85. BTR(0,R1);
  86. return;
  87. }
  88. for (int i = next; i<=F2-(F-k-1); i++)
  89. {
  90. nF[k] = i;
  91. BTF(k+1,i+1);
  92. }
  93. }
  94. int main()
  95. {
  96. ifstream fin("cowcycle.in");
  97. ofstream fout("cowcycle.out");
  98. fin>>F>>R>>F1>>F2>>R1>>R2;
  99.  
  100. //backtrack
  101.  
  102. BTF(0,F1);
  103.  
  104. //output
  105. string sep = "";
  106. for (int f = 0 ; f<F ; f++)
  107. {
  108. fout<<sep<<ansF[f];
  109. sep = ' ' ;
  110. }
  111. fout<<endl;
  112. sep = "";
  113. for (int r = 0 ; r<R ; r++)
  114. {
  115. fout<<sep<<ansR[r];
  116. sep = ' ';
  117. }
  118. fout<<endl;
  119.  
  120. fin.close();
  121. fout.close();
  122. return 0;
  123. }
Add Comment
Please, Sign In to add comment