Atcoder Petrozavodsk Contest 001
A - Two Integers
XがYの倍数でなければXが答えになる.
#include <iostream> using namespace std; int main(void) { int x, y; cin >> x >> y; if(x % y == 0) { cout << -1 << endl; return 0; } cout << x << endl; }
B - Two Arrays
操作回数は(bの総和) - (aの総和)回.
ここまではコンテスト中にわかった.
1. a[i] > b[i]のとき少なくともb[i]をa[i] - b[i]回1増やす必要がある.
2. a[i] < b[i]のとき少なくともa[i]を(b[i] - a[i] + 1) / 2 (小数点以下切り捨て)回2増やす必要がある.
上の2つが(editorialによると)必要十分らしい.
02/07追記: (bの総和), (aの総和), 1増やす回数, 2増やす回数はlong long intでなければいけないのでコードを修正.
#include <iostream> using namespace std; int main(void) { int n; cin >> n; int a[n], b[n]; for(int i = 0; i < n; i++) { cin >> a[i]; } for(int i = 0; i < n; i++) { cin >> b[i]; } long long int sum_a = 0, sum_b = 0; for(int i = 0; i < n; i++) { sum_a += a[i]; sum_b += b[i]; } long long int t = sum_b - sum_a; long long int t_a = 0; long long int t_b = 0; for(int i = 0; i < n; i++) { if(a[i] < b[i]) { t_a += (b[i] - a[i] + 1) / 2; } else if(a[i] > b[i]) { t_b += a[i] - b[i]; } } if(t >= t_a && t >= t_b) { cout << "Yes" << endl; } else { cout << "No" << endl; } }