Connection Status:
Competition Arena > VolumeGuess

VolumeGuess

SRM 191 · 2004-04-24 · by Ishan

SRM 191 · 2004-04-24 · by Ishan · Brute Force
Class Name: VolumeGuess
Return Type: int
Method Name: correctVolume
Arg Types: (vector<string>, int, int)
Problem Statement

Problem Statement

You are given a certain number of boxes (numberOfBoxes) of different volumes. The boxes are numbered 1 to numberOfBoxes. After this, I then make comparisions between every pair of boxes and, for each pair, tell you the volume of the smaller box. Given this data, you have to tell me the size of the box numbered ithBox. (The box numbered ithBox will not be one of the two largest boxes.)

You are given a String[], queries, each element of which describes a single comparision and is of the form "box1,box2,volume" (quotes for clarity) where box1 and box2 are the numbers of the two boxes being compared and volume is the volume of the smaller box. For instance, if I compare the boxes numbered 5 and 6, which have volumes 10 and 99, respectively, the query will be represented as "5,6,10" (quotes for clarity).

Notes

  • Keep in mind, the volume of the largest box is irrelevant.

Constraints

  • numberOfBoxes will be between 3 and 9, inclusive.
  • queries will contain exactly numberOfBoxes*(numberOfBoxes-1)/2 elements.
  • Every element of queries will be in the given format ("box1,box2,volume", quotes for clarity).
  • Each element of queries will contain between 5 and 50 characters, inclusive.
  • Each box1 will be an integer between 1 and numberOfBoxes, inclusive, with possible leading zeros.
  • Each box2 will be an integer between 1 and numberOfBoxes, inclusive, with possible leading zeros.
  • Each volume will be an integer between 1 and 500, inclusive, with possible leading zeros.
  • queries will contain no duplicates, that is, no pair of boxes will be compared twice.
  • No two boxes will have the same volume.
  • ithBox will be between 1 and numberOfBoxes, inclusive.
  • The given data will be consistent.
  • The box numbered ithBox will not be one of the two largest boxes.
Examples
0)
{"1,2,10","1,3,10","2,3,20"}
3
1
Returns: 10

If box 1 has volume 10, box 2 has volume 20 and box 3 has volume 30, we get the given data. Another possibility is box 1 has volume 10, box 2 has volume 30 and box 3 has volume 20. Another is box 1 has volume 10, box 2 has volume 45 and box 3 has volume 20. There are many possibilities (infinite in fact). However, in all of them box 1 has to have size 10.

1)
{"1,02,10","2,3,010","1,3,20"}
3
2
Returns: 10

If box 1 has volume 20, box 2 has volume 10 and box 3 has volume 30, we get the given data. (Note that leading zeros are allowed.)

2)
{"1,2,31","1,3,9","1,4,31","2,4,32","3,4,9","3,2,9"}
4
1
Returns: 31

One possibility is box 1 has volume 31, box 2 has volume 50, box 3 has volume 9 and box 4 has volume 32.

3)
{"1,2,31","1,3,9","1,4,31","2,4,32","3,4,9","3,2,9"}
4
3
Returns: 9

Same situation as above, but asks for a different ithbox.

4)
{"3,2,80","5,2,15","1,2,193","3,1,80","5,1,15","5,3,15","3,4,3","4,5,3","2,4,3","4,1,3"}
5
3
Returns: 80

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

Coding Area

Language: C++17 · define a public class VolumeGuess with a public method int correctVolume(vector<string> queries, int numberOfBoxes, int ithBox) · 48 test cases · 2 s / 256 MB per case

Submitting as anonymous