KogCoder Code Contest #2 A (AOJ-1149-"Cut the Cake" or "ケーキカット")

問題

Cut the Cake | Aizu Online Judgeを参照

 

問題文の中で特に注意すること(自身が解く際に見落としていたこと)は以下のルール

  • 先に生まれたピースほど識別番号が小さい.
  • 1回のカットで生まれる二つのピースについては,(上から見た)面積の小さい方が識別番号も小さい.

 

考え方


テストケースの1つ目(上の方で図が示されている)を数字等を入れ詳しくした図を以下に示す.

3 5 6

カット回数3回

幅5,奥行き6

f:id:abc10946:20170814232234p:plain

 1 18

識別番号1のピース(一番最初なので識別番号は特に関係はない)に北西から時計回りに18進んだ地点を起点にしてカット.

f:id:abc10946:20170814232240p:plain

カットした後の識別番号は以下のようになる.

これは1回のカットで生まれる2つのピースは、面積の小さいほうが識別番号が小さくなるというルールに従う.

f:id:abc10946:20170814232245p:plain

2 19

識別番号2のピースに北西から時計回りに19進んだ地点を起点にしてカット.

このときピースの外周1周よりも時計回りに進む距離が長いが何周もすることができるので1を起点にカットする.

f:id:abc10946:20170814232304p:plain

2回目のカットのあと識別番号は以下のようになる.

識別番号は先に生まれたピースほど小さいというルールに従う必要がある.

f:id:abc10946:20170814232308p:plain

1 2

識別番号1のピースに北西から時計回りに2進んだ地点を起点にしてカット.

その後の識別番号は以下のようになる.

識別番号は先に生まれたピースほど小さいというルールに従う必要がある.

これを考慮しないでコードを書いていた結果、小一時間悩んでいたため強調してる.

f:id:abc10946:20170814232311p:plain

これにより大方のイメージは捉えられたと思われる.

 

プログラム

コードの大方の解説.

幅、奥行きを簡単に扱えるようなクラスか構造体またはpairをusingでシノニムを作るなどする.

ピースを簡単に管理するために上で定義したRectクラスを使いそれの配列を作る.

Siがピースを1周以上するときはs%((w+d)*2)で無駄な周回分を省く.

時計回りに北、東、南、西と順番に回っていくので 、それぞれの処理をする.

 

KogCoder-Code-Contest-#2