#include <iostream>
using namespace std;
int main() {
    int K,A,B, MAX = 200000;
    while(cin>>A>>B>>K) {
        int N;
        for (N = 0; N < MAX; N++) {
            if ((N*K - A) < 0 || ((N*K - A) & 0x1) != 0) 
                continue;
            if ((N*K - A)/2 <= A*((N-1)/2) + B*(N/2) || A == 0) 
                break;
        }
    	if (N < MAX) 
            cout<<N<<endl;
        else 
            cout<<-1<<endl;
    }
    return 0;
}

#include<iostream>
#include<cmath>
using namespace std;

int function(int A, int B, int K){
	int remainder = A % K;//直接翻转后的剩余待翻转个数
	int count = A / K;//直接翻转
	int S = A + B;//总个数
	if (A == 0 || remainder == 0)
		;
	else if ((S <= K) || (remainder % 2 == 1 && K % 2 == 0))
		count = -1;//无法翻成功的输出-1
	else if ((K + remainder) % 2 == 0 && count > 0 && B + K * count >= 2 * K - (remainder + K) / 2)
		count++;//一种特殊情况，还剩下K+remainder个0时直接翻两次即可完成
	else if (remainder % 2 == 0)
		count += 2 * ceil(remainder / double(2 * (S - K)));
       //每翻两次最多能把remainder中的2*(S-K)个0翻成1，注意这里指的是最多，当翻最后2次或者S-K>remainder/2时，只需翻两次，所以这里用到了ceil（）
	else
		count += 2 * ceil((K - remainder) / double(2 * (S - K))) + 1;
       //当remainder是奇数时，相当于先把所有1中的K-remainder个翻成0，这样加上remainder一共K个0，只需额外再翻一次即可，K-remainder是奇数时，永远不能翻成功，是偶数时，翻转方法同上面
	return count;
}

int main(){
	int A, B, K;
	cin >> A >> B >> K;
	cout << function(A, B, K);
	return 0;
}
//没有循环，只用到了条件语句，时间复杂度O(1),空间复杂度O(1)

import sys
def main(A, B, K):
    if A == 0: return 0
    if K == 0: return -1
    if A % K == 0: return A / K
    if A & 1 > K & 1 or K >= A + B: return -1
    ret = A // K + 1
    while 1:
        if (ret * K - A) & 1 == 0 and ret * K <= ret * (A + B) - (A, B)[ret & 1]:
            return ret
        ret += 1
print main(*map(int, sys.stdin.readline().split()))

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/*
 * 问题：一行数字，初始有a个0和b个1，现在目标是把所有的值都变为1，每次可以任意选择恰好k个数字，并将这个k个数字
 * 的值进行翻转（0变成1,1变成0）。请问达到目标最少需要几次操作。
 */
/*
 * 有初始状态和结束状态，求最少操作次数。显然这是一个宽度优先遍历（BFS）
 * 初始状态：a个0，b个1
 * 结束状态：0个0，（a+b）个1
 * 边（规则）：每次可以翻转k个数
 */
public class FanZhuan {
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		int a=scanner.nextInt();
		int b=scanner.nextInt();
		int k=scanner.nextInt();
		scanner.close();
		
		int count=BFS(a, b, k);
		System.out.println(count);
	}
	public static int BFS(int a,int b,int k){
		if(a==0 && b==0){
			return 0;
		}
		if(k>a+b){
			return -1;
		}
		
		Node node=new Node(a, b, 0);//初始状态
		Queue<Node> queue=new LinkedList<>();//队列
		boolean[] vis=new boolean[a+b+1];//判断是否出现过
		Arrays.fill(vis, false);//全部初始化成false
		queue.add(node);
		vis[a]=true;
		while(!queue.isEmpty()){
			Node temp=queue.poll();
			if(temp.a==0){
				return temp.step;
			}
			//选择k个数字进行反转，假设选择了i个0，i要小于等于a和k的最小值，i至少为1
			//这时1翻转的次数就为k-i
			for(int i=1;i<=Math.min(temp.a, k);i++){
				if(temp.b<k-i){//没有那么多1可供翻转，那就继续，多翻转一个0
					continue;
				}
				int newa=temp.a-i+(k-i);//翻转i个0后，还剩余的0的个数。
				if(newa==0){
					return temp.step+1;
				}
				//判断newa个0的情况有没有出现过
				if(!vis[newa]){
					vis[newa]=true;
					queue.add(new Node(newa, a+b-newa, temp.step+1));
				}
				
			}	
		}
		return -1;
		
	}
}
class Node{
	int a;//表示0的个数
	int b;//表示1的个数
	int step;//表示操作次数
	public Node(int a,int b,int step) {
		this.a=a;
		this.b=b;
		this.step=step;
	}
}

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int K = sc.nextInt();
        sc.close();
        int g = A % K;
        if (g == 0) {//能直接整除
            System.out.println(A / K);
            return;
        }
        if (A + B <= K) {//缺少交换空间
            System.out.println("-1");
            return;
        }
        if ((K % 2 == 0) && (g % 2 == 1)) {//剩余0的个数总为奇数，不可能有结果
            System.out.println("-1");
            return;
        }
        //下面分支对交换空间是否充足进行分析
        //交换空间成立条件A + B - g >= K - g / 2（其中最差的情况就是g=2时）
        //说明只要在一次交换中尽可能减小g的值，就能最快的完成全部交换
        if (g == A) {
            int count = 0;
            if (K % 2 == 0) {//如果K为偶数，则当前剩余0的个数一定是偶数
                while (true) {
                    if ((g % 2 == 0) && (A + B - g >= K - g / 2)) {
                        count = count + 2;
                        break;
                    }
                    if (count % 2 == 0) {
                        count++;
                        g = A + B - (K - (A + B - g));
                    }
                    if (count % 2 == 1) {
                        count++;
                        g = K - g;
                    }
                }
            } else {
                while (true) {//如果K为偶数，则当前剩余0的个数是一次奇数一次偶数的交替
                    if ((g % 2 == 0) && (A + B - g >= K - g / 2)) {
                        count = count + 2;
                        break;
                    }
                    if (g % 2 == 0) {
                        count++;
                        g = A + B - (K - (A + B - g));
                    }
                    if (g % 2 == 1) {
                        count++;
                        g = K - g;
                    }
                }
            }
            System.out.println(A / K + count);
            return;
        }
        if (A > 2 * K||B >(K+(g-A)/2)) {
            //举例A=10000 B=10000 K=548时，不需要贪心的交换到A剩余136的时候
            //只需要交换到684的时候，进行两次交换即可全1，而不是贪心到底要多一次
            System.out.println(A / K + 1);
            return;
        }
        if (g < A)
            if (g % 2 == 0) {
                System.out.println(A / K + 2);
                return;
            } else {
                System.out.println(A / K + 3);
                return;
            }
    }
}

# coding=utf-8

"""
@author: beyourself
@time: 2018/5/28 9:58
@file: 01flip-flop.py
"""

A, B, K = [int(i) for i in input().split()]
MAX = 200000
for N in range(0, MAX + 2):
    if (N * K - A < 0) or (((N * K - A) & 0x1) != 0):
        continue
    if ((N * K - A) // 2 <= A * ((N - 1) // 2) + B * (N // 2)) or (A == 0):
        break

if N < MAX:
    print(N)
else:
    print('-1')

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Step {
	public int a;
	public int b;
	public int step;
	public Step(int a, int b, int step) {
		super();
		this.a = a;
		this.b = b;
		this.step = step;
	}
	
}

public class Main {
	
	private static Scanner in = new Scanner(System.in);
	
	public static void main(String[] args) {
		
		int a = in.nextInt();
		int b = in.nextInt();
		int k = in.nextInt();
		int ans = BFS(a,b,k);
		System.out.println(ans);	
		
	}
	
	public static int BFS(int a, int b, int k) {
		int n = a+b;
		boolean[] vis = new boolean[n+1];
		Arrays.fill(vis, false);
		Queue<Step> q = new LinkedList<>();
		Step start = new Step(a,b,0);
		q.offer(start);
		vis[a] = true;
		
		while(!q.isEmpty()) {
			Step s = q.poll();
			if(s.a == 0) {
				return s.step;
			}
			for(int i = 1; i <= Math.min(s.a, k); i++) {
				if(s.b < k-i) {
					continue;
				}
				int next = s.a-i+(k-i);
				if(next == 0) {
					return s.step+1;
				}
				if(!vis[next]) {
					vis[next] = true;
					q.offer(new Step(next, n-next, s.step+1));
				}
			}
		}
		return -1;
	}
	
}

1. 很像网易游戏雷火那道推箱子题目，宽度优先。

2. 0 和 1 的个数决定当前状态，更确切说0的个数旧决定了当前状态。 如果下一步翻转i个0 ，则必然要翻转 K-m 个1，遍历0的合法的翻转个数，从而推出下一个所有可能状态。 每个状态记录到达此状态的转移步数，用mm记录， 从上一个状态到下一个状态，下一个状态步数即上一个状态步数+1 ， 第一次到达0个0的状态的步数就是最短步数。

3. 注意边界条件，没有0的时候不需要翻转，输出0.

4.不要试图用标准库的unordered_map,会超时，用数组存储状态。

#include
#include
#include
#include
using std::vector;
using std::cout;
using std::cin;
using std::string;
using std::queue;
int main()
{
    int A ;
    int B ;
    int K ;
    cin>>B>>A>>K ;
// if no zeros , no need to change, number of steps = 0
    if(B==0){cout<<0;return 0;}
    int mm[A+B+1];
    for(int i =0 ; i< A+B+1; i++)mm[i]= 0;

    mm[B] = 1;
    queue> que ;
    que.push({A,B});
    while(!que.empty())
    {
          vector tt = que.front();
          que.pop();
          int ones = tt[0];
          int zeros= tt[1];  
          int maxE = K-ones > 0 ? K-ones:0;
          for(int i = zeros>K?K:zeros; i>=maxE ; i--)
           if(mm[zeros - i + (K-i)]==0)
          { 
               if(zeros - i + (K-i) ==0){
               cout <<mm[zeros];
               return 0;
           }
              mm[zeros -i + (K-i)] = mm[zeros]+1;
             que.push({ones+i-(K-i) , zeros - i+(K-i)});   
          }          
    }
  cout <<-1;
  return 0;
}

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/*
 * 参考大神：https://www.nowcoder.com/questionTerminal/9c4c9d10e3db4448b906c6e6cea22b7f @OceanFan
 * 有部分人使用数学推断得到结果但是比较难想，使用bfs还好理解一点
 * 有起始状态和结束状态，计算其中的变化信息考虑使用bfs
 * */
public class Reverse01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int k = scanner.nextInt();
            System.out.println(reverse01(a, b, k));
        }
    }

    private static int reverse01(int a, int b, int k) {
//        已经完成
        if (a == 0 && b == 0) {
            return 0;
        }
//        不可能反转成功
        if (a + b < k) {
            return -1;
        }

        boolean[] visited = new boolean[a + b + 1];
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(a, b, 0));
        visited[a] = true;
        while (!queue.isEmpty()) {
            Node tmp = queue.poll();
            if (tmp.a == 0) {
                return tmp.times;
            }
//            对于1~min(tmp.a,k)个0进行反转
            for (int i = 1; i <= Math.min(tmp.a, k); i++) {
//                1不够反转,继续操作
                if (k - i > tmp.b) {
                    continue;
                }
                int newa = tmp.a - i + (k - i);
                if (newa == 0) {
                    return tmp.times + 1;
                }
                if (!visited[newa]) {
                    visited[newa] = true;
                    queue.add(new Node(newa, tmp.a + tmp.b - newa, tmp.times + 1));
                }
            }
        }
        return -1;
    }

    private static class Node {
        int a, b, times;

        public Node(int a, int b, int times) {
            this.a = a;
            this.b = b;
            this.times = times;
        }
    }
}

//使用深搜，通过只有70%。。。。。。 import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;

/**
 * Created by Administrator on 2017/8/21.
 * 模拟1--01翻转
 */
public class Main {
    static int count;
    static int min;
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            int a = in.nextInt();
            int b = in.nextInt();
            int k = in.nextInt();
            if (a==0){
                System.out.println(0);
                continue;
            }

            count = 0;
            HashMap<Integer,Integer> hashMap = new HashMap<Integer, Integer>(a+b);
            hashMap.put(a,b);
            min = Integer.MAX_VALUE;
            solve(a,b,k,hashMap);
            if(min!=Integer.MAX_VALUE)
                System.out.println(min);
            else
                System.out.println(-1);
        }

    }

    private static boolean solve(int a, int b, int k, HashMap<Integer, Integer> hashMap) {
        if (a%k==0){
            count++;
            min = Math.min(min,count);
            return true;
        }

        for (int i = 0; i <=k && i<=a; i++) {
            if (b<k-i){
                continue;
            }
            if (!hashMap.containsKey(a-i+k-i)){
                hashMap.put(a-i+k-i,b-(k-i)+i);
                count++;
                solve(a-i+k-i,b-(k-i)+i,k,hashMap);
                count--;
                hashMap.remove(a-i+k-i);

            }
        }
        return false;
    }
} 

/*
用个最傻的办法，遍历翻牌子的状态空间，跑的慢，不过也没超时
*/
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main(){
	int a, b, k;
	while ((cin >> a >> b >> k)){
        int n = a + b;//最大0的个数
        vector<int> dp(n + 1, 0);//记录到达i个0状态的最少步数，0表示不可达
        queue<int> q;
        //去一些最简单的情况
	if (a == 0) cout << 0 << endl;
	else if (k >= a + b){
		if (k == a) cout << 1 << endl;
		else cout << -1 << endl;
	}
	else{
            dp[a] = 1;//初始状态
            q.push(a);
            while (!q.empty()){
                a = q.front();//当前状态a个0，n-a个1
                q.pop();
                for (int i = min(k, a); i >= 0; --i){//i为翻0的个数
                    if (k - i > n - a) break;//k-i为翻1的个数，不够翻就退出循环
//翻i个0,0的个数-i，就得翻k-i个1,0的个数+k-i，总计0个数的变化=-i+k-i=k-2*i
                    int new_a = a + k - 2 * i;//翻完后0的个数
                    if (dp[new_a] == 0){
                        dp[new_a] = dp[a] + 1;
                        q.push(new_a);
                    }
                }
            }
            cout << dp[0] - 1 << endl;
		}
	}

	return 0;
}

import java.util.*;  class Step { public int a;  public int b;  public int step;  public Step(int a, int b, int step) { this.a = a;  this.b = b;  this.step = step;  }
} public class Main { public static void main(String[] args) {
        Scanner in = new Scanner(System.in);  int a = in.nextInt();  int b = in.nextInt();  int k = in.nextInt();  int ans = BFS(a,b,k);  System.out.print(ans);  } public static int BFS(int a, int b, int k) { int n = a+b;  boolean[] vis = new boolean[n+1];  Arrays.fill(vis, false);  Queue<Step> q = new LinkedList<>();  Step start = new Step(a,b,0);  q.offer(start);  vis[a] = true;  while(!q.isEmpty()) {
            Step s = q.poll();  if(s.a == 0) { return s.step;  } for(int i = 1; i <= Math.min(s.a, k); i++) { if(s.b < k-i) { continue;  } int next = s.a-i+(k-i);  if(next == 0) { return s.step+1;  } if(!vis[next]) {
                    vis[next] = true;  q.offer(new Step(next, n-next, s.step+1));  }
            }
        } return -1;  }
}

用深搜的，通过50%，一直报错“请检查是否存在数组越界等非法访问情况”，但是检查了好
几遍也没发现有数组越界的情况，是不是递归导致栈溢出了？

import java.util.*;
public class Main{     
    static int tmin(int zeros, int ones, int k, boolean visited[]){
        if(zeros == 0)  return 0;
        if(zeros == k) return 1;
        if(visited[zeros])  return -1;//陷入无限循环中,无解
        visited[zeros] = true;
        int re_max = Math.min(zeros, k);//最多反转max个0
        int re_min = Math.max(0,k - ones);//最少反转min个0
        //re_min可能与re _max相等
        int min =  -1;//无解
        //i:反转i个0,剩下的用于反转1
        for(int i = re_min; i <= re_max; ++i){
            int nzeros = zeros - i + (k - i);
            int tmp = tmin(nzeros,ones+zeros-nzeros,k,visited);
            if(tmp == -1)	continue;
            else if(min == -1) min = tmp;
            else min = Math.min(min,tmp);
        }
        if(min == -1)   return -1;
        else return min+1;
    }
    public static void main(String[] arg){
        Scanner sc = new Scanner(System.in);
        int zeros = sc.nextInt(), ones = sc.nextInt(), k = sc.nextInt();
        if(k > ones+zeros)  return ;
        if(k == 0 || zeros < 0 || ones < 0)  return ;
        boolean visited[] = new boolean[zeros+ones+1];
        System.out.print(tmin(zeros,ones,k,visited));
        return ;
    }
}

include<iostream>

using namespace std;

int main() { int A,B,K; cout>A>>B>>K; int x,y,m,n,t; x=A%K; y=B%K; m=A/K; n=B/K; if(x==0) { t=m; } else { if(x%2==0) { t=m*2+x; } else { t=m-1+x/2+K+1; } } cout<<"需要最少的操作次数是："<<t<<endl; }

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

/**
 * 牛牛正在挑战一款名为01翻转的游戏。游戏初始有A个0,B个1，牛牛的目标就是把所有的值都变为1，每次操作牛牛可以任意选择恰好K个数字，并将这K个数字的值进行翻转(0变为1，1变为0)。牛牛如果使用最少的操作次数完成这个游戏就可以获得奖品，牛牛想知道最少的操作次数是多少？
 例如:A = 4 B = 0 K = 3
 0000 -> 1110 -> 1001 -> 0100 -> 1111
 需要的最少操作次数为4
 * Created by Administrator on 2017/3/19.
 */


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            Integer a = sc.nextInt();
            Integer b = sc.nextInt();
            Integer n = a+b;
            Integer k = sc.nextInt();

            System.out.println(caozuo3(a,n,k));
        }
    }

/**
BFS遍历
**/
    public static int caozuo3(int a,int n,int k){
        if (a==0){
            return 0;
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        int[] visited = new int[n+1];
        int[] disk = new int[n+1];
        queue.offer(a);
        visited[a] = 1;
        disk[a] = 0;
        while (!queue.isEmpty()){
            int local = queue.remove();
            for (int i=1;i<=k;i++){
                if (i<=local&&k-i<=n-local){
                    int next = local-2*i+k;
                    if (visited[next]==0){
                        if (next==0)return disk[local]+1;
                        queue.offer(next);
                        visited[next] = 1;
                        disk[next] = disk[local]+1;
                    }

                }
            }
        }
        return -1;
    }
}