In order to practice for the Round 1 of Google Code Jam 2012, which is coming in two weeks, I started solving the problems of the same round of last year’s edition. Below you’ll find the first one:

The Problem

I played D (D > 0) games of FreeCell today. Each game of FreeCell ends in one of two ways — I either win, or I lose. I’ve been playing for many years, and have so far played G games in total (obviously, G ≥ D).

At the end of the day, I look at the game statistics to see how well I have played. It turns out that I have won exactly PD percent of the D games today, and exactly PG percent of G total games I had ever played. Miraculously, there is no rounding necessary — both percentages are exact! Unfortunately, I don’t remember the exact number of games that I have played today (D), or the exact number of games that I have played in total (G). I do know that I could not have played more than N games today (D ≤ N).

Are the percentages displayed possible, or is the game statistics calculator broken?

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line contains 3 integers — N, PD and PG.

Output

For each test case, output one line containing “Case #x: y”, where x is the case number (starting from 1) and y is either “Possible” or “Broken”.

Limits

0 ≤ PD ≤ 100;
0 ≤ PG ≤ 100.

Small dataset

1 ≤ T ≤ 100;
1 ≤ N ≤ 10.

Large dataset

1 ≤ T ≤ 2000;
1 ≤ N ≤ 1015.

Sample Input
3
1 100 50
10 10 100
9 80 56

Sample Output
Case #1: Possible
Case #2: Broken
Case #3: Possible

My Solution

First of all you need to test all possible Ns and to see if there is one that will yield a natural number when the percentage of wins is applied to it. If you find one of such numbers then you just need to rule the impossible results on the edges (which is 100% of wins in PG and less than 100% in PD, and 0% of wins in PG and more than 0% of wins on PD).

My solution below solved the small input but was too slow on the large one. I am working on that.

#include <stdio.h>

int main(){
  int t,i;
  int n,pd,pg;
  int j, wins;
  int numerator,denominator;

  scanf("%d",&t);

  for (i=0;i<t;i++){
    scanf("%d %d %d",&n,&pd,&pg);
    printf("Case #%d: ",i+1);
    for (j=1;j<=n;j++){
      if ((j*pd)%100==0){    
        if (!(pg==0&&pd>0)){  
          if (!(pg==100&&pd<100)){  
            printf("Possible");
            goto fromhere;    
          }
        }        
      }
    }
    printf("Broken");
    
    fromhere:
    if (i<t-1)
      printf("n");    
  }

return 0;
}