Let's designate characters on the first letter of the name. The queue looks like: SH-L-P-R-G, through 5 cans: SH-SH-L-L-P-P-R-R-G-G, through 10 cans: SH-SH-SH-SH-L-L-L-L-P-P-P-P-R-R-R-R-G-G-G-G.

The regularity is clear, and the solution is very simple: we will be iterated on p - we will find such minimum p that 5· 2^p > n (thus if this number is less or equally we will subtract it from n) then we know that at first 2^p Sheldon's stand, then 2^p Leonard's and so on. And now we can easily answer who took a can number n (namely there was a person with number n / 2^p in sequence SH-L-P-R-G (in 0-indexation).

For the solution the following important fact is required to us: we will admit elements v and u are in one set then in any of n· (n - 1) / 2 of sequences from the input data where meets v  u necessarily meets. And also if v and u are in different sets there is such sequence in which is v, but isn't present u. Then it is possible to enter the equivalence relation for all elements of all sets - two elements are equivalent, if there is no sequence where one element meets, and another isn't present. Classes of equivalence also are required sets.

It was possible to consider the answer as following algorithm: we will write out for each number the list of numbers of sequences where there is this number, and will unite two numbers if these lists are equal. This algorithm can be realized for O(n² * log(n)) however the solution for O(n³) passes all tests with time large supply too.

The special case is a test with n = 2. This test was used for a considerable quantity of hacks.

At first we will estimate from above the maximum time to which all divisions will reach capital - obviously it is required no more n days for this purpose. Therefore restrictions quite allowed model movements of divisions. The key moment of the solution - we will always consider divisions in priority order. Then in every day we will consider the list of those divisions who hasn't reached yet capital, and we will put in priority order on the necessary train. If the train is already filled, the division remains in a current city, differently we will change its position, and in day when the division will reach capital we will write down the answer. Total: in total days which it is necessary model, no more n, and every day we move no more n divisions. So our solution has asymptotic form no more O(n²). 

The solutions using various structures of the data (sets, turns with priorities etc.) work for O(n²· log(n)) and it didn't always keep within in TL.