codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; // will loop endlessly if a/b == c/d inline bool greaterOrEqualPositiveFraction(int a,int b,int c,int d); inline bool greaterPositiveFraction(int a,int b,int c,int d); inline bool greaterFraction(int a,int b,int c,int d); inline bool greaterOrEqualPositiveFraction(int a,int b,int c,int d) { if(b == 0) { return true; } if(d == 0) { return false; } if(a*d > b*c) { return true; } if(a*d < b*c) { return false; } return !greaterFraction(b,a%b,d,c%d); } inline bool greaterPositiveFraction(int a,int b,int c,int d) { if(d == 0) { return false; } if(b == 0) { return true; } if(a*d > b*c) { return true; } if(a*d < b*c) { return false; } return !greaterOrEqualPositiveFraction(b,a%b,d,c%d); } inline bool greaterFraction(int a,int b,int c,int d) { if(b<0) { b = -b; a = -a; } if(d<0) { d = -d; c = -c; } if(a<0 && c<0) { return greaterPositiveFraction(-c,d,-a,b); } if(a<0) { return false; } if(c<0) { return true; } return greaterPositiveFraction(a,b,c,d); } char seq[1000005]; int main() { int T; scanf("%d", &T); for(int t=0; t<T; t++) { memset(seq, '\0', 1000005); scanf("%s", seq); int sz = strlen(seq); int pus[sz], pyr[sz], cnt_pus=0, cnt_pyr=0; for(int i=0; i<sz; i++) { if(seq[i]=='A' || seq[i]=='G') { cnt_pus++; } else { cnt_pyr++; } pus[i] = cnt_pus; pyr[i] = cnt_pyr; } int max_pus=pus[0], max_pyr=pyr[0]; for(int i=0; i<sz; i++) { for(int j=i; j<sz; j++) { int num_pus = pus[j] - (i-1<0?0:pus[i-1]); int num_pyr = pyr[j] - (i-1<0?0:pyr[i-1]); // printf("[%d-%d]: %d/%d > %d/%d\n", i,j,num_pus,num_pyr,max_pus,max_pyr); if(num_pyr==0 && max_pyr==0) { max_pus = max(max_pus,num_pus); } else if(num_pyr==0) { // max sure wins } else if(max_pyr==0) { // num sure wins max_pus = num_pus; max_pyr = num_pyr; } else { // num_pyr!=0, max_pyr!=0 if(max_pus*num_pyr == num_pus*max_pyr) { // take longer sequence if(num_pus+num_pyr > max_pus+max_pyr) { max_pus = num_pus; max_pyr = num_pyr; } } else if(greaterFraction(num_pus,num_pyr,max_pus,max_pyr)) { max_pus = num_pus; max_pyr = num_pyr; } } } } printf("%d %d\n", max_pus,max_pyr); } return 0; }
Private
[
?
]
Run code
Submit