시간 제한메모리 제한제출정답맞힌 사람정답 비율
25 초 (추가 시간 없음) 1024 MB333100.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.

제한

  • 1 ≤ T ≤ 100.
  • R + B > 0.

Test Set 1 (7점)

  • 0 ≤ R ≤ 50.
  • 0 ≤ B ≤ 50.

Test Set 2 (17점)

  • 0 ≤ R ≤ 500.
  • 0 ≤ B ≤ 500.

예제 입력 1

2
2 0
4 5

예제 출력 1

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:

  • one juggler with one red chainsaw
  • one juggler with two red chainsaws
  • one juggler with one blue chainsaw
  • one juggler with three blue chainsaws
  • one juggler with one red chainsaw and one blue chainsaw

출처

Contest > Google > Code Jam > Google Code Jam 2018 > Round 2 B번

채점 및 기타 정보

  • 예제는 채점하지 않는다.