B - Glass and Mug Editorial by en_translator Editorial for printing
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: