Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <string>
- #include <fstream>
- #include <algorithm>
- using namespace std;
- int F,R,F1,F2,R1,R2;
- double nF[11],nR[11];
- double nres[121];
- double ansF[121],ansR[121];
- double minvar = 0x7fffffff;
- bool cmp(double i, double j)
- {
- return (i<j);
- }
- void calculat()
- {
- if (nF[0]==25&&nF[1]==53&&nR[0]==28&&nR[1]==40)
- {
- int a = 1;
- }
- if (nF[F-1]*nR[R-1]<3.0*nR[0]*nF[0])
- {
- //PRUNE
- return;
- }
- int i = 0;
- for (int r = R-1; r>=0; r--)
- {
- for (int f = 0; f<F; f++)
- {
- nres[i++] = nF[f]/nR[r];
- }
- }
- //sort
- sort(nres,nres+F*R,cmp);
- for (int j = 0; j<i-1; j++)
- {
- nres[j] = nres[j+1] - nres[j];
- }
- //
- double sum1 = 0;
- double sum2 = 0;
- for (int j = 0; j<i-1; j++)
- {
- sum1 += nres[j];
- sum2 += nres[j]*nres[j];
- }
- double count = i-1;
- sum1/= count;
- sum2/= count;
- double var = sum2 - sum1*sum1;
- if (var<minvar)
- {
- for (int r = 0 ; r<R ; r++)
- {
- ansR[r] = nR[r];
- }
- for (int f = 0 ; f<F ; f++)
- {
- ansF[f] = nF[f];
- }
- minvar = var;//DO NOT FORGET!!
- }
- }
- void BTR(int k,int next)
- {
- if (k==R)
- {
- calculat();
- return;
- }
- for (int i = next; i<=R2-(R-k-1); i++)
- {
- nR[k] = i;
- BTR(k+1,i+1);
- }
- }
- void BTF(int k,int next)
- {
- if (k==F)
- {
- BTR(0,R1);
- return;
- }
- for (int i = next; i<=F2-(F-k-1); i++)
- {
- nF[k] = i;
- BTF(k+1,i+1);
- }
- }
- int main()
- {
- ifstream fin("cowcycle.in");
- ofstream fout("cowcycle.out");
- fin>>F>>R>>F1>>F2>>R1>>R2;
- //backtrack
- BTF(0,F1);
- //output
- string sep = "";
- for (int f = 0 ; f<F ; f++)
- {
- fout<<sep<<ansF[f];
- sep = ' ' ;
- }
- fout<<endl;
- sep = "";
- for (int r = 0 ; r<R ; r++)
- {
- fout<<sep<<ansR[r];
- sep = ' ';
- }
- fout<<endl;
- fin.close();
- fout.close();
- return 0;
- }
Add Comment
Please, Sign In to add comment