Codeforces #164 div2
本選までにTopcoderとCodeforces両方Div1上がれたらしい。けどすぐ落ちそう。
A. やる
int n, ans; int h[50], a[50]; int main(){ cin >> n; rep(i, n) cin >> h[i] >> a[i]; rep(i, n){ rep(j, n){ if(i == j) continue; if(h[i] == a[j]) ans++; } } cout << ans << endl; return 0; }
B. ちょっと考えるとわかる
int n; ll ans; int main(){ cin >> n; for(int i = 1; i <= n; i++) ans += i * (n - i); ans += n; cout << ans << endl; return 0; }
C. 自明にx座標かy座標が同じところには一つ置けないので、斜めに並べた時より多く並べることはできないのがわかる。
int n, m; int main(){ cin >> n >> m; if(n == m){ cout << n + 1 << endl; rep(i, n + 1) cout << n - i << ' ' << i << endl; return 0; } if(n > m){ cout << m + 1 << endl;; for(int i = 0; i <= m; i++) cout << 1 + i << ' ' << i << endl; return 0; } if(n < m){ cout << n + 1 << endl; for(int i = 0; i <= n; i++) cout << i << ' ' << m - i << endl; } return 0; }
E. 適当にソートしてdpすればいいのかな〜とか思うがわからなかった。頭わるい。
D. 図が怖くて諦めた
追記:
editorialを読んだ。Eやっぱりソートして累積和みたいなの使ってやるとできるのか...こういうのでソートするのPKUとかで見た気もするなあ
実装軽いしこういうの好き。
int n; double ans; double rui; struct song{ double poss; int per, len; }; bool operator<(const song& p, const song& q){ return p.poss > q.poss; } song k[500010]; int main(){ scanf("%d", &n); rep(i, n){ scanf("%d %d", &k[i].len, &k[i].per); if(k[i].per != 100) k[i].poss = k[i].len * k[i].per / (double)(100 - k[i].per); else k[i].poss = 10000000; } sort(k, k + n); rep(i, n){ ans += (double)k[i].len; ans += rui * (double)(100 - k[i].per) / 100.0; rui += (double)k[i].len * (double)k[i].per / 100.0; } printf("%.14lf\n", ans); return 0; }