Codeforces #175 Div2 B "Find Marble"
問題
考えた事
一回シャッフルして次のようになったとする
1 2 3 4 ↓ 2 3 1 4
後はこれをs->tまで何回でいけるのかたどっていく。
例えばs=2 t=1であれば
2->3 3->1となって2回シャッフルすればよい。
もしtに着く前にsに戻ってしまったら永久にたどり着けない。(s=4 t=2など)
シャッフル後はどんな位置になるのかは
何回か紙で試したところ、入力のp1, p2, ..., pnとまったく同じになる。
ソースコード
int after[100001]; int main() { int n, s, t; cin >> n >> s >> t; // s == tであればシャッフルの必要なし if( s == t ){ cout << 0 << endl; return 0; } // シャッフル後の配置入力 for( int i = 1; i <= n; i++ ){ in >> after[i]; } // たどっていく int p = s; int res = 0; while( p != t ){ p = after[p]; res++; if( p == s ) break; } if( p == s ) res = -1; cout << res << endl; }