公式

D - Glass and Mug 解説 by mechanicalpenciI


グラスとマグカップにに入っている水の量をそれぞれ \(x\) ml, \(y\) mlとしたときに、\(1\) 回の操作で水の量がどのように変化するか考えます。

まず、\(x=G\) のとき、\(x=0\) に変更します。 そうでなく \(y=0\) ならば \(y=M\) に変更します。
上のいずれでもないとき、マグカップからグラスに水を移しますが、移す水の量はマグカップに入っている水の量 \(y\) mlとグラスを水で満たすために必要な水の量 \((G-x)\) ml のうち小さい方です。よって、\(z=\min(y,G-x)\) として \(x\)\(z\) 増加させ、\(y\)\(z\) 減少させれば良いです。

あとは、\(x=0\), \(y=0\) から始めて \(1,2,\ldots,K\) 回目の操作の後でどのように変化するかを順に求めていけば良いです。
\(K\leq 100\) なので十分高速にこのシミュレーションを行うことができます。
よってこの問題を解くことができました。

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;
}

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))

投稿日時:
最終更新: