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;
}