#PU615. USACO 2016 February Contest, Bronze — Problem 1. Milk Pails

    ID: 1350 传统题 文件IO:pails 2000ms 256MiB 尝试: 0 已通过: 0 难度: 普及 上传者: 标签>USACO赛事:feb16来源:usaco.orgscoring:equal_test_cases枚举

USACO 2016 February Contest, Bronze — Problem 1. Milk Pails

USACO 2016 February Contest, Bronze — Problem 1. Milk Pails

题目描述

Farmer John has received an order for exactly MM units of milk (1≤M≤1,0001 \leq M \leq 1,000) that he needs to fill right away. Unfortunately, his fancy milking machine has just become broken, and all he has are three milk pails of integer sizes XX, YY, and MM (1≤X<Y<M1 \leq X < Y < M). All three pails are initially empty. Using these three pails, he can perform any number of the following two types of operations:

  • He can fill the smallest pail (of size XX) completely to the top with XX units of milk and pour it into the size-MM pail, as long as this will not cause the size-MM pail to overflow.
  • He can fill the medium-sized pail (of size YY) completely to the top with YY units of milk and pour it into the size-MM pail, as long as this will not cause the size-MM pail to overflow. Although FJ realizes he may not be able to completely fill the size-MM pail, please help him determine the maximum amount of milk he can possibly add to this pail.

输入格式

The first, and only line of input, contains XX, YY, and MM, separated by spaces.

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

17 25 77
76
In this example, FJ fills the pail of size 17 three times and the pail of size
25 once, accumulating a total of 76 units of milk.
Problem credits: Brian Dean