公式
B - Broken Rounding 解説 by physics0523
\(10^k\) の位以下を四捨五入する賢明な方法を考えてみましょう。
まず、 \(10^k\) の位以下を四捨五入する際に、 \(10^{k-1}\) の位以下は気にしなくてよいことが分かります。
理由: \(10^k\) の位が \(4\) 以下ならば切り捨て、 \(5\) 以上ならば切り上げとなるからです。(メモ: 問題文の四捨五入の定義は一般的なそれと一致します。)
そこで、 \(X\) の \(10^k\) の位以下を四捨五入する際に、次の手順が成り立ちます。
- まず、 \(X\) を \(10^k\) で割る。(小数点以下切り捨て)
- これにより、 \(10^k\) の位が \(1\) の位となり、 \(10^{k-1}\) の位以下の情報については一旦失われます。
- \(X\) の \(1\) の位を \(m\) ( \(=X\) を \(10\) で割った余り) とします。
- もし \(m \le 4\) なら、 \(X\) から \(m\) を引いたのち \(X\) を \(10^k\) 倍する。 (この操作後、切り捨てが実現します)
- そうでない ( \(m \ge 5\) ) なら、 \(X\) に \(10-m\) を足したのち \(X\) を \(10^k\) 倍する。 (この操作後、切り上げが実現します)
- 以上の操作の双方で、操作後に \(X\) の \(10^k\) の位以下がすべて \(0\) になることに留意してください。
これを実装すればこの問題に正解できます。なお、以上の操作は全て整数型で完結させることができます。
実装例(C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
long long x,k;
cin >> x >> k;
long long pow10=1;
for(long long i=0;i<k;i++){
x/=pow10;
long long m=(x%10);
if(m<=4){x-=m;}
else{x+=(10-m);}
x*=pow10;
pow10*=10;
}
cout << x << "\n";
return 0;
}
投稿日時:
最終更新: