2243-Step Step Evolution
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2243
考え方
最初に右足を置く場合と左足を置く場合があることに注意しつつ、
足の置き方が不正になる場合を数える。
実装(C++)
#include <cstring> #include <cstdio> char in[100001]; #define x(ch) ((((ch)-'1')%3)-1) int main(){ for(;~scanf("%s",in);){ if(in[0]=='#')break; int r,l,L=strlen(in),b=0,R,res=9999999; for(int k=0;k<2;k++){ r=3;l=-3;R=0;b=k; for(int i=0;i<L;i++){ if(!b){ if(x(in[i])>r){ R++; r=x(in[i]); }else{ l=x(in[i]); b=!b; } }else{ if(x(in[i])<l){ R++; l=x(in[i]); }else{ r=x(in[i]); b=!b; } } } if(res>R)res=R; } printf("%d\n",res); } return 0; }