CF Round #734 A - Polycarp and Coins


Tags:cpcodeforcesdiv3greedymath

問題

https://codeforces.com/contest/1551/problem/A

問題文

c1+2c2=nc_1 + 2 c_2 = n となるように c1,c2c_1, c_2 を定めてね。
ただし、 c1c2|c_1 - c_2| を最小化してね。

制約

  • 1t1041 \le t \le 10^4
  • 1n1091 \le n \le 10^9

サンプル

6
1000
30
1
32
1000000000
5
334 333
10 10
1 0
10 11
333333334 333333333
1 2

考察

1 と 2 を一緒にして、 3 として考える。
c3=n3c_3 = \lfloor \frac{n}{3} \rfloor とする。

  • nmod3=0n \bmod 3 = 0 のとき、 (c1,c2)=(c3,c3)(c_1, c_2) = (c_3, c_3)
  • nmod3=1n \bmod 3 = 1 のとき、 (c1,c2)=(c3+1,c3)(c_1, c_2) = (c_3 + 1, c_3)
  • nmod3=2n \bmod 3 = 2 のとき、 (c1,c2)=(c3,c3+1)(c_1, c_2) = (c_3, c_3 + 1)

これを出力すれば OK。

コード

https://codeforces.com/contest/1551/submission/123470098

void solve() {
  ll n;
  cin >> n;
  ll ans = n / 3;
  cout << ans + (n % 3 == 1) << ' ' << ans + (n % 3 == 2) << endl;
}