首页 > 试题广场 >

01翻转

[编程题]01翻转

热度指数：1895 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

输入为一行： 一共三个整数A(0 ≤ A ≤ 100,000),B(0 ≤ B ≤ 100,000),K(1 ≤ K ≤100,000).以空格分隔

输出描述:

输出一个整数，表示最少需要的操作次数。如果不能完成，则输出-1

示例1

输入

4 0 3

输出

算法知识视频讲解

Python

beyourselfUltra

# 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')

发表于 2018-05-28 10:10:52 回复(0)