|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|25 초 (추가 시간 없음)||1024 MB||3||3||3||100.000%|
You are the manager of the Graceful Chainsaw Jugglers performance group, and you are trying to succeed in the very competitive chainsaw juggling business. You have an unlimited number of identical talented jugglers, and each of them knows how to juggle any number of chainsaws. To run a show, you will choose some number of jugglers, and then distribute your red chainsaws and blue chainsaws among them, so that each juggler gets at least one chainsaw. For example, one juggler might juggle two red chainsaws and three blue chainsaws, and another juggler might juggle just one red chainsaw. During the show, each chainsaw is used by only one juggler; the jugglers do not pass chainsaws around, because it is already hard enough just to juggle them!
According to your market research, your audience is happiest when the show uses as many jugglers and chainsaws as possible, but the audience also demands variety: no two jugglers in the show can use both the same number of red chainsaws and the same number of blue chainsaws.
You have R red chainsaws and B blue chainsaws, and you must use all of them in the show. What is the largest number of jugglers that you can use in the show while satisfying the audience's demands?
The first line of the input gives the number of test cases, T; T test cases follow. Each test case consists of one line with two integers R and B: the numbers of red and blue chainsaws that you must use in the show.
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 largest number of jugglers that you can use in the show while satisfying the audience's demands, as described above.
2 2 0 4 5
Case #1: 1 Case #2: 5
In Sample Case #1, the only possible strategy is to give both red chainsaws to one juggler.
In Sample Case #2, one optimal strategy is to have:
Contest > Google > Code Jam > Google Code Jam 2018 > Round 2 B번