[백준] 1072번: 게임 (retry)

https://www.acmicpc.net/problem/1072

initial

When we find out the win rate at the start (for example 80%), we want to find when it becomes 81% (i.e. there is an integer change).

I initially thought if new_z becomes integer 81, then the difference will be 1 so when diff is 1, we break out of the loop and return mid.

But this is wrong because if new_z is like 81.9, then we can further narrow down the binary search range to maybe like 81.1. So the correct condition is

if new_z is smaller or equal to z, we are getting close to answer.

The edge case if original z is already greater or equal to 99%, then it is impossible to reach 100% because there are already lost games so we return -1.

BTW for python, Z= (cur//total)100 does not work because 80//100 is 0 so 0100 is 0. The multiplication of 100 has to come inside the bracket.

I am still not sure when to do mid -1 or mid +1 and when to return mid or left or whatever. tbc

solution

import sys
input = sys.stdin.readline

total, cur = map(int, input().split())
Z = (cur*100 // total)
if Z>=99:
    print(-1)
    exit()
ans = 0
left = 0
right = total

while left <= right:
    mid = left + (right - left) // 2
    new_z = (cur + mid)* 100 // (total + mid)
    if new_z <= Z:
        left = mid + 1
        ans = mid+1
    else:
        right = mid-1

print(ans)

complexity

The provided code calculates the additional games that need to be played to increase the win rate (Z) from a given value to a target value while considering a total number of games played (total) and games won (cur). Here's the complexity analysis:

1. Reading Input:

   • Reading the values of total and cur takes O(1) time as it involves only simple input operations.

2. Calculation of Z:

   • The calculation of Z takes O(1) time, as it involves simple arithmetic operations.

3. Binary Search:

   • The binary search loop runs until left is less than or equal to right. In the worst case, the loop will run until left and right converge (i.e., until left is very close to right).
   • The binary search performs O(log(total)) iterations since the search space is reduced by half in each iteration.
   • In each iteration, it calculates new_z using simple arithmetic operations and checks whether it's less than or equal to Z.

4. Printing Output:

   • The code prints the final answer, which is a constant time operation.

Overall, the time complexity of the code is dominated by the binary search, which is O(log(total)). The code efficiently finds the number of additional games (ans) needed to achieve the desired win rate (Z).