問題一覧 > 通常問題

No.825 賢いお買い物

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 236
作問者 : Pachicobue / テスター : kopricky
11 ProblemId : 2983 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2019-05-02 18:28:01

問題文

青木くんはX国に住んでいます。X国で用いられている硬貨は1G,10Gの2種類です。
青木くんは今、1G硬貨をA枚と10G硬貨をB枚を持ってスーパーマーケットに買い物に来ています。このスーパーマーケットには 1G,2G,...,10100G の商品が揃っています。
青木くんの目的は正の値段の商品を一つ購入し、最終的に財布の中に全部でC枚の硬貨が残るように買い物をすることです。
但し無駄遣いはしたくないので、できるだけ少額の買い物で達成したいです。
最小で何Gの商品を買う必要があるかを求めて下さい。

お金の支払い方は財布から払えて、商品の値段以上の合計金額であれば自由です。
お釣りは1G,10Gを用いて合計枚数が最も少なくなるような構成で返ってきます(この構成は一意に定まることが示されます)。

入力

A B C

一行目に1,10Gの初期所持枚数である A,Bと、最終的な目標硬貨枚数Cが空白区切りで与えられる。

制約
  • 0A,B20
  • 0C100
  • 入力は全て整数である。

出力

目標を達成するために使う最小の価格を一行で出力しなさい。
但しどのように買い物をしても目標が達成できない場合は"Impossible"を出力しなさい(ダブルクオーテーションは不要です)。
最後に改行して下さい。

サンプル

サンプル1
入力
3 10 9
出力
13

13Gの商品を1G 3枚と10G 1枚で支払えば、お釣りは0Gなので財布には10G 9枚が残ります。

サンプル2
入力
20 20 29
出力
2

2Gの商品を1G 12枚で支払えば、お釣りは10G 1枚で返ってくるので、財布には1G 8枚と10G 21枚が残ります。

サンプル3
入力
1 0 1
出力
Impossible

もともと硬貨は1枚ですが、正の値段を支払わないといけないので不可能です。

サンプル4
入力
15 9 41
出力
Impossible

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。