[yukicoder] No. 846 メダル

2019年7月5日

問題

方針

天井関数

\[\lceil \dfrac{x}{y} \rceil = z\]

上記を満たす整数 \( x, y, z \) について、次の不等式が成り立ちます。

\begin{eqnarray}
z – 1 &<& \dfrac{x}{y} \leq z\\
y (z – 1) &<& x \leq yz
\end{eqnarray}

制約条件

\( N \) が満たすべき条件は、

\[ \lceil \dfrac{N}{P} \rceil = A \wedge \lceil \dfrac{N}{Q} \rceil – A= B \wedge \lceil \dfrac{N}{R}\rceil – (A + B)= C\]

よって、上式より、\( N \) の最小値を \( N_1 \) 、最大値を \( N_2 \) とすると、

\[ N_1 = \max (P(A – 1), Q * (A + B – 1), R * (A + B + C – 1)) + 1\]

\[ N_2 = \min (PA, Q * (A + B), R * (A + B + C))\]

となります。

コード

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


int main() {
  ll P, Q, R, A, B, C;
  cin >> P >> Q >> R >> A >> B >> C;
  
  ll nMin = max(P * (A - 1) + 1, max(Q * (A + B - 1) + 1, R * (A + B + C - 1) + 1));
  ll nMax = min(P * A, min(Q * (A + B), R * (A + B + C)));
 
  if (nMin > nMax) cout << "-1\n";
  else cout << nMin << " " << nMax << "\n";
  return 0;
}