ZIO 2012:玩具套装
一套玩具包含显示从1到9之间的数字的块。有大量的块显示每个数字，而显示相同数字的块是难以区分的。我们要检查在一个序列中排列块的不同方法的数目，这样显示的数字加起来就等于一个固定的和。例如，假设之和为4，有8种不同的安排：
1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
4.
行按字典顺序排列(也就是说，如果它们在字典中列出，它们就会出现)。在以下每一种情况下，您都会得到所需的和S和一个数字K。当所有与S相加的安排如前所述时，您必须写下Kth线。例如，如果S是4，K是5，则答案是21，1。请记住，S可能很大，但是块上的数字仅为1到9。
(a) S= 9，K= 156
(b) S= 11，K= 881
(c) S= 14，K= 4583
所以基本上每个案件(1111,112等)在数学中也被称为一个数字的分区，虽然112和121是相同的分区(在数学中)，但在这里我必须考虑它们不同的分区。在这种情况下，我们的考虑是不同的。我尝试通过寻找一个常见的模式来强制执行，如果我们考虑一个数组par[]，它由9的所有分区(问题的第一部分)组成，按字典顺序排列，par = 111111111，par1 = 11111112 par2 - par3将包含两个由11111121和1111113组成的术语。如果我们仔细观察最后两个数字，我们会注意到它们是3的分区。因此，基本上，以1开头的除法将遵循1+1 ( 2的分区)+2(3的分区)+4(4的分区)的顺序，以2的幂增加，直到par127 = 18，no。对于8的分区，我们注意到，在添加它们时，我们得到了2的幂。然而，当par128 = 21111111时，我似乎被困在了计算第156号位置上，而且我无法在我的方法中进一步移动。最受欢迎的是重复关系或伪码。作为整数的答案可以在网上找到，但不包括算法。请帮帮我。
来源：http://www.iarcs.org.in/inoi/2012/zio2012/zio2012-qpaper.pdf
解决方案：http://www.iarcs.org.in/inoi/2012/zio2012/zio2012-solutions.pdf
回答 1
Stack Overflow用户
发布于 2016-11-19 06:26:06
暗示：
partitions of 1
1 the number itself
partitions of 2
11 1 followed by partitions of 1
2 the number itself
partitions of 3
111 1 followed by partitions of 2
12 .
21 2 followed by partitions of 1
3 the number itself
partitions of 4
1111 1 followed by partitions of 3
112 .
121 .
13 .
211 2 followed by partitions of 2
22 .
31 3 followed by partitions of 1
4 the number itself
partitions of 5
11111 1 followed by partitions of 4
1112 .
1121 .
113 .
1211 .
122 .
131 .
14 .
2111 2 followed by partitions of 3
212 .
221 .
23 .
311 3 followed by partitions of 2
32 .
41 4 followed by partitions of 1
5 the number itselfhttps://stackoverflow.com/questions/40689582
复制相似问题
腾讯云开发者
