## Google Code Jam '10 Round 1A Problem C - Number Game

View as PDF

Points: 20 (partial)
Time limit: 90.0s
Memory limit: 1G

Problem types

Arya and Bran are playing a game. Initially, two positive integers and are written on a blackboard. The players take turns, starting with Arya. On his or her turn, a player can replace with for any positive integer , or replace with for any positive integer . The first person to make one of the numbers drop to zero or below loses.

For example, if the numbers are initially , the game might progress as follows:

• Arya replaces with , leaving on the blackboard.
• Bran replaces with , leaving on the blackboard.
• Arya replaces with , leaving on the blackboard.
• Bran replaces one with , and loses.

We will say is a winning position if Arya can always win a game that starts with on the blackboard, no matter what Bran does.

Given four integers , , , , count how many winning positions there are with and .

#### Input Specification

The first line of the input gives the number of test cases, . test cases follow, one per line. Each line contains the four integers , , , , separated by spaces.

#### Output Specification

For each test case, output one line containing Case #x: y, where is the case number (starting from 1), and is the number of winning positions with and .

#### Limits

Memory limit: 1 GB.

.

.

.

##### Small Dataset

Time limit: 30 seconds.

.

.

##### Large Dataset

Time limit: 90 seconds.

.

.

3
5 5 8 8
11 11 2 2
1 6 1 6

Case #1: 0
Case #2: 1
Case #3: 20

#### Note

This problem has different time limits for different batches. If you exceed the Time Limit for any batch, the judge will incorrectly display >90.000s regardless of the actual time taken. Refer to the Limits section for batch-specific time limits.