P4416 [COCI 2017/2018 #1] Plahte

Little Donald decided to wash all N of his white sheets one day. After washing them, he put them to dry on the ground in his backyard. Donald placed the sheets so that ** none of them touch on the tips or the sides and that none of their sides intersect​**, but it is possible that he placed smaller sheets on top of bigger ones, or that a sheet is completely covering another sheet. After doing this, Donald went to bed. Donald’s friend Kim somehow got the information that Donald is drying his sheets and decided to mess with him. He found a paintball gun from his father in the attic. Along with the gun, there were M paintball balls in different colours, but it is possible that there were more balls having the same colour. As soon as Donald fell asleep, Kim walked into his backyard and started shooting the sheets with his paintball gun. We all know that sheets bleed, so when Kim shoots the topmost sheet, that sheet would bleed the color of the ball down to all of the sheets beneath it. After Kim used all the balls, he happily left Donald’s backyard. When Donald woke up and went to get his sheets, shock ensued. On most of Donald’s sheets, there was a number of new colours. Since Donald is very interested in correct data, and he’s in shock and not able to think, he is asking you to tell him the number of new colours on each sheet. We can represent Donald’s backyard as an infinite coordinate system, and the sheets as rectangles parallel to the coordinate axes. Kim’s shots can be represented as points in that system. Please note: it is possible that Kim’s shot missed all the sheets, but coordinates of each shot are unique.

无

无