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
#include <iostream>
#include <climits>

#define EACH_PLAYER(iter) (iter = 1; iter <= n; iter++)

using namespace std;

typedef signed long INT;

const INT MAX = 10e6 + 1;

struct player
{
	INT id;
	INT cash;
};

struct variant
{
	INT balance;
	INT max_lose;
};

struct slot_machine
{
	bool program[MAX * 2];
	INT len;
	INT games_to_lcm;
	INT program_step;
	INT variants_count;
	variant variants[MAX];

	void load_program(INT len, const char* program_str);
	void analyze(INT players_count);
	void analyze_variant(INT variant_id);
	INT games_before_defeat(player p, INT variant_id);
	INT solve(player players[]);
};

INT n, m;
player players[MAX];
slot_machine slots;
char program_buf[MAX];

long long gcd(int a, int b)
{
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
}

long long lcm(int a, int b)
{
    int temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
}

void input()
{
	INT i;

	cin >> n;

	for EACH_PLAYER(i)
	{
		players[i].id = i;
		cin >> players[i].cash;
	}

	cin >> m >> program_buf;
	slots.load_program(m, program_buf);
	slots.analyze(n);
}

void slot_machine::load_program(INT len, const char* program_str)
{
	INT i;
	this->len = len;

	for (i = 0; i < len; i++)
	{
		program[i] = program[i + m] = (program_str[i] == 'W');
	}
}

void slot_machine::analyze(INT players_count)
{
	INT i;

	variants_count = min(players_count, len);
	// long long lcm = players_count * variants_count; // TODO true LCM, prevent int overflow
	games_to_lcm = lcm(variants_count, players_count) / players_count;
	// long long lcm = players_count * variants_count; // TODO true LCM, prevent int overflow
	// games_to_lcm = variants_count;
	program_step = players_count;

	for (i = 0; i < variants_count; i++)
	{
		analyze_variant(i); // TODO possibly early exit if everyone wins
	}
}

void slot_machine::analyze_variant(INT variant_id)
{
	INT idx = variant_id;
	variant *v = &variants[variant_id];

	v->balance = v->max_lose = 0;

	do {
		v->balance += program[idx] ? 1 : -1;
		if (v->balance < v->max_lose) { v->max_lose = v->balance; }
		idx = (idx + program_step) % len;
		// TODO program can be reordered before analysys
	} while (idx != variant_id);
	v->max_lose *= -1;
}

INT slot_machine::solve(player players[])
{
	INT i, gtd, before_defeat;
	INT games = INT_MAX;

	for EACH_PLAYER(i)
	{
		before_defeat = games_before_defeat(players[i], (i - 1) % variants_count);
		gtd = before_defeat * program_step + players[i].id;
		if (before_defeat >= 0 && gtd < games) { games = gtd; }
	}

	return games < INT_MAX ? games : -1;
}

INT slot_machine::games_before_defeat(player p, INT variant_id)
{
	INT idx, counter, cash, cycles;
	variant *v = &variants[variant_id];

	if (p.cash <= v->max_lose)
	{
		// Lose at this cycle
		idx = variant_id;
		cash = p.cash;
		for (counter = 0;; counter++)
		{
			cash += program[idx] ? 1 : -1;
			if (cash <= 0){ return counter; }
			idx = (idx + program_step) % len;
		}
	}
	else if (v->balance < 0)
	{
		// Lose after some cycles
		// TODO divmod at once: http://linux.die.net/man/3/div
		cycles = (p.cash - v->max_lose) / (-1 * v->balance);
		p.cash += cycles * v->balance;
		return cycles * games_to_lcm + games_before_defeat(p, variant_id);
	}
	else
	{
		// Never ever lose
		return -1;
	}
}

int main(int argc, char **argv)
{
	input();
	cout << slots.solve(players);
	return 0;
}