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
/*
Tomasz Stepanko
PA2015 Runda3 
Zadanie B - Hazard
*/
#include<stdio.h>

#ifdef _WIN32 
typedef __int64 bigInt; 
#define bigIntFormat "%I64d" 
#else 
typedef long long int bigInt; 
#define bigIntFormat "%lld" 
#endif 

bigInt gcd(bigInt x, bigInt y)
{
	if(x < y)
	{
		int tmp = y;
		y = x;
		x = tmp;
	}
	while(y != 0)
	{
		int tmp = y;
		y = x % y;
		x = tmp;
	}
	//printf("gcd = %d\n", x);
	return x;
}

bigInt lcm(bigInt x, bigInt y)
{
	//printf("%u = %u * %u / %u\n", result, x, y, gcd(x,y));
	return x*y/gcd(x,y);
}

int main()
{
	bigInt n, m;
	scanf(bigIntFormat, &n);
	bigInt* savings = new bigInt[n];
	for(bigInt i = 0; i < n; i++)
	{
		scanf(bigIntFormat, &savings[i]);
	}
	scanf(bigIntFormat, &m);
	char* results = new char[m];
	for(bigInt i = 0; i < m; i++)
	{
		char r;
		scanf("\n%c", &r);
		//printf("\nreded %c\n", r);
		results[i] = r == 'P' ? -1 : 1;
	}
	//printf("Data read\n");
	
	// calculate results after play one full cycle
	bigInt* resultsAfterCycle = new bigInt[n];
	for(bigInt i = 0; i < n; i++)
	{
		resultsAfterCycle[i] = 0;
	}
	//printf("Calculating lcm\n");
	bigInt cycle = lcm(n, m);
	//printf("Cycle is %I64d elements long\n", cycle);
	for(bigInt i = 0; i < cycle; i++)
	{
		//printf("end cycle %I64d\n");
		resultsAfterCycle[i%n] += results[i%m];
		//printf("For %d boy adding result %d(%d), now sum of the games is %d\n", i%n, results[i%m], i%m, resultsAfterCycle[i%n]);
		if(resultsAfterCycle[i%n] + savings[i%n] <= 0)
		{
			printf(bigIntFormat, i+1);
			printf("\n");
			return 0;
		}
	}
	
	/*for(int i = 0; i < n; i++)
	{
		printf("%d ", resultsAfterCycle[i]);
	}
	printf("\n");*/
	
	// find the boy who loos his money first
	bigInt minFullCyclesCount = 1000000000000;
	bool found = false;
	for(bigInt i = 0; i < n; i++)
	{
		if(resultsAfterCycle[i] < 0)
		{
			bigInt tmpFullCyclesCount = -1*savings[i]/resultsAfterCycle[i] - 1;
			//printf("for %d -1 * %d / %d = %d\n", i, savings[i], resultsAfterCycle[i], tmpFullCyclesCount);
			if(tmpFullCyclesCount < minFullCyclesCount)
			{
				minFullCyclesCount = tmpFullCyclesCount;
				found = true;
			}

		}
	}
	//printf("min cycles needed %d\n", minFullCyclesCount);
	if(!found)
	{
		printf("-1");
	}
	else
	{
		for(bigInt i = 0; i < n; i++)
		{
			savings[i] += minFullCyclesCount*resultsAfterCycle[i];
		}
		for(bigInt i = 0; i < cycle; i++)
		{
			//printf("end cycle %I64d\n");
			savings[i%n] += results[i%m];
			if(savings[i%n] <= 0)
			{
				printf(bigIntFormat, minFullCyclesCount*cycle + i + 1);
				printf("\n");
				break;
			}
		}
	}
	return 0;
}