Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 months ago
858 B
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

const int MAX = 5000;

int N, a[MAX], b[MAX], memo[MAX], me;
map<int, bool> mp;

int dp(int n) {
  if(n > 1000) return MAX;
  if(n < me) return MAX;
  if(memo[n] != -1) return memo[n];
  if(mp.count(n)) return 1;
  memo[n] = MAX;
  for(int i = 0; i < N; ++i) {
    if(b[i] - a[i] == 0 || a[i] > n) continue;
    memo[n] = min(memo[n], dp(n + (b[i] - a[i])) + 1);
  }
  return memo[n];
}

int main() {
  while(cin>>N && N) {
    memset(memo, -1, sizeof(memo));
    mp.clear();
    me = MAX;
    for(int i = 0; i < N; ++i) {
      cin>>a[i];
      me = min(me, a[i]);
      mp[a[i]] = 1;
    }
    for(int i = 0; i < N; ++i) {
      cin>>b[i];
    }
    int ans = (mp.count(100) ? 0 : dp(100));
    if(ans > 1000) cout<<"cavaleiro morreu\n";
    else cout<<ans<<'\n';
  }
}
Leave a Comment