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
/*
 * main.c
 *
 *  Created on: 30 wrz 2015
 *      Author: slawek
 */

#include <stdio.h>

//#define DEBUG_1
//#define DEBUG_13
//#define DEBUG_11

#define MAXLICZKOL	1000000
#define MAXDLCPAU	1000000

long n, m;	//liczba kolegow, dlugosc cyklu pracy automatu

long koledzy[MAXLICZKOL];
short int automat[MAXDLCPAU];

//---- tabela losowan ---
//struct wyniki	{
//	long lok_nr_los;	//lokalny numer losowania
//	long rezultat; 	//rezultat osiagniety po lok_nr_los-tym losowaniu (tylko ujemne)
//}
long losowania[MAXDLCPAU];
long top_min;	//najwieksza strata osiagnieta w ciagu losowania
long rezultat;	//ostateczny rezultat po przejsicu calej kolejki losowan
long dl_tab_losowan;	//dlugosc tablicy losowan - ilosc ujemnych rezultatow w kolejce
//-------------


//zmienne potrzebne przy budowaniu kolejki losowan dla danego kolegi
long long nww;
long il_kolejki, il_losowan;

long long get_nww(long a, long b);
void buduj_tabele(long gracz);
long long daj_wynik(long gracz);
//......
int main()
{
	long i, in;
	char ina;
#ifdef DEBUG_11
	long j;
#endif
	long long wynik, wynik_tmp;

	scanf("%ld\n", &n);
	for(i=0; i<n; i++)
	{
		scanf("%ld",&in);
		koledzy[i] = in;
	}

	scanf("%ld\n", &m);
	for(i=0; i<m; i++)
	{
		scanf("%c",&ina);
		automat[i] = (ina=='W')? -1 : 1; //przegrana 1, wygrana -1
	}
#ifdef DEBUG_10
	for(i=0; i<n; i++)
	{
		printf("%ld: %ld\n",i, koledzy[i]);
	}
	for(i=0; i<m; i++)
	{
		printf("%ld: %d\n",i, automat[i]);
	}
#endif

	//zmienne potrzebne do zbudowania ciągów wyników
	nww = get_nww(n,m);
	il_kolejki = nww/n; //ilosc powtorzen kolejki graczy (dlugosc ciagu)
	il_losowan = nww/m;	//ilosc powtorzen kolejki losowan

#ifdef DEBUG_13
	printf("%lld, %ld, %ld\n", nww, il_kolejki, il_losowan);
#endif

	wynik = -1;
	for(i=0; i<n; i++)
	{
		//budowanie ciagu wynikow dla danego kolegi
		buduj_tabele(i);
#ifdef DEBUG_11
		printf("=====\n");
		printf("dl:%ld, res:%ld, top:%ld\n------\n",dl_tab_losowan, rezultat, top_min);

		for(j=0; j<dl_tab_losowan; j++)
		{
			printf("minimum (pomn. o 1) %ld osiagniete w kroku (pomn. o 1):%ld\n",j, losowania[j]);
		}
		continue;
#endif

		if( (wynik_tmp=daj_wynik(i)) > 0 )
		{
#ifdef DEBUG_12
			printf("wyn:%lld\n",wynik_tmp);
#endif
			if( (wynik_tmp < wynik) || (wynik==-1) )
			{
				wynik = wynik_tmp;
			}
		}
	}

	printf("%lld\n", wynik);


	return 0;
}

//***************************

long long daj_liczbe_losowan(long gracz, long obrotow, long reszta)
{
	long long wynik=0;

	wynik = gracz+1;
	if(obrotow)
	{
		wynik += obrotow * nww; //hmm
	}

	if(reszta)
	{
		wynik += (losowania[reszta-1])*n;//???
	}
	return wynik;
}
//....
long long daj_wynik(long gracz)
{
	long obrotow, reszta;

	if( (rezultat<=0) && koledzy[gracz] > top_min )	//ciag daje wynik dodatni a minimum ciagu jest mniejsze od zasobow gracza
		return -1;

	obrotow = (koledzy[gracz]-top_min)/rezultat;
	if((koledzy[gracz]-top_min)%rezultat)
		obrotow++;
	reszta = koledzy[gracz] - (obrotow * rezultat);
#ifdef DEBUG_12
printf("topmin: %ld rezultat:%ld kol{gracz]: %ld gracz:%ld obrotow:%ld reszta:%ld\n",top_min, rezultat, koledzy[gracz], gracz, obrotow,reszta);
#endif
	return daj_liczbe_losowan(gracz, obrotow, reszta);
}
//----------------------
void buduj_tabele(long gracz)
{
	long i;
	long long nr_losowania;
//	long curr_res;

	top_min = 0;	//najwieksza strata osiagnieta w ciagu losowania
	rezultat = 0;	//ostateczny rezultat po przejsicu calej kolejki losowan
	dl_tab_losowan = 0;

	for(i=0; i<il_kolejki; i++)
	{
		nr_losowania = (long long)i * n + gracz;
		rezultat += automat[nr_losowania%m];	//tu mamy ostateczny rezultat ciagu -dodatni/+ujemny
		if(rezultat > top_min) //nowe minimum wyniku
		{
//			losowania[dl_tab_losowan].rezultat = rezultat; //rezultat ujemny...
//			losowania[dl_tab_losowan++].lok_nr_los = i; //..osiagniety w kroku i
			losowania[dl_tab_losowan++] = i; //kolejne minimum (pomniejszone o 1) osiagniete w kroku i (liczone od 0)
			top_min = rezultat;	//tu mamy najgorszy wynik w ciagu
		}
	}
}
//--------------------
long long get_nww(long a, long b)
{
	long long ab;
	long t;

	ab = (long long)a * (long long)b;
	while(b)
	{
		t = b;
		b = a % b;
		a = t;
	}
	ab /= a;

	return ab;
}