All submissions for this problem are available.
Byteland has always been popular among tourists. Seeing a business opportunity, Chef has built a brand new Hotel Balifornia there. The hotel has R unique comfortable rooms for guests' purpose. The rooms are numbered by integers from 0 to R-1, inclusive. All rooms in the hotel are on the same floor and arranged in a circle. Namely,
- the room next to the room 0 is the room 1;
- the room next to the room 1 is the room 2;
- the room next to the room R-2 is the room R-1;
- finally, the room next to the room R-1 is the room 0.
When R = 1 we have only one room and it is next to itself.
Below, we will be needing the notion of k-th next room to the given room. It should be quite clear from the notation what does it mean but let's define it formally to avoid any ambiguities. The 1-st next room to the room r is simply the next room to the room r. Assume that the notion of (k-1)-th next room is already defined. Then the k-th next room to the room r is the room next to the (k-1)-th next room to the room r.
At the time of check-in, among other things, the guest is required to provide his first name and the number of hours he will be staying in the hotel. Chef has sent a special machine called "Room Number Generator" (RNG) for allocating the rooms to the guests. The RNG takes a string (the first name of the guest) as the input and returns the room id. This is how RNG does it:
- The string is composed of lowercase and uppercase letters of English alphabet.
- At first, uppercase letters (from 'A' to 'Z', inclusive) are replaced by the corresponding lowercase letters: 'A' by 'a', 'B' by 'b', ..., 'Z' by 'z'.
- Next, each letter is replaced by an integer value: 'a' by 1, 'b' by 2, ..., 'z' by 26.
- Then we consider thus obtained list of positive integers as a representation of some integer in base 33. Namely, if D1, D2, ..., DL is the list of integers obtained after encoding all the letters we will consider the following value: D1 * 33L-1 + D2 * 33L-2 + ... + DL-1 * 33 + DL.
- Finally, RNG takes the remainder of division of the number, obtained at the previous step, by the number of rooms in the hotel. So this will be (D1 * 33L-1 + D2 * 33L-2 + ... + DL-1 * 33 + DL) mod R. This value is the room id returned by RNG. Well, at least Chef deems that RNG returns this value...
Consider some examples:
- "Ab" will be at first replaced by "ab" and then will be represented as 1 * 33 + 2 = 35. If the number of rooms in the hotel is 40 then the room will be 35 mod 40 = 35.
- "Chef" will be at first replaced by "chef" and then will be represented as 3 * 333 + 8 * 332 + 5 * 33 + 6 = 116694. If the number of rooms in the hotel is 37 then the room will be 116694 mod 37 = 33.
Chef noted that for some unlucky values of R regardless of the name of the guest, RNG returns only rooms from some range that does not cover all rooms in the hotel. This, of course, would be disaster for Chef. For example, for R = 33 rooms 0, 27, 28, 29, 30, 31, 32 can not be the values returned by RNG. Chef is smart guy and quickly realizes that this happens if and only if R is divisible by 33. Hence he ensures that the number of rooms in the hotel is not divisible by 33.
The hotel manager was having fun time, 'RNGing' the names of his acquaintances, just when he discovered that his wife's RNG number came out the same as his friend's! Horrified he visited the VP and explained the problem that different guests may end up in the same room. The VP thought for a moment, and then suggested that the one who comes later be allotted a different room. How clever! But which room? The hotel management fought for several days over this. Ultimately the lift boy's scheme was taken up.
- The lift boy is fond of sequences and number theory. Hence he will use the following sequence in his scheme: 1, 2, 3, 6, 11, 20, 37, ... Here each term of the sequence, starting from the 4-th one, equals to the sum of three previous terms. We denote the n-th term of this sequence as An. So A1 = 1, A2 = 2, A3 = 3, A4 = 6, and so on.
- Assume that RNG number of the current guest is r0.
- At first we check the room r0 and if it is free we settle guest in this room.
- Otherwise, we check the room r1 which is A1-th next to the room r0. If it is free we settle guest in this room. Note that since A1 = 1 then, actually, r1 is simply the next room to r0.
- Otherwise, we check the room r2 which is A2-th next to the room r1. If it is free we settle guest in this room. Note that since A2 = 2 then, r2 is the room, next to the room that is next to the room r1 (ignore this, if it blows your mind).
- In general, at k-th step we have all rooms r0, r1, ..., rk-1 occupied and we check the room rk which is Ak-th next to the room rk-1. If it is free we settle guest in this room and finish the process. Otherwise we continue.
- If we can't find the free room in any finite number of steps, we inform the guest that we unable to settle him. In this case we provide him the minimal number of minutes after which he could come again so that we could find the free room for him by the above scheme, assuming that we start the process again from the room r0.
- Please, be sure that you are using exactly this definition to find the required number of minutes. According to some weird facts about 'RNG' below, the room 'RNGing' to the guest later could differ from r0, but we still use the old value to perform the lift boy's scheme.
- Actually, no guest will return back to the hotel if we ask him to come back later without settling him in some room. The reason is that only celebrities visit Chef's hotel (see the example ;)) and they take a huge offense to the Chef if they were not settled in any room. Hence they will never return to the hotel again in this case. So actually we inform them the minimal number of minutes just out of courtesy :)
Chef hears this and is a bit worried about guests' response, so he requests you to analyze the inconvenience that will be caused to the guests. If the guest was settled in some room, the inconvenience equals to the least integer k for which the room rk is free, so, actually, it is the number of rooms that was found occupied while processing this guest. Otherwise it is equal to the number of minutes he should wait to come again if no free room was found for him by lift boy's scheme.
After invention of the lift boy's scheme Chef also realizes that his old fears about unlucky values of R is useless but still he believes that values of R divisible by 33 could lead to larger average guests' inconvenience than other values of R. So, just in case, he still ensures that R is not divisible by 33.
What Chef and hotel management does not realize is that RNG has a mind of its own. Don't get scared! It just remembers the inconvenience caused to each guest and it uses this information to adjust the returned value. Namely, RNG add to the initial RNG value described above the sum of inconveniences caused to all previous guests. Then this number is taken modulo R to get the correct room number and RNG returns it. See example for clarity.
You will be given the list of all visits to the Hotel Balifornia in increasing order of time and should output the inconvenience caused to each guest. To make the output more readable print the dash before the inconvenience of each guest that was not settled in any room.
Also note that Chef's hotel is very popular, so the time interval between two consecutive visits is strictly less than 24 hours. Hence we will be providing only hour and minute of the day for each visit.
We could have several visits at the same moment of time. In this case we process guests in order they appear in the input.
If we have a visiting guest and some other guest leaving the hotel at the same moment, then the room which will be vacated by the leaving guest will be considered as free when applying the lift boy's scheme to the visiting guest. The same is true when deciding the waiting minutes for not settled guests.
We assume that all guests are different. But they could have equal first names. Indeed, Daniel Craig and Daniel Radcliffe are different persons having equal first names :)
The first line of the input contains an integer T, denoting the number of test cases. The description of T test cases follows. The first line of each test case contains two space-separated integers N and R, denoting the number of visits to the hotel and the number of rooms in the hotel respectively. The description of N visits follows. Namely, each of the following N lines contains 3 space separated integers H, M, G followed by a space and the string S. Here H and M is the hour and the minute of the day at which guest comes. Recall that visits are given in increasing order of time but the time interval between two consecutive visits is strictly less than 24 hours. G is the number of hours for which the guest will stay and S is his/her first name.
For each visit of each test, output a single line containing the inconvenience caused to the guest who made this visit. Don't forget to output '-' (dash) before result for each guest that should wait (see above). Please do not consider this dash as minus sign and do not assume that inconvenience is negative in this case. This dash is used only to make output more readable and have no effect on the actual inconvenience value.
- 1 ≤ T ≤ 1000
- 1 ≤ N ≤ 200000 (2 * 105)
- 1 ≤ R ≤ 500 (R is not divisible by 33)
- 0 ≤ H ≤ 23
- 0 ≤ M ≤ 59
- 0 ≤ G ≤ 9999999 (107 − 1)
- The total number of visits over the input does not exceed 200000 (2 * 105)
- The name of each guest contains only uppercase and lowercase letters of English alphabet and has length from 1 to 10, inclusive
Input: 1 8 4 0 10 15 Brad 0 12 6 Kanye 1 10 24 Angelina 5 38 48 John 12 55 56 Bill 12 56 6 Tom 20 1 2 Nicole 3 0 24 Daniel Output: 0 0 0 2 2 -134 1 1
|Guest's name||Cur Time||Prev. inconv.||RNG output||Room||Status||Order of rooms||Output|
|Brad||00:10||0||91513 + 0||1||
|Kanye||00:12||0||13097144 + 0||0||
|Angelina||01:10||0||60979313407 + 0||3||
|John||05:38||0||375983 + 0||3||
||3 → 0 → 2||2|
|Bill||12:55||2||82083 + 2||1||
||1 → 2 → 0||2|
|Tom||12:56||4||22288 + 4||0||
||0 → 1 → 3 → 2||-134|
|Nicole||20:01||138||558693338 + 138||0||
||0 → 1||1|
|Daniel||03:00||139||158240589 + 139||0||
||0 → 1||1|
- The Prev. inconv. column contains the total inconvenience caused to all previous guests.
- By RNG output here we mean the value before taking it modulo R.
- The Room column contains the room that was initially assigned to the guest and it is the actual value returned by RNG. It is equal to the value in the previous column take modulo R = 4.
- The Status column contains the current status of each room: '-' indicates a free room, while uppercase letter indicates that the room is occupied by the person whose first name starts at this letter.
- The Order of rooms column contains the sequence of rooms produced by the lift boy's scheme for the current guest.
- Note on the Tom's visit. After 4 steps of the lift boy's scheme we found out that all rooms in the hotel are occupied. Hence we can't settle Tom in any room. The room that will become free next is the room 1 occupied currently by Brad. This will happen at 15:10 which is 134 minutes after the 12:56 (the time of Tom's visit).
- Note on the Daniel's visit. We see that his visit time is less than for the previous visit. So it seems to violate the following constraint: times of visits are given in increasing order. In fact, this only means that Daniel came next day! (Again recall that the time interval between two consecutive visits is strictly less than 24 hours.)
|Tags||jan13, medium, pigeonhole, vinayak garg|
|Time Limit:||1.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.