#include <vector> #include <algorithm> #include <string> using namespace std; int main() { const long long int INF = 1000000000000000001LL; int n, m; scanf("%d", &n); vector < int > Money(n); vector < long long int > Turns(n); for(int i = 0; i < n; i++) scanf("%d", &Money[i]); scanf("%d", &m); char c; scanf("%c", &c); vector < int > Value(m); for(int i = 0; i < m; i++) { scanf("%c", &c); Value[i] = (c == 'W' ? 1 : -1); } /***********************************/ for(int i = 0; i < n; i++) { int start = i % m; int node = start; int cycle_sum = Value[start]; long long int turns = 1; int cycle_min = cycle_sum; if(Money[i] + cycle_sum <= 0) { Turns[i] = turns; continue; } node = (node + n) % m; bool to_outer = 0; while(node != start) { cycle_sum += Value[node]; if(cycle_sum < cycle_min) cycle_min = cycle_sum; turns ++; if(Money[i] + cycle_sum <= 0) { Turns[i] = turns; to_outer = 1; break; } node = (node + n) % m; } long long int cycle_size = turns; if(to_outer) continue; if(cycle_sum >= 0) { Turns[i] = -1; continue; } int cycles = ceil((Money[i] - abs(cycle_min)) / (double)abs(cycle_sum)); Money[i] += cycles * cycle_sum; turns = cycles * cycle_size; node = start; turns ++; Money[i] += Value[node]; node = (node + n) % m; while(Money[i] > 0) { Money[i] += Value[node]; turns ++; node = (node + n) % m; } Turns[i] = turns; } long long int min_turns = INF; for(int i = 0; i < n; i++) { if(Turns[i] != -1) { Turns[i] = (Turns[i] - 1) * n + i + 1; if(Turns[i] < min_turns) min_turns = Turns[i]; } } if(min_turns == INF) { printf("-1"); return 0; } printf("%lld", min_turns); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 | #include <vector> #include <algorithm> #include <string> using namespace std; int main() { const long long int INF = 1000000000000000001LL; int n, m; scanf("%d", &n); vector < int > Money(n); vector < long long int > Turns(n); for(int i = 0; i < n; i++) scanf("%d", &Money[i]); scanf("%d", &m); char c; scanf("%c", &c); vector < int > Value(m); for(int i = 0; i < m; i++) { scanf("%c", &c); Value[i] = (c == 'W' ? 1 : -1); } /***********************************/ for(int i = 0; i < n; i++) { int start = i % m; int node = start; int cycle_sum = Value[start]; long long int turns = 1; int cycle_min = cycle_sum; if(Money[i] + cycle_sum <= 0) { Turns[i] = turns; continue; } node = (node + n) % m; bool to_outer = 0; while(node != start) { cycle_sum += Value[node]; if(cycle_sum < cycle_min) cycle_min = cycle_sum; turns ++; if(Money[i] + cycle_sum <= 0) { Turns[i] = turns; to_outer = 1; break; } node = (node + n) % m; } long long int cycle_size = turns; if(to_outer) continue; if(cycle_sum >= 0) { Turns[i] = -1; continue; } int cycles = ceil((Money[i] - abs(cycle_min)) / (double)abs(cycle_sum)); Money[i] += cycles * cycle_sum; turns = cycles * cycle_size; node = start; turns ++; Money[i] += Value[node]; node = (node + n) % m; while(Money[i] > 0) { Money[i] += Value[node]; turns ++; node = (node + n) % m; } Turns[i] = turns; } long long int min_turns = INF; for(int i = 0; i < n; i++) { if(Turns[i] != -1) { Turns[i] = (Turns[i] - 1) * n + i + 1; if(Turns[i] < min_turns) min_turns = Turns[i]; } } if(min_turns == INF) { printf("-1"); return 0; } printf("%lld", min_turns); return 0; } |