mickypinata

TOI16: Dino Wheel of Destiny

Nov 25th, 2021
311
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 9 + 5;
  7. const int L = 99 + 5;
  8.  
  9. string str[N];
  10. lli dp[N];
  11. int n, tr;
  12. char tmp[L];
  13.  
  14. lli __lcm(lli a, lli b){
  15.     return a / __gcd(a, b) * b;
  16. }
  17.  
  18. lli mn = 1e18;
  19. void recur(int i, lli mve){
  20.     if(i == n + 1){
  21.         mn = min(mn, mve);
  22.         return;
  23.     }
  24.     for(lli j = 0; j <= dp[i]; j += dp[i - 1]){
  25.         if(str[i][(j + mve) % str[i].size()] == tr + '0'){
  26.             if(j + mve >= mn){
  27.                 return;
  28.             }
  29.             recur(i + 1, j + mve);
  30.         }
  31.     }
  32. }
  33.  
  34. int main(){
  35.  
  36.     scanf("%d%d", &n, &tr);
  37.     for(int i = 1; i <= n; ++i){
  38.         scanf(" %s", tmp);
  39.         str[i] = string(tmp);
  40.     }
  41.     dp[0] = 1;
  42.     for(int i = 1; i <= n; ++i){
  43.         dp[i] = __lcm(str[i].size(), dp[i - 1]);
  44.     }
  45.     recur(1, 1);
  46.     cout << mn;
  47.  
  48.     return 0;
  49. }
  50.  
RAW Paste Data