ZOJ Problem Set - 1153
In many competitions, players are given seeding numbers to represent their relative strength, where the best player is given seed #1, the second best is given seed #2, etc.. The seeding of a single elimination tournament is an arrangement of matches which keeps the best players from playing each other until as late as possible (the last round with players seeded 1 and 2). Define the strength for a match as the sum of the two seeds in the match, and the ideal strength as the strength for the match assuming the best two players make it to that match (or in other words, the minimum sum of the two seeds which cound play in that match). The total number of rounds r needed for a tournament of n contestants is given be the formula r = ceiling(log(2,n)). If we call the finals of the tournament round r, the semi-finals round r-1, etc., then the way in which seeding is done can be described as follows: in round k, we arrange players such that the ideal match strength for all matches in that round is 2^(r-k+1)+1. For example, the seeding of a match of 13 people would look as follow:
You are asked to solve the following problem: given the values of n and m, determine the earliest round in a tournament of n players in which a match strength of m could occur. You may assume that the seeding is done in the manner described above.
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
You will be given a number of cases in the input. Each case will be specified on one line, consisting of two integers n and m, where 2 <= n <= 100 and m >= 3. You may assume in each case that a match strength of m can occur during some round. Input is terminated by a case in which n = m = 0.
For each test case, print the case number and the earliest round for that case in format shown below.
Case 1: Round 7
Source: East Central North America 1999, Practice