시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
20 초 (추가 시간 없음) | 1024 MB | 18 | 10 | 9 | 69.231% |
Professor Shekhu was a famous scientist working in the field of game theory in the early days of computer science. Right now, he's working on a game which involves a box containing N distinct cards. The i-th of these cards has a red number written on one side, and a blue number written on the other side. Both of these numbers are positive integers. The game proceeds as follows:
Professor Shekhu has summoned his best student, Akki, to play this game. Can you help Akki find the minimum possible total, considering all possible ways in which he can play the game?
The first line of the input contains an integer T, the number of test cases. T test cases follow; each test case consists of three lines: First line of the each test case will contain an integer N.
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
is the minimum possible total that Akki can attain, if he plays optimally.
2 2 1 2 3 3 3 1 101 501 3 2 3
Case #1: 1 Case #2: 5
In Sample Case #1, Akki has only one move in which he picks up the available cards and has two options.
The second option is better and the answer is 1.
In Sample Case #2, one optimal strategy is to take the red number from first card and the blue number from second card, add 1 ^ 2 = 3 to the total, and return first card to the box. Then, take the red number from first card and the blue number from third card, add 1 ^ 3 = 2 to the total, and return either of the cards to the box. The final total is 5.
Contest > Google > Kick Start > Google Kick Start 2017 > Round G B번