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

using namespace std;
typedef long long int LL;

LL NWD(LL a, LL b)
{
   while(a!=b)
        if(a>b)
            a-=b;
        else
            b-=a;
    return a;
}

main()
{
    LL n,m, nwd, len, el;

    cin >> n;
    vector<LL> money(n);
    for (LL i=0; i<n; i++)
        cin >> money[i];
    
    cin >> m;
    nwd = NWD(n,m);     // ilosc cykli
    len = m/nwd;        // dlugosc cyklu
    el = n/nwd;		// elementow w grupie;	

   
    vector< vector <LL> > cyclek;
    vector< vector <LL> > cycle;
    vector< vector <LL> > cycleMin;
    for (LL i=0; i<nwd; i++)
    {
	cycle.push_back( vector<LL>(len,0) ); 
	cyclek.push_back( vector<LL>(len,0) ); 
	cycleMin.push_back( vector<LL>(len,0) ); 
    }
    
    vector<LL> inCycle(n,0);
    vector<LL> startPos(n,0);
    char v;
    for (LL i=0, j; i<len; i++)
    {
        for (j=0; j<nwd; j++)
        {
            cin >> v;
	    if (v=='P') cyclek[j][i]=-1;
            else cyclek[j][i]=1;
	}
    }
	
    for (LL i=0, j, ind=0; i<len; ind=(ind + n)%len, i++)
        for (j=0; j<nwd; j++)
            cycle[j][i]=cyclek[j][ind];

	
    for (LL i=0; i<n; i++)
    {
	    inCycle[i]=i%nwd;
	    startPos[i]=i%len;
    }
   
    vector<LL> cyclesum(nwd,0);
    for (LL j=0, i; j<nwd; j++)
    {
	cyclesum[j]=0;
	cycleMin[j][0]=0;
	for (i=0; i<len; i++)
	{
	    cyclesum[j]+=cycle[j][i];
	    if (cycleMin[j][0] > cyclesum[j])
		cycleMin[j][0] = cyclesum[j];
	}    
    }
	  
    for (LL j=0, i; j<nwd; j++)
	for (i=1; i<len; i++)
	    cycleMin[j][i]=cycleMin[j][i-1]-cycle[j][i-1];

    vector<LL> l(n,LLONG_MAX);
    
    for (LL i=0; i<n; i++)
    {
      if ((cyclesum[inCycle[i]] >= 0) && (-cycleMin[inCycle[i]][startPos[i]] < money[i])) continue;
      if ((cyclesum[inCycle[i]] < 0) && (-cycleMin[inCycle[i]][startPos[i]] < money[i]))
      {
	 l[i]  = (money[i]+cycleMin[inCycle[i]][startPos[i]])/(-cyclesum[inCycle[i]]);
      }
      else 
	 l[i] = 0;
    }
	
    LL minc=LLONG_MAX, minpos=LLONG_MAX;
    
    for (LL i=0; i<n; i++)	
	 if (l[i]<minc) minc=l[i];

    if (minc==LLONG_MAX) 
    {
	cout << "-1" << endl;
	return 0;
    }
	 
    LL result=minc*len;
    for (LL i=0; i<n; i++)
	 money[i]+=minc*cyclesum[inCycle[i]];

    LL i=0;
    do
    {
	money[i%n]+=cyclek[inCycle[i%n]][i%len];
	result++;
	if (!money[i%n])
	{
	    cout << result << endl;
	    return 0;
	}
	i=(i+1)%(n*m);
    }
    while (true);
	
}