AOJ-ICPC 2149 - 備忘録

今日はこの問題。

毎フレーム表示される数字が変わるスロットで、どのフレームでボタンを押せば最も早くスロットをそろえられるかという問題。
一つ前の数字をx、次の数字をx'とすると、x' = (a * x + b) % cで表されるそうです(a,b,cは与えられた数字)。
ただし揃うまでのフレーム数が10000を越えたら揃えることはできないものとして-1を返すことにします。

答えはこちら。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
  
using namespace std;
 
int main()
{
    int n, a, b, c, x;
    while(1){
        cin >> n >> a >> b >> c >> x;
        if(n == 0) break;
        int cnt = 0;
        int y[100];
        for(int i = 0; i < n; i++){
            cin >> y[i];
        }
        for(int i = 0; i < n; i++){
            while(x != y[i]){
                cnt++;
                x = (a * x + b) % c;
                if(cnt > 10000) break;
            }
            if(cnt > 10000){
                cnt = -1;
                break;
            }
            if(i != n - 1) cnt++;
            x = (a * x + b) % c;
        }
        cout << cnt << endl;
    }
    return 0;
}

スロットで次に止める値と乱数が一致するまで乱数を変更していきます。その回数をcntに保存しています。
cntが10000を越えたらそこで強制的に終了しcntの値を-1とします。
値と乱数が一致したとき、最後のリールでない場合ではcntの値を1増やしてxの値を変更します。
最終的にcntが答えとなります。

昔これを解いたときは最初にTLEしまくっていた覚えがあるのですが、今回はすっと通ったのでよかったです。