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: