1/18 PKU

2432 Around the world

地球上の何点かにFJの友人がいる。それぞれの友人はある緯度の位置に住んでいる。いくつかの友人のペアの間に、その間を結ぶ航空便が存在する。航空便は、移動する緯度が少ない方の向きで移動する。友人1の場所から始めて、地球一周して元の場所に戻ってくる時（時計回りの移動と反時計回りの移動の長さが異なるとき）最低何回飛行機に乗る必要があるか。

BFS。１周したときは位置+360したりして区別する。

2553 The Bottom of a Graph

グラフVが与えられる。グラフ中の頂点vで、「∀w∈V, (v→w)⇒(w→v)」なる頂点をすべて求めよ。

強連結成分分解して、文字通り「bottom」（その成分からは他の成分に辺が一切出ていない成分）を求めるとよい。

2584 T-Shirt Gumbo

Tシャツを選手に配布する。各選手ごとに、着られるサイズの範囲が決まっており、各サイズごとに枚数に限りがある。全選手がちょうどいいサイズのTシャツを1枚ずつ得られるかどうか判定せよ。

3282 Ferry Loading IV

フェリーが壊れて修理してたら車の列ができてた。フェリーには車を１列しか搭載できず、車の長さの和がフェリーの長さの和以下にならないといけない。フェリーは左岸と右岸を往復し、先頭の車から順に詰め込めるだけ詰めて、川をわたり、反対岸で車を下ろしてまた詰め込むということを繰り返す。何回フェリーは川を渡る必要があるか。

やるだけ