AtCoderログ：0072 - 三井住友信託銀行プログラミングコンテスト2019 B

問題

問題文

高橋君は ABC 洋菓子店でアップルパイをひとつ買い、そのとき $N$ 円を支払ったことを覚えています。
この店で食料品を購入する際には $8$ パーセントの消費税が課されます。すなわち、税抜価格 $X$ 円のアップルパイを買う際には $X \times 1.08$ 円 (小数点以下切り捨て) を支払わなければなりません。
高橋君はアップルパイの税抜価格 $X$ を忘れてしまい、これを知りたくなりました。$N$ を入力として $X$ を求めるプログラムを書いてください。なお、$X$ は整数とします。
ただし、考えられる税抜価格が複数存在する場合はそのうちのいずれか $1$ つを求めてください。また、高橋君が支払った金額 $N$ を覚え間違えている可能性もあるので、アップルパイの税抜価格として考えられるものが存在しない場合はその旨を報告してください。

制約

・$1 \le N \le 50000$
・$N$ は整数

収録されている問題セット

• [BfB-E](AtCoder Problems Boot camp for beginners Easy 100) #004

回答

回答1 (AC)

アップルパイの値段 $X$ 円は支払金額 $X$ 円よりも少なく、$N$ の範囲は $1 \le N \le 50000$ となっているので、$X$ を $1$ から $50000$ までループを回すことで、アップルパイの値段を求めることができます。ただし、答えがない場合を想定する必要があります。コードは以下になりました。

計算量は $O(X)$ なので効率は良くありませんが、処理回数は $50000=5 \times 10^4$ 回程度なので、十分に処理可能です。

sumitb2019b-1.cpp

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

int main() {
  int n;
  cin >> n;

  string answer = ":(";
  for ( int x=1; x<=50000; x++ ) {
    if ( floor(x*1.08)==n ) {
      answer = to_string(x);
    }
  }

  cout << answer << endl;
}

回答2 (AC)

繰り返しをしない方法を考えます。支払金額 $N$ は、値段 $X$ を $1.08$ 倍して小数点以下を切り捨てた値なので、$N = \lfloor 1.08X \rfloor$ と表すことが出来ます。従って、$1.08X$ は(小数点以下を切り捨てた値なので)$N$ 以上 $N+1$ 未満です。つまり $\frac{N}{1.08} \le X < \frac{N+1}{1.08}$ となっているはずです。
このとき左辺の小数点を切り上げた $\lceil \frac{N}{1.08} \rceil$ は $X$ の値の候補になっているので、この値段が右辺より小さければ、それを $X$ として出力すれば良いでしょう。コードは以下になりました。このコードでは繰り返し処理を用いていないので、計算量は $O(1)$ となります。

sumitb2019b-2.cpp

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

int main() {
  int n;
  cin >> n;

  if ( ceil(n/1.08)<(n+1)/1.08 ) {
    cout << ceil(n/1.08) << endl;
  } else {
    cout << ":(" << endl;
  }
}

調べたこと

AtCoder の解説 → ユーザ解説

回答1と同じ方針でした。

AtCoder の解説 → コンテスト全体の解説

回答1,2と同じ方針でした。

リンク

前後の記事

• 前の記事 → AtCoderログ：0071 - ABC 091 B
• 次の記事 → AtCoderログ：0073 - ABC 081 C