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
#include<iostream>
#include<string>
#include<vector>
#include<cstring>
using namespace std;
const int MAX = 1000111;
long k[MAX], n, m;
string s;

vector<int> cykl[MAX];
bool dbg = false;
int main() {
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> k[i];
  };
  cin >> m;
  cin >> s;
  
  int x = 0;
  bool bez_cyklu = true, first = true;
  while (bez_cyklu) {
  for (int i = 0; i < n; ++i) {
	  cykl[i].push_back(x);
	  x = (x+1)%m;
  };
  if (cykl[0][0]==cykl[0][cykl[0].size()-1] && !first) bez_cyklu = false;
  first = false;
  };

  int bestret = -1, odp = -1;
  int gdzie_sa_min[MAX];
  for (int i = 0; i < n; ++i) {
	  memset(gdzie_sa_min, 0, sizeof(gdzie_sa_min));
	  if (dbg) cout << i << ": ";
	  int ile = 0, ile_min = 0, gdzie = 0;
	  for (int j = 0; j < cykl[i].size()-1; ++j) {
		  if (s[cykl[i][j]]=='W') {
			  ile++;
		  } else {
			  ile--;
			  if (ile<ile_min) { ile_min = ile; gdzie = j; }
			  if (ile<0 && gdzie_sa_min[-ile]==0){
				  gdzie_sa_min[-ile]=j+1;
				  if (dbg) cout << "GDZIE[" << -ile << "]=" << j << ";";
			  };
		  };
		  if (dbg) cout << cykl[i][j] << "(" << ile << "),";
	  };
//	  cout << ".. cykl=" << cykl[i][cykl[i].size()-1] << endl;

	  int ret = -1;
	  if (k[i] + ile_min <= 0) {
		  ret = 0;
	  } else if (ile>=0) {
		  ret = -1;
	  } else {
	          ret = (-k[i] - ile_min)/ile;
	  };
	  if (dbg) cout << "pelnych cykli = " << ret;
	  if (ret >= 0 && (ret <= bestret || bestret == -1)) {
		  bestret = ret;
		  int zostalo = k[i] + ret * ile;
		  int tmp_odp = ret * (cykl[i].size()-1) * n + (n*(gdzie_sa_min[zostalo]-1)) + i+1;//gdzie_sa_min[zostalo];
		  if (dbg) cout << " bestodp=" << tmp_odp;

		  if (dbg) cout << "[na starcie=" << k[i] << " pelnych cykly=" << ret << " to zostalo " << zostalo << "]";
		  if (odp==-1 || odp>tmp_odp) odp=tmp_odp;
	  };
	  if (dbg) cout << endl;
/*          if (s[cykl[i][0]]=='W')
		  ile++;
	  else
		  ile--;*/
//	  cout << " .." << ile_min << endl;
  };

  cout <<odp;
}