发信人: styc(Frank!)
整理人: dynadino(2001-03-02 10:23:35), 站内信件
|
此题选自2001年广东省青少年信息学重点中学邀请赛。这项比赛已于2001年2月24、25日在中山大学举行。《裁剪布料》是25日进行的第二试第二题。本人也参加了这比赛。真是惭愧，这题一分没得。
解决此题关键在于找出简便的计算方法。一块布，不论大小，剪一下，就会变成两块。显然，如果最多可以叠L层的话，剪一下，剪开的布的数量就可以增加L块。因此，把MxN的布剪开需要剪的次数的理论最小值是[(MxN-1)/L]（符号[x]表示取不大于x的最大整数）。但是实际上，这个最小值并不一定能达到，因为当剪开的布的数量小于L时，剪一下至多只能使布的数量翻倍。分析至此，题目的解法已经很明了的。简述如下：
找一个整数E，使2^E<L<=2^(E+1)。再找一整数P，使LxP+2^(E+1)>MxN。那么P+E就是要剪的最少次数。
这就是第二个问题的解答。根据此法，可算出第一题的答案是16。
----
Hala Madrid! Hala Madrid!
A triunfar en buena lid, defendiendo tu color!
Hala Madrid! Hala Madrid! Hala Madrid!
Siempre te apoyo,
El Real Madrid Club de Fútbol que amo!
|
|