Problem C : Flipping Frustration
Form uva,11312
确定最小的x－y之后判定在翻的中间过程中是否越界，用dfs深搜：能像右翻就一直翻到底，否则向左翻到底，不能翻了就gg
题意比较简单就不翻译了。参考了别人的代码，自己目前还不熟练。希望加油！
1 #include <iostream> 2 #include <cstdio> 3 #include <cmath> 4 5 using namespace std; 6 7 int x,y,gcd; 8 int n,l,r,t; 9 10 void extend_gcd(int a,int b) 11 { 12 if(b == 0) 13 { 14 a=1; 15 b=0; 16 gcd=a; 17 return; 18 } 19 extend_gcd(b,a%b); 20 int tmp=x; 21 x=y; 22 y=tmp-a/b*y; 23 } 24 25 bool dfs(int x,int y,int cur) 26 { 27 if(!x && !y) return 1; 28 int k=min(x, (n-cur)/r) 29 if(cur+r<=n && k) return dfs(x-k,y,cur+r*k); 30 k=min(y,cur/l); 31 if(k) return dfs(x,y-k,cur-l*k); 32 return 0; 33 } 34 35 int main() 36 { 37 int c; 38 scanf("%d",&c); 39 while(c--) 40 { 41 scanf("%d %d %d %d",&n,&l,&r,&t); 42 if(t==1) {puts("0");continue;} 43 extend_gcd(r,l); 44 t--;n--; 45 if(t%gcd){puts("uh-oh!");continue;} 46 int N=ceil(max(-1.0*x*t/l,1.0*y*t/r)); 47 x=(x*t+l*N)/gcd;y=(y*t-r*N)/gcd; 48 if(dfs(x,-y,0)) printf("%d\n",x-y); 49 else puts("uh-oh!"); 50 } 51 return 0; 52 }