yukicoder No.146 試験監督(1)
問題概要
椅子に隣同士に座ることはできない。一つに机に椅子がいくつある椅子が、何個あるかが与えられるので、最大で何人座ることができるかを求める。
解法
2人掛けなら1人、3人掛けなら2人、4人掛けなら2人、5人掛けなら3人が最大で座れる数となる。よって、
cが偶数の時、その机に座れる人数は、(c/2)d
cが奇数の時、その机に座れる人数は、((c/2+1)d
となる。あとはこれを計算するだけだが、制約が大きいので、そのまま計算して、最後にmodを取るだけだと、オーバーフローしてしまう。modを頻繁に計算式にいれないとだめ。
pythonなら気にすることなく書くことができる。
ミス
完全に制約見ていなかった。オーバーフローは注意しよう。 下の様に、dをmod取らずに、かけるとオーバーフロー
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const ll mod = 1e9 + 7; int main(void){ ll n; cin >> n; ll ans = 0; rep(i, n){ ll c, d; cin >> c >> d; if(c % 2 == 0){ ans += (c / 2) % mod * d % mod; }else{ ans += (c / 2 + 1) % mod * d % mod; } ans %= mod; printf("%lld\n", ans); } printf("%lld\n", ans); return 0; }
コード
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const ll mod = 1e9 + 7; int main(void){ ll n; cin >> n; ll ans = 0; rep(i, n){ ll c, d; cin >> c >> d; if(c % 2 == 0){ ans += (c / 2) % mod * (d % mod) % mod; }else{ ans += (c / 2 + 1) % mod * (d % mod) % mod; } ans %= mod; } printf("%lld\n", ans); return 0; }
pythonはオーバーフローとか気にしなくていいから? 楽だね。
n = int(raw_input()) ans = 0 #mod = 10**9 + 7 mod = int(1e9 + 7) for i in range(n): c, d = map(int, raw_input().split()) if c % 2 == 0: ans += (c / 2) * d else: ans += (c / 2 + 1) * d ans %= mod print int(ans)