9/23 PKU

1791 Paper Cutting

名刺を紙に印刷する。名刺を切り出すのに何回切断作業が必要か？

やるだけ

1228 Grandpa's Estate

凸多角形状の農地があって、周上に杭が打ってあり、そこにロープがかけられていた。ある日、ロープが外されて、杭もいくつかなくなっていた。今、農地の周を正確に判定できるか？

まず杭で凸包を生成する。ここで、凸包の辺上にある点も含めて生成する。凸包上のすべての辺について、辺上に(端点以外で)点が存在するなら答えはYES、さもなくばNOである。

1322 Chocolate

箱にC種類のチョコレートがそれぞれたくさん入っている。今、N個のチョコレートを箱から順番に取り出す。同じ種類のチョコレートが2つになったら両方食べる。その後、M個のチョコレートが残っている確率は？

DP。ただし普通にやると簡単にTLEするので、nが大きいときは勝手に小さくする（要求される精度が低いから）という変なコードを書いた。でも通った