Official

B - Glass and Mug Editorial by en_translator


Let \(x\) and \(y\) be the amount of water in the glass and mug in milliliters, respectively, and consider how these values change by an operation.

If \(x=G\), set \(x=0\). Otherwise, if \(y=0\), set \(y=M\).
Otherwise, you move some water from the mug to the glass; the amount of water to be moved is the smaller of \(y\) milliliters, which is the amount of water in the mug, and \((G-x)\) milliliters, which is the amount of water required to fill the glass. Therefore, it is sufficient to let \(z=\min(y,G-x)\), increase \(x\) by \(z\), and decrease \(y\) by \(z\).

All that left is to start with \(x=0\) and \(y=0\), and find the transition by the \(1\)-st, \(2\)-nd, \(\ldots\), and \(K\)-th operations.
Since \(K \leq 100\), the simulation can be done fast enough.
Thus, the problem has been solved.

Sample code in C++:

#include <bits/stdc++.h>
using namespace std;

int main() {
	int k,g,m;
	int x=0,y=0,z;
	cin>>k>>g>>m;
	for(int i=0;i<k;i++){
		if (x==g)x=0;
		else if(y==0)y=m;
		else{
			z=min(g-x,y);
			x+=z,y-=z;
		}
	}
	cout<<x<<" "<<y<<endl;
	return 0;
}

Sample code in Python:

k,g,m=map(int, input().split())
x,y=0,0

for i in range(k):
    if x==g:
      x=0
    elif y==0:
      y=m
    else:
      z=min(y,g-x)
      x,y=x+z,y-z

print(str(x)+" "+str(y))

posted:
last update: