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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

#ifndef DEBUG
#define NDEBUG
#endif
#include<assert.h>

#ifdef DEBUG
#define log(format, ...)     fprintf(stderr, format "\n", ##__VA_ARGS__)
#else
#define log(...)
#endif


using namespace std;

class Node;

int n;
int m;
int* cash;
char* queue;
Node** node;    // mapa z liściami

/**
 * Pomocnicza funkcja oblicząjąca pozycję po steps krokach zaczynając od from
 */
int calcStep(int from, int steps) {
    return (int) ( ((int64_t)from+((int64_t)steps)*((int64_t)n) ) % (int64_t)m);   // jeden krok to przesunięcie o n (liczbę graczy)
}

/**
 * Pomocnicza funkcja wykonujaca dzielenie i
 * zwracajaca wynika zaokraglony do gory
 */
inline int divUp(int a, int b) { return (a+b-1)/b; }
inline int minVal(int a, int b) { return a<b?a:b; }
inline int maxVal(int a, int b) { return a>b?a:b; }

class Node {
public:
	Node* left;
	Node* right;
	Node* parent;
	int ch;		//!< Koszt przejscia tego fragmentu - jaki bedzie stan na koniec
	int from;	//!< Punkt początkowy dla tego obszaru
	int len;	//!< Długość tego obszaru
	int min;	//!< Ile nalezy miec na starcie, aby przejsc ten wierzcholek; czyli masymalny mozliwy dolek w tym fragmencie
	int index;  //!< nr kolejny tego węzła/liścia w ciągu
public:
    Node(Node* _parent, int _from, int _len) : left(NULL), right(NULL), parent(_parent), ch(0), from(_from), len(_len), min(0) {}

	inline bool isRoot() { return parent==NULL; }
	inline bool isLeaf() { return len==1; }
	inline bool isLeft(Node* n) { return left==n; }

	/** Funkcja budująca drzewo rekurencyjnie */
	void buildRec(int indexPos=0) {
        //log("  Build rec for node %d with len: %d",from, len);
        index=indexPos;
        assert(len>0);
        assert(from>=0 && from<m);
        if(isLeaf()) {    // liść
            ch=(queue[from]=='W')?1:-1;
            if(ch<0) min=1;   // gdy ujemny, to wymagany jest start z nie mniej niż 1 żetonem (<=1 = przegrana)
            assert(node[from]==NULL);
            node[from]=this;    // rejestrujemy się w mapie liści
        } else {    // nie liść - ma przynamnije 2 dziec
            int sp=(len+1)/2;
            left=new Node(this,from,sp);
            left->buildRec(indexPos);
            right=new Node(this,calcStep(from, sp), len-sp);
            right->buildRec(indexPos+sp);
            // po zbudowaniu dzięci oblcizamy wartości dla węzła
            // aby przejść cały fragment, najpierw należy przejść lewy, więc jego minumum musi być
            // następnie, aby przejść prawy nalezy uwzględnić wynik z lewego i skorygować o tyle minimum prawego, z tym że nie moze być mniej niż 0
            min=maxVal(left->min, maxVal( right->min-left->ch, 0) );
            ch=left->ch+right->ch;  // zmiana będzie taka jaka suma zmian
        }
#ifdef DEBUG
        {
            //log("  Checking node %d with len: %d; Change=%d, Min=%d",from,len, ch, min);
            int p=from;
            int sum=0;
            int mi=0;
            for(int i=0;i<len;++i) {
                assert(p>=0 && p<m);
                sum+=(queue[p]=='W'?1:-1);
                if(sum<mi) mi=sum;
                p=(p+n)%m;
            }
            //log("  Expecting Ch=%d, Min=%d",sum, -mi);
            assert(ch==sum);
            assert(min==-mi);
        }
#endif
	}
};


/**
 * Metoda wyliczajaca dane pomocnicze dla jednej kolejki:
 * - oblicza jaka bedzie zmiana salda po przejsciu calego cyklu
 * - buduje drzewo z podziałami
 */
void initQueue(int l) {
	int sum=0;
	int start=l;
	int len=0;      // TODO: Największy wspólny dzielnik o ile się nie mylę
	// etap 1 - przejście po całości - wyliczenie długości oraz sumy całości
	for(;;) {
		//sum+=leaf[l].change();
		l=(l+n)%m;	// następny krok
		++len;
		if(l==start) break;	// przetworzono cały ciąg
	}
    log("Building tree for node %d with len=%d ",l, len);
	// mamy sumę oraz długość
	// budujemy drzewo dla tej kolejki od korzenia
	Node* root=new Node(NULL, start, len);
	root->buildRec();

#ifdef DEBUG
#endif
}

/**
 * Funkcja zwracają krok, w którym zabraknie pieniędzy licząc od wierzchołka n
 */
int findEnd(int cash, Node* t) {
    int res=0;
    for(;;) {
        assert(cash <= t->min); // nie powinno być pieniędzy na przejście danego fragmentu
        if(!t->isLeaf()) {
            if(cash > t->left->min) {   // to znaczy, że lewą stroną przejdziemy, czyli upadek jest w prawej
                cash+=t->left->ch;  // aktualizujemy stan pieniędzy o to co byśmy mieli po przejściu lewej
                res+=t->left->len;  // aktualizujemy licznik kroków, po przejściu lewego
                t=t->right;         // i idziemy do prawego
            } else {    // upadek jest w lewej
                t=t->left;  // idzemy do lewej, nie zmieniamy stanu
            }
        } else {    // jeżlie dośliśmy już na sam dół drzewa, czyli do konkretnego pola to znaczy że jest to koniec i tu przegramy
            assert(cash==1);    // ilość piniędzy w ostatnim kroku powinna być 1
            assert(t->ch==-1);  // ostatni krok powinien być na minus
            return res;
        }
    }
}

/**
 * Funkcja zwracająca liczbę kolejek, w których gracz z daną ilością pieniędzy je straci. Jeżeli gracz będzie wygrywał, to funkcja zwraca -1.
 * Argument do funkcji, to górna gałąż dla kolejki, w której jest dany gracz, a kwota jest wyliczona dla początku kolejki
 */
int64_t findLimit(int cash, Node* root) {
    assert(root!=NULL);
    assert(root->isRoot());
    assert(cash>0);

    if(cash>root->min && root->ch>=0) return -1;    // gracz ma wymaganą ilość pieniędzy, aby bezpiecznie przejść całą kolejkę oraz przejście całej kolejki nie zmniejsza stanu pieniędzy
    int64_t res=0;
    if(cash > root->min) {    // jeżeli mamy na przejście tej rundy, ale każde przejście pomniejsza ilość pieniędzy, to
		int cost=-root->ch;
        int x=(cash - root->min + cost-1)/cost;  // mamy pieniedzy na przejscie tyle kolejek
#ifdef DEBUG
		/*int tstx=1;
		while(cash-cost*tstx>root->min) ++tstx;
		assert(tstx==x);*/
#endif
		log("  Cash %d; QueueMin: %d, Queue Cost: %d. Processing %d rounds with result cash: %d",
			cash, root->min, root->ch, x, cash-x*cost);
        cash-=x*cost;  // tyle będzie po przejściu x kolejek
        assert(cash<=root->min);
		assert(cash+cost>root->min);
        res+=((int64_t)root->len)*x;    // tyle razy grac będzie musiał zagrać, aby dość do ostatniej rundy
        log("    Cash for %d rounds. New cash: %d",x, cash);
    }
    // liczymy miejsce, w którym zakończy się ostatnia runda
    assert(cash <= root->min);
    return res+findEnd(cash, root);
}

/**
 * Funkcja obliczająca, czy dany gracz przejdzie pierwszą rudę do końca.
 * Zwracana jest -1, gdy gracz jest w stanie dość do konca rundy lub nr oznaczają
 */
int checkFirst(Node* s, int& cash, int& steps) {
    // najpierw idziemy do góry, do pierwszego miejsca w którym zabraknie piniędzy
    steps=0;
    int startPos=s->index;  // pozycja startowa
    int pos=startPos;   // aktualna (na potrzeby chodzenia)
    Node* last=NULL;
    for(;;) {
        log("  Checking node %d with len=%d, min=%d, ch=%d, pos=%d. Curretly at pos=%d, cash=%d, steps=%d",s->from,s->len,s->min,s->ch, s->index, pos, cash,steps);
        assert(s!=NULL);
        assert(pos >= s->index && pos <= (s->index + s->len));
        if(pos==s->index) { // to pokrywa się z aktualnie odwiedzanym fragmentem i można go w całości sprawdzić
            log("  At index start");
            if(cash > s->min) { // to fragment można przejść
                steps+=s->len;
				pos+=s->len;
                cash+=s->ch;
                if(s->isRoot()) {
                    log("  Gone to root - done");
                    return -1;  // udało się dość do końca
                }
                s=s->parent;
            } else {    // jeżeli nie można przejść, to zwykłe szukanie zwróci wynik, bo jesteśmy na początku fragmentu
                log("  Cannot pass");
                steps+=findEnd(cash, s)+1;
                return steps;   // po tylu krokach będzie koniec
            }
        } else if(pos==s->index+s->len) {    // na końcu, to nie ma nic do roboty tylko można pójść do góry
            log("  Right way up");
            if(s->isRoot()) {
                return -1;
            }
            s=s->parent;
        } else {    // jesteśmy w środku, to znaczy, że nalezy uwzględnić prawą gałąż
            log("  Middle check");
            assert(s->right!=NULL);
            assert(s->right->index==pos);
            if(cash > s->right->min) {  // jest kasa na przejście prawą stroną, więc nalezy to uwzględnić
                cash+=s->right->ch;
                steps+=s->right->len;
                pos+=s->right->len;
            } else {
				log("  Middle check no cash");
                return findEnd(cash, s->right)+steps+1; // po tylu krokach będzie koniec
            }
            if(s->isRoot()) return -1;
            s=s->parent;
        }
    }
}


#ifdef DEBUG
/**
 * Funkcja testowa, która sprawdza ile gracz przejdzie (ile razy zagra) majać zadaną ilość pieniędzy
 * oraz zaczynając w danym miejscu kolejki.
 */
int testWalk(int cash, int from) {
	int startCash=cash;
	int step=0;
	int i=from;
	for(;;) {
		++step;

		if(queue[i]=='W') ++cash;
		else if(--cash==0) return step;	// gdy pieniądze się kończą to wychodzimy z pętli
		i=(i+n)%m;
		if(i==from && cash>=startCash) return -1;	// gdy zrobimy pętlę i mamy więcej lub tyle samo pieniędzy, to wiadomo że można grać w nieskończoność
	}
}

/**
 * Funkcja testowa, która sprawdza ile gracz przejdzie (ile razy zagra) majać zadaną ilość pieniędzy
 * oraz zaczynając w danym miejscu kolejki.
 */
int testFirstWalk(int& cash, int from, int limit) {
	int startCash=cash;
	int step=0;
	int i=from;
	for(;;) {
		++step;

		if(queue[i]=='W') ++cash;
		else if(--cash==0) return step;	// gdy pieniądze się kończą to wychodzimy z pętli
		i=(i+n)%m;
		if(i==limit) return -1;	// gdy zrobimy pętlę i mamy więcej lub tyle samo pieniędzy, to wiadomo że można grać w nieskończoność
	}
}



#endif


int main(int argc, char** argv) {

	// etap 0 - odczyt danych
	scanf("%d",&n);
	cash=(int*)malloc(sizeof(int)*n);
	for(int i=0;i<n;++i) scanf("%d",&cash[i]);
	log("Loaded cash info for %d players",n);

	scanf("%d",&m);
	queue=(char*)malloc(sizeof(char)*(m+2));
	scanf("%s",queue);
	log("Loaded queue with %d commands",m);

	// etap 1 - budowa drzewa grupujacego
	node=(Node**)malloc(sizeof(Node*)*m);   // dla każdego elementu będzie liść

	for(int i=0;i<m;++i) node[i]=NULL;  // oznaczamy, że jeszcze nie ma podpiętego liścia do tego elementu opisu kolejki

    log("Initializing tree");
	for(int i=0;i<m;++i) if(node[i]==NULL) initQueue(i);
	log("All queues trees initialized");
#ifdef DEBUG
    for(int i=0;i<m;++i) {
        assert(node[i]!=NULL);
        assert(node[i]->ch==1 || node[i]->ch==-1);
        assert(node[i]->len==1);
        assert(node[i]->from==i);
    }
#endif

	// etap 2 - sprawdzenie kiedy dany gracz się wyzeruje w celu odnalezienia miniumum
	int64_t min=-1;
	for(int i=0;i<n;++i) {
        Node* s=node[i%m];    // weżeł startowy
        int c=cash[i];      // początkowa ilość pieniędzy
        int steps=0;
        int64_t pos=i+1;	// nr gracza w kolejce - jest początek rundy dla tego gracza
        log("Processing player %d with cash: %d",(i+1), c);
        assert(s!=NULL);
        assert(c>=1 && c<=1000000);
#ifdef DEBUG
		bool check=false;
		int64_t testRes;
		int testRun;
		if(i==2016-1) {
			check=true;
			testRun=testWalk(c,i%m);
			testRes=(testRun==-1)?-1:(((int64_t)testRun-1)*(int64_t)n+i+1);
			log("  Test walk: %d = round %lld",testRun, testRes);	// kolejka = (ilosc kroków -1 ) * ilość graczy + numer startu (i+1)
		}
#endif
        if(s->index!=0) {   // gracz jest nie jest na początku kolejki
            log("  Not at queue start - firstCheck");
            int res=checkFirst(s,c,steps);
			if(res==-1) {
	            pos+=((int64_t)steps)*n;   // tyle kroków wykonano, aby wykonać pierwsze przejście
			} else {
	            pos+=((int64_t)(res-1))*n;   // tyle kroków wykonano, aby wykonać pierwsze przejście
			}
            log("  Check first result: %d in steps: %d and cash: %d, pos=%lld", res, steps, c, pos);
#ifdef DEBUG
			{
				Node *r=s;
				int tstCash=cash[i];
				while(!r->isRoot()) r=r->parent;	// do root-a
				int testFirst=testFirstWalk(tstCash,i%m,r->from);	// limitem jest poczek kolejki, który zapisany jest w korzeniu
				log("  Test check first result: %d, testCash=%d; QueueLen=%d; StartIndex=%d",testFirst, tstCash, r->len, s->index);
				assert(res==testFirst);
				if(res==-1) assert(c==tstCash);
			}
#endif
            if(res>=0) {    // jeżeli skończyła się kasa, to pos to miejsce przegania
#ifdef DEBUG
				if(check) {
					assert(testRun==res);	// sprawdzamy tylko w przypadku końca, bo pierwsze przejście to tylko do końca pętli
					assert(testRes==pos);
				}
#endif
                if(min==-1 || min>pos) {
					min=pos;      // miejsce przegrania
					//if(min==172250004LLU) return -1;
				}
                continue;   // gracz przerobiony
            }
            // gracz przechodzi pierwszą rundę i jest na początku kolejnej kolejki
        }
        while(!s->isRoot()) s=s->parent;
        assert(s->isRoot());

        int64_t res2=findLimit(c,s);
        log("  Find limit result: %lld",res2);
        if(res2==-1) {
#ifdef DEBUG
			if(check) assert(testRes==-1);
#endif
			continue;      // to gracz nigdy nie przegrywa
		}
        pos+=(res2*n);
        log("  Loose round: %lld",pos);
#ifdef DEBUG
		if(check) assert(testRes==pos);
#endif
        // TODO: Testy
        if(min==-1 || min>pos) {
			min=pos;
			//if(min==172250004LLU) return -1;
		}
	}
	printf("%lld\n",min);

	return 0;
}