daily 2

CF 792E

void solve(){
  string s;
  cin>>s;
  int n=s.size();
  s=')'+s;
  vector dp(n+1,vector<ll>(3,INF)),trace(dp);
  if(n==1){
    if((s[1]-'0')%3==0)cout<<s[1]<<'\n';
    else cout<<-1<<'\n';
    return;
  }
  dp[1][0]=1;
  dp[1][(s[1]-'0')%3]=0;
  for(int i=2;i<=n;++i){
    int num=s[i]-'0';
    int rem=num%3;
    for(int j=0;j<3;++j){
        dp[i][j]=dp[i-1][j]+1;
        trace[i][j]=j;
        if(s[i]=='0'&&dp[i-1][j]==i-1)continue;
        if(dp[i-1][(j-rem+3)%3]<dp[i][j]){
            dp[i][j]=dp[i-1][(j-rem+3)%3];
            trace[i][j]=(j-rem+3)%3;
        }
    }   
  }
  if(dp[n][0]==n){
    for(int i=1;i<=n;++i){
        if(s[i]=='0'){
            cout<<s[i]<<'\n';
            return;
        }
    }
    cout<<-1<<'\n';
    return;
  }
  int pre;
  vector<char>ans;
  for(int i=n,j=0;i>=2;j=pre,--i){
    pre=trace[i][j];
    if(dp[i-1][pre]==dp[i][j]){
        ans.push_back(s[i]);
    }
  }
  if((s[1]-'0')%3==pre){
    ans.push_back(s[1]);
  }
  for(int i=ans.size()-1;i>=0;--i){
    cout<<ans[i];
  }
  return;
}

CF 797E

void solve(){
  int n;
  cin>>n;
  int m=sqrt(n);
  for(int i=1;i<=n;++i)cin>>a[i];
  for(int i=n;i>=1;--i){
    for(int j=1;j<=m;++j){
        if(i+a[i]+j>n){
            dp[i][j]=1;
        }else{
            dp[i][j]=dp[i+a[i]+j][j]+1;
        }
    }
  }
  int q;
  cin>>q;

  while(q--){
    int p,k;
    cin>>p>>k;
    if(k<=m){
        cout<<dp[p][k]<<'\n';
    }else{
        int ans=0;
        while(p<=n){
            ++ans;
            p+=a[p]+k;
        }
        cout<<ans<<'\n';
    }
  } 
  return;
}