ABC195 B - Many Oranges

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import datetime

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def it(): return tuple(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B, W = il()
    W *= 1000

    mi, ma = INF, 0
    for i in range(0, W+1):
        if A * i <= W <= B * i:
            mi = min(mi, i)
            ma = max(ma, i)

    if mi == INF:
        print('UNSATISFIABLE')
    else:
        print(mi, ma)


if __name__ == '__main__':
    main()

考え方

みかんをN個選択したとき、
みかんの重さとしてあり得るのは最低でA * N、最高でB * Nです。
このとき、A * N <= W <= B * Nとなれば、N個で丁度Wキログラムにすることが可能です。

Nの範囲はAが最低でも１グラムであることが保証されているため1 <= N <= W * 1000となります。
（みかんはグラム単位、合計の重さがキログラム単位のため単位を一致させる必要がある）