問題
http://community.topcoder.com/stat?c=problem_statement&pm=1945&rd=4725
数字を合わせてロックを空ける回転式の鍵がある。
合わせるのに必要な数字の一覧が順に与えられ、数字の数も与えられる。
ロックを解除する操作は以下の通り。
１．回す方向を決める
２．合わせるのに必要な一覧の、残りの数だけ１回転させる
３．現在合わせる数字まで回転させる
４．次の回転は逆回り
最初にセットしてある数字が与えられるとき、ロックの解除までに必要な回転角度を求める。
解き方
問題文の理解に時間がかかったが、サンプルを例に試してみることで理解できた。
問題文の理解ができれば、あとはシミュレーション問題なので実装するだけ。
時計回りと反時計回りのときに数字を合わせるまでに動かす数だけ正確に実装できればあとは簡単。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CombinationLock {
public: double degreesTurned(vector<int> combo, int size, int start) {
double ret=0.0;
int n=combo.size();
int pos=start,dir=1;
FORE(i,0,n){
int dif= dir==1 ? (combo[i]+size-pos)%size :(pos+size-combo[i])%size;
ret+=(n-i)*360+dif*360.0/size;
dir*=-1;
pos=combo[i];
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class CombinationLock {
public: double degreesTurned(vector<int> combo, int size, int start) {
double ret=0.0;
int n=combo.size();
int pos=start,dir=1;
FORE(i,0,n){
int dif= dir==1 ? (combo[i]+size-pos)%size :(pos+size-combo[i])%size;
ret+=(n-i)*360+dif*360.0/size;
dir*=-1;
pos=combo[i];
}
return ret;
}
};