Connection Status:
Competition Arena > TurntableService

TurntableService

SRM 219 · 2004-11-20 · by lbackstrom

SRM 219 · 2004-11-20 · by lbackstrom · Search, Simulation, Sorting
Class Name: TurntableService
Return Type: int
Method Name: calculateTime
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are out for Chinese food with a bunch of friends. You are all sitting at a round table, and in the center of the table is a turntable onto which all of the entrees are placed. There is one entree immediately in front of each of you.

Each of you likes certain items, given as a String[] favorites, each element of which is a space delimited list of integers. Each integer corresponds to an entree, where 0 is the entree initially in front of person 0, etc. Element i of favorites contains the indexes of all the entrees that person i likes.

The turntable rotates in either direction. When someone is serving himself, he can only take from the entree that is directly in front of him. However, he is not required to take the entree presented to him, even if it is one of his favorites.

It takes 2 seconds to rotate the turntable by one position. But, to rotate it by two positions takes 3 seconds, and in general it takes n+1 seconds to rotate the turntable by n positions. It takes 15 seconds for a person to serve himself the entree in front of him. If multiple people have favorite entrees in front of them, they can serve themselves simultaneously. The turntable cannot be rotated while anyone is serving himself.

You are to return an int indicating the minimum number of seconds it takes for each person to have served himself one entree.

Notes

  • You may assume that each of the entrees on the turntable is unique.

Constraints

  • favorites will contain between 1 and 15 elements, inclusive.
  • Each element of favorites will be a list of integers, separated by a single space, with no leading or trailing spaces.
  • Each element of favorites will contain only digits ('0'-'9') and spaces (' ').
  • Each element of favorites will contain between 1 and 50 characters, inclusive.
  • Each number in each element of favorites will be between 0 and n - 1, inclusive, where n is the number of elements in favorites. Leading zeros are permitted, and numbers may be repeated.
Examples
0)
{"0 2", "1", "0 1"}
Returns: 32

The first two people serve themselves immediately (15 seconds). Then, we have to turn the turntable one unit, in either direction (2 seconds), so the last person can serve himself (another 15 seconds). This takes 32 seconds.

1)
{"0", "0", "0"}
Returns: 49

Here, each person only likes one entree, so they have to be served one at a time. Three servings (15 seconds each) and two single-unit rotations (2 seconds each) takes a total of 49 seconds.

2)
{"4", "1", "2", "3", "0"}
Returns: 50

First, the middle three people take their entrees (15 seconds). Then, we rotate one unit--either way (2 seconds), serve the entree (15 seconds), and then rotate back two units (3 seconds) and serve the last person (15 seconds). All together this takes 50 seconds.

3)
{"0 004", "2 3", "0 01", "1 2 3 4", "1 1"}
Returns: 35

Note here that leading zeros are permitted, and that elements may contain repeats.

4)
{"1 2 3", "0 1 2", "0 1", "2 0000000000000000000000000000000000000000000002"}
Returns: 17
70)
{"0 1","3","0 3","0 1 6","0 3 6","0","0 6"}
Returns: 51

pick 5, 6 and 4 gives 15*3+2*3 = 51

Submissions are judged against all 103 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TurntableService with a public method int calculateTime(vector<string> favorites) · 103 test cases · 2 s / 256 MB per case

Submitting as anonymous