TOI16: Dino Wheel of Destiny

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 9 + 5;
const int L = 99 + 5;

string str[N];
lli dp[N];
int n, tr;
char tmp[L];

lli __lcm(lli a, lli b){
    return a / __gcd(a, b) * b;
}

lli mn = 1e18;
void recur(int i, lli mve){
    if(i == n + 1){
        mn = min(mn, mve);
        return;
    }
    for(lli j = 0; j <= dp[i]; j += dp[i - 1]){
        if(str[i][(j + mve) % str[i].size()] == tr + '0'){
            if(j + mve >= mn){
                return;
            }
            recur(i + 1, j + mve);
        }
    }
}

int main(){

    scanf("%d%d", &n, &tr);
    for(int i = 1; i <= n; ++i){
        scanf(" %s", tmp);
        str[i] = string(tmp);
    }
    dp[0] = 1;
    for(int i = 1; i <= n; ++i){
        dp[i] = __lcm(str[i].size(), dp[i - 1]);
    }
    recur(1, 1);
    cout << mn;

    return 0;
}