B - Many Oranges 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200 点

問題文

みかんがたくさんあります。どのみかんの重さも A グラム以上 B グラム以下であることがわかっています。（みかんの重さは整数とは限りません。）

この中からいくつかのみかんを選んだところ、選んだみかんの重さの合計がちょうど W キログラムになりました。

選んだみかんの個数として考えられる最小値と最大値を求めてください。ただし、このようなことが起こり得ないなら、かわりにそのことを報告してください。

制約

  • 1 \leq A \leq B \leq 1000
  • 1 \leq W \leq 1000
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

A B W

出力

選んだみかんの個数としてありえる最小値と最大値を空白区切りでこの順に出力せよ。ただし、与えられた条件に合うような個数が存在しない場合、かわりに UNSATISFIABLE と出力せよ。

入力例 1

100 200 2

出力例 1

10 20

みかん 1 個の重さは 100 グラム以上 200 グラム以下です。

  • 200 グラムのみかんを 10 個選んだとき、重さの合計はちょうど 2 キログラムになります
  • 100 グラムのみかんを 20 個選んだとき、重さの合計はちょうど 2 キログラムになります

9 個以下または 21 個以上でちょうど 2 キログラムになることはないので、10 個と 20 個がそれぞれ最小値と最大値になります。

入力例 2

120 150 2

出力例 2

14 16

みかん 1 個の重さは 120 グラム以上 150 グラム以下です。

  • 例えば 140 グラムのみかん 10 個と、150 グラムのみかん 4 個を選んだとき、重さの合計はちょうど 2 キログラムになります
  • 例えば 120 グラムのみかん 8 個と、130 グラムのみかん 8 個を選んだとき、重さの合計はちょうど 2 キログラムになります

13 個以下または 17 個以上でちょうど 2 キログラムになることはないので、14 個と 16 個がそれぞれ最小値と最大値になります。

入力例 3

300 333 1

出力例 3

UNSATISFIABLE

みかん 1 個の重さは 300 グラム以上 333 グラム以下です。

このようなみかんいくつかの重さの合計がちょうど 1 キログラムになることはありえません。

Score : 200 points

Problem Statement

We have many oranges. It is known that every orange weighs between A and B grams, inclusive. (An orange can have a non-integer weight.)

We chose some of those oranges, and their total weight was exactly W kilograms.

Find the minimum and maximum possible numbers of oranges chosen. If no set of oranges can weigh exactly W kilograms in total, report that fact.

Constraints

  • 1 \leq A \leq B \leq 1000
  • 1 \leq W \leq 1000
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B W

Output

Print the minimum and maximum possible numbers of oranges chosen, in this order, with space in between. If there is no number of oranges that can have the specified total weight, print UNSATISFIABLE instead.

Sample Input 1

100 200 2

Sample Output 1

10 20

Here, one range weighs between 100 and 200 grams (inclusive).

  • If we choose 10 200-gram oranges, their total weight will be exactly 2 kilograms.
  • If we choose 20 100-gram oranges, their total weight will be exactly 2 kilograms.

With less than 10 oranges or more than 20 oranges, the total weight will never be exactly 2 kilograms, so the minimum and maximum possible numbers of oranges chosen are 10 and 20, respectively.

Sample Input 2

120 150 2

Sample Output 2

14 16

Here, one range weighs between 120 and 150 grams (inclusive).

  • If we choose 10 140-gram oranges and 4 150-gram oranges, for example, their total weight will be exactly 2 kilograms.
  • If we choose 8 120-gram oranges and 8 130-gram oranges, for example, their total weight will be exactly 2 kilograms.

With less than 14 oranges or more than 16 oranges, the total weight will never be exactly 2 kilograms, so the minimum and maximum possible numbers of oranges chosen are 14 and 16, respectively.

Sample Input 3

300 333 1

Sample Output 3

UNSATISFIABLE

Here, one range weighs between 300 and 333 grams (inclusive).

No set of oranges of this kind can weigh exactly 1 kilograms in total.