1183C - Computer Game - CodeForces Solution


binary search math *1400

Please click on ads to support us..

Python Code:

import sys
def input():
    return sys.stdin.readline().strip()
def ispossible(make,n,k,a,b):
                return make*a+b*(n-make)<k
for _ in range(int(input())):
    k,n,a,b=map(int,input().split())
    if n*b>=k:
        print("-1")
        continue
    l=0
    r=n 
    ans=0
    while l<=r:
        m= (r-l)//2 + l 
        if ispossible(m,n,k,a,b):
            l=m+1 
            ans=m 
        else:
            r=m-1 
    print(ans)
    
   	  		  	     		  		  			  	

C++ Code:

#include <iostream>
using namespace std;

long long int busca_binaria(long long int k, long long int n, long long int a, long long int b) {
    long long int max = n, min = 0, meio, aux, result;

    while (min <= max) {
        meio = (min + max) / 2;
        aux = n - meio;

        if (meio * a + aux * b < k) {
            result = meio;
            min = meio + 1;
        }
        else if (meio * a + aux * b >= k)
            max = meio - 1;
    }
    
    if (max != - 1)
        return result;
    else
        return max;
}

int main() {
    long long int consulta, k, n, a, b, aux;

    cin >> consulta;

    for (long long int i = 0; i < consulta; i++) {
        cin >> k;
        cin >> n;
        cin >> a;
        cin >> b;

        printf("%lld\n", busca_binaria(k, n, a, b));
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

1029A - Many Equal Substrings
1675D - Vertical Paths
1271C - Shawarma Tent
805A - Fake NP
1163A - Eating Soup
787A - The Monster
807A - Is it rated
1096A - Find Divisible
1430C - Numbers on Whiteboard
1697B - Promo
208D - Prizes Prizes more Prizes
659A - Round House
1492C - Maximum width
171B - Star
1512B - Almost Rectangle
831B - Keyboard Layouts
814A - An abandoned sentiment from past
268C - Beautiful Sets of Points
1391C - Cyclic Permutations
11A - Increasing Sequence
1406A - Subset Mex
1365F - Swaps Again
50B - Choosing Symbol Pairs
1719A - Chip Game
454B - Little Pony and Sort by Shift
1152A - Neko Finds Grapes
1719B - Mathematical Circus
1719C - Fighting Tournament
1642A - Hard Way
285C - Building Permutation