/**
* January 2013 Long Challenge at Codechef
*
* Problem: HOB - Hotel Balifornia
* Author: Anton Lunyov (Tester and Editorialist)
* Complexity: O(N * R) per test + O(Per(R)) for each R in the file,
* where Per(R) is the Pisano period of sequence
* of prefix sums of Tribonacci sequence modulo R
* Timing: 0.70 out of 1.50
*
* Description:
* For the current R we left only first occurrence of each room in the lift boy's scheme
* and then use this in order to process the guest in O(R) time
* The lift boy's scheme is stopped when we meet some repetitions which lead to periodicity.
*/
#include
#include
using namespace std;
typedef vector > VPII;
const int maxR = 500;
// returns the polynomial hash of S with base 33 modulo R
int hash(char *S, int R) {
int hash = 0;
for (int i = 0; S[i]; ++i) {
// rectify uppercase letter
char c = S[i];
if ('A' <= c && c <= 'Z') {
c = (c - 'A') + 'a';
}
// get integer value of lowercase letter
int d = c - 'a' + 1;
// update the hash by Horner scheme
hash = (33 * hash + d) % R;
}
return hash;
}
// ROOMS[R] will contain the sorted by k list of pairs (k, r),
// with meaning that room r is visited at k-th iteration first
// when lift boy's scheme applied to the room 0 (the hotel has R rooms)
VPII ROOMS[maxR + 1];
// whether we calculate ROOMS[R] before or not
int calculated[maxR + 1]; // initially contains all zeros
// the maximum period of sumA[]
// the actual maximum is 345072 and attains on R=483
const int maxP = 350000;
int A[maxP]; // lift boy's sequence
int sumA[maxP]; // prefix sums of A[]
// returns ROOMS[R] calculating it if necessary
VPII rooms_calc(int R) {
// if we calculate rooms list for R before,
// we simply return previously calculated result
if (calculated[R]) {
return ROOMS[R];
}
// otherwise we do calculation
// this array will contain moment of first visit for each room
// -1 means that room was never visited
vector firstVisit(R, -1);
// and this is the desirable sorted list of pairs
VPII rooms;
// loop over lift boy's scheme
for (int k = 0; ; ++k) {
// A[k] is the k-th element of the lift boy's sequence
// by setting A[0]=0 we get A[3]=3=2+1+0=A[2]+A[1]+A[0] which conforms the pattern
// we need it only modulo R, of course
A[k] = (k < 3 ? k : A[k - 1] + A[k - 2] + A[k - 3]) % R;
// sumA[k] is the actual room that will be checked, assuming that r0 = 0
// Actually rk = (r0 + sumA[k]) % R
sumA[k] = A[k];
if (k > 0) {
sumA[k] = (sumA[k] + sumA[k - 1]) % R;
}
// we noted the first visit for room sumA[k] if it was not visited before
int r = sumA[k];
if(firstVisit[r] < 0) {
firstVisit[r] = k;
// and add the pair (k, r) to the list
// since we iterate over k in increasing order
// the list automatically will be sorted
rooms.push_back(make_pair(k, r));
}
// the condition of periodicity of the sequence sumA[].
// when the quadruple (sumA[n],A[n+1],A[n+2],A[n+3]) coincides with (sumA[0],A[1],A[2],A[3])
// for some n then it is clear from recurrent formulas for A[k] and sumA[k] that
// sumA[n+k] = sumA[k] for all k hence we will not meet any new room after that
// it can be proved that for any R such n exists
if (k >= 3 && sumA[k - 3] == 0 && A[k - 2] == 0 && A[k - 1] == 1 % R && A[k] == 2 % R) {
break;
}
}
// we mark that we have already calculate the sorted list of pairs for this R
calculated[R] = 1;
// and return this list simultaneously saving it at ROOMS[R]
return ROOMS[R] = rooms;
}
int main() {
// input number of tests
int T;
scanf("%d", &T); // we use scanf for faster input
// loop over tests
for (int t = 0; t < T; ++t) {
// input N and R
int N, R;
scanf("%d%d", &N, &R);
// calculate order of rooms visited in lift boy's scheme
// note that we do this in lazy fashion
// by saving previously calculated results
VPII rooms = rooms_calc(R);
// time[r] is the time when the room becomes free
vector time(R, 0);
int day = 0; // day of the current visit
int prev = 0; // minute of the day of the previous visit
int inconv = 0; // inconvenience caused to all previous guests (modulo R)
// loop over visits
for (int n = 0; n < N; ++n) {
// input visit data
int H, M, G;
char S[11];
scanf("%d%d%d%s", &H, &M, &G, S);
// calculating time stamp with help of variables day and prev
int cur = 60 * H + M;
if (prev > cur) {
++day;
}
prev = cur;
cur += 24 * 60 * day;
// the initial room assigned by RNG
int r0 = (hash(S, R) + inconv) % R;
// the upper bound for the time that guest could wait
// dictated by the upper bound on G
// factor 60 since G is in hours and we seek for minutes
int wait_time = 60 * 10000000;
// indicates whether we find the room or not
bool found = false;
// iterate over the list of pairs that contains all rooms
// found during lift boy's scheme but without repetition
for (int i = 0; i < rooms.size() && !found; ++i) {
// the current room to check
// rooms[i].second is sumA[k] from the rooms_calc
int r = (r0 + rooms[i].second) % R;
if (time[r] <= cur) {
// in this case we can settle the guest
// so we update the time[r]
time[r] = cur + 60 * G;
// change total inconvenience by rooms[i].first which is k
// in the lift boy's scheme
inconv = (inconv + rooms[i].first) % R;
// print the inconvenience for the current guest
printf("%d\n", rooms[i].first);
// and indicate that we found the room for the guest
found = true;
}
// the wait_time should be the minimum of waiting times over all visited rooms
// time[r] - cur is the time we should wait from now before the room r will be free
wait_time = min(wait_time, time[r] - cur);
}
if (!found) {
// in this case the guest could not be settled
// and we print the waiting time
printf("-%d\n", wait_time);
// and update the total inconvenience accordingly
inconv = (inconv + wait_time) % R;
}
}
}
return 0;
}