Problem 7

All submissions for this problem are available.
You are playing a game where you initially have A zeros and B ones.
Your goal is to end up with all ones.
In each move, you must choose exactly K of the numbers and flip their values (zeros change to ones, and viceversa).
You can choose any K numbers each time, regardless of their current values or whether you have flipped them before.
Input
The first line of input specifies the number of test cases t followed by t test cases.(1<=t<=20)
For each test case there are three values A(0<=A<=100000),B(0<=A<=100000), and K(1<=A<=100000),
all seperated by spaces.
Output
Output is the minimal number of moves required to win the game, or 1 if it is impossible.
Examples
Input 3 3 0 3 4 0 3 3 2 5 OutPut 1 4 1 For the first test case you initially have 3 zeros and 0 ones, and you must flip 3 numbers in each move. Your only possible move is to flip every number. After the first move, you end up with all ones and win the game. Second test case is similar to the previous example, but this time, you have 4 zeros. Here's one minimal sequence of moves that will lead to a win: 0. 0000 (the initial state) 1. 1110 (first three numbers flipped) 2. 1001 (last three numbers flipped) 3. 0100 (first, second and fourth numbers flipped) 4. 1111 (first, third and fourth numbers flipped) Third test case is self explanatory, no moves formed.
Author:  admin 
Tags  admin 
Date Added:  21092009 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.4, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 