天平称重问题

问题描述

Iyo Kiffa-Australis女士有一个天平，只有两种砝码来测量药物的剂量。例如：

• 要称量200毫克阿司匹林，使用300毫克和700毫克砝码：
  • 方案1：药物侧放1个700mg砝码，另一侧放3个300mg砝码（共4个砝码）
  • 方案2：药物侧放4个300mg砝码，另一侧放2个700mg砝码（共6个砝码，不被采用）
• 她总是选择使用砝码总数最少的方案。

输入格式

输入是一系列数据集，每行包含三个正整数a、b和d（空格分隔）：

• a ≠ b
• a ≤ 10000
• b ≤ 10000
• d ≤ 50000
• 保证有解

输入结束标志是"0 0 0"。

输出格式

对每个数据集，输出两个非负整数x和y（空格分隔），满足：

1. 可以使用x个a mg砝码和y个b mg砝码称量d mg
2. 砝码总数(x+y)是所有可行解中最小的
3. 在满足最少砝码数的解中，选择总质量(ax+by)最小的

示例输入/输出

来源

日本2004程序设计竞赛