Tuenti Challenge 7

Challenge 9 - The Supreme Scalextric Architect

After many years of pursuing the role, you have been hired as The Supreme Scalextric Architect in a company producing slot car racing tracks. As such, your job is to design the longest and coolest possible Scalextric circuits.

Your company is still new, and for now it only creates three types of basic track sections:

  • Straight sections (S)
  • 90-degree curves (C)
  • Double length straight sections (D)

All types of sections are designed to be easily interoperable, so they all have the same square dimensions (a D section has the same size as two S sections put together).
All sections are flat, no section is designed to intersect or go over or under another.

Input

The first line will contain an integer N, the number of cases for our problem.
Each case consists of a line with three integers separated by spaces: S, C and D, with each representing the number of available sections of the type identified by the corresponding letter.

Output

For each case, a line starting with "Case #x: " followed by the maximum number of sections which can form a closed circuit. If no circuit can be formed with the existing sections, the output will be 0.

Examples

Case 1:

5 2 7
Case 2:

0 4 0
Case 3:

3 7 1

In Case 1, the answer is 0, as it's not possible to create a closed circuit with the given sections.
In Case 2, the answer is 4. You can make a circle-shaped circuit with the 4 curved sections.
In case 3, the answer is 9. You can use every given section except for a single straight and a single curved section. An example circuit would be:

Case 3

Limits

  • 0 ≤ S, C, D ≤ 500

Sample Input

3
5 2 7
0 4 0
3 7 1

Sample Output

Case #1: 0
Case #2: 4
Case #3: 9

Test your code

You can test your program against both the input provided in the test phase and the input provided in the submit phase. A nice output will tell you if your program got the right solution or not. You can try as many times as you want to. Be careful with extra whitespaces, the output should be exactly as described.

Test your program against the input provided in the test phase

Download test input

Program output:

Test your program against the input provided in the submit phase

Download input

Program output:

During the submit phase, in some problems, we might give your program harder inputs. As with the test token, a nice output will tell you if your program got the right solution or not. You can try as many times as you need.

In the actual contest you first need to solve the test phase before submitting the code, you must provide the source code used to solve the challenge and you can only submit once (once your solution is submitted you won't be able to amend it to fix issues or make it faster).

If you have any doubts, please check the info section.