竞赛题: 合并果子 etc.(做完一道 go on)

yarco1

既然已经顶了. 不好意思不发题目. go on...
来自w3china.org

1.给定一个正整数n, 则在n所有的分解式中, 求因子乘积最大的一个分解及此乘积.

PS: 这是我的翻译, 不太清楚. 举例说, n = 8时, 则8有如下分解式：8 = 8, 8 = 7 + 1 , 8 = 4 + 4 , 8 = 3 + 3 + 2, 8 = 2 + 2 + 2 + 2 直至 8 = 8个1的和，等等
那么，在这些分解式中，３*３*２ = 18最大，这就是所要求的结果．　对于n = 12,则应该是3*3*3*3 = 81.

yzc2002

原帖由 yarco1 于 2005-11-8 13:29 发表
既然已经顶了. 不好意思不发题目. go on...
来自w3china.org

这个太简单了,拆尽可能多的3
p=1;
while(n > 4)
{
    p *= 3;
    n -= 3;
}
p *= n;

yarco1

不会吧...

1. 
   
2. 第一章 胜利的逃亡
   
3. 
   
4. Time Limit:1s Memory Limit:32768k
   
5. Total Submit:368 Accepted:95
   
6. Problem
   
7. 
   
8. 来自异空的精灵族为这个世界带来了秩序。为了与不断侵犯的邪恶力量作战，万神殿选中了他们最强大的战士Prince与Gush作为他们的守护战神。他们在上百万年的时间里一丝不苟地履行着自己的职责，搜寻并摧毁一切能找到的恶魔。终于有一天在艾泽拉斯遭遇了两支从实体世界中获得了巨大能量的强大恶魔种族。兵败后他们被关在恶魔之都的地下监狱里。
   
9. 漫长的等待后终于获得了一个逃跑计划。这能够使两位战神跑到恶魔之都的传送点。然后一同回自己的世界。首先Gush沿着城市的街道跑到传送点。然后发送超声信号给Prince，告诉Prince应该跑到哪里。然后Prince沿着街道跑到相同地点，与Gush会合，接着秘密传送回自由的领地。
   
10. Gush穿着精灵族的铠甲行走，所以会引起路上恶魔的注意。所以Prince的行程不能与Gush相同。即Gush走过的街Prince不能再走。你需要计算从Gush离开监狱到Prince到达传送点的最短时间。假设发送消息不花费任何时间。
    
11. 
    
12. 简而言之：
    
13. 给你一个有权的无向图，找到两条最短的从S到T的路，使得每条街最多走了一次。输出他们最短的时间之和。
    
14. 
    
15. Input
    
16. 
    
17. 本题含有多组数据。每组数据开头为n (2<=n<=100)（街道交点的个数-即结点个数）。监狱在结点1，传送点在结点n。下一行为街道个数m。接着m行描述这m条街。每行有三个整型变量a b t，a b为这条街连接的两个结点号，t (1<=t<= 1000)为走过这条街道需要的时间。每条街连接两个不同的结点。每两个结点之间不会有多条街道。最后一组数据后为一个0。
    
18. Output
    
19. 
    
20. 对于每组数据输出从Gush离开监狱到Prince到达传送点的最短时间。如果无解则输出一行"Back to jail"。
    
21. Sample Input
    
22. 
    
23. 2
    
24. 1
    
25. 1 2 999
    
26. 3
    
27. 3
    
28. 1 3 10
    
29. 2 1 20
    
30. 3 2 50
    
31. 9
    
32. 12
    
33. 1 2 10
    
34. 1 3 10
    
35. 1 4 10
    
36. 2 5 10
    
37. 3 5 10
    
38. 4 5 10
    
39. 5 7 10
    
40. 6 7 10
    
41. 7 8 10
    
42. 6 9 10
    
43. 7 9 10
    
44. 8 9 10
    
45. 0
    
46. Sample Output
    
47. 
    
48. Back to jail
    
49. 80
    
50. Back to jail
    
51. Source
    
52. 
    
53. 同济大学程序设计大赛
    

复制代码

yarco1

原帖由 yzc2002 于 2005-11-8 13:36 发表

这个太简单了,拆尽可能多的3
p=1;
while(n > 4)
{
    p *= 3;
    n -= 3;
}
p *= n;

yum...a...你肯定做过acm
偶还没zixi看呢...
不过说得也是...
假如是5的话, 那么2*3>5

torrent

为什么把1个和2个和在一起消耗3的力气而不是1？

dbcat

Not hard..........
The problem is:
x(1)+x(2)+.....+x(m)=n
find the maximum of x(1)*x(2)*...*x(m)

If u know x(1)+x(2)+...+x(m)>=m*pow(x(1)*x(2)*...*x(m),1/m)
then the result is max((n/m)^m) (m=1...n);

A shell program can solve that:
for eg :n=12
echo "12"|seq 1 12 |xargs -i echo "(12/{})^{}" | bc -l | sort -n | tail -1
Result:81.

yarco1

原帖由 dbcat 于 2005-11-8 16:22 发表
Not hard..........
The problem is:
x(1)+x(2)+.....+x(m)=n
find the maximum of x(1)*x(2)*...*x(m)

If u know x(1)+x(2)+...+x(m)>=m*pow(x(1)*x(2)*...*x(m),1/m)
then the result is max((n/m)^m ...

恩...谢了...是不等式...
好象是高中的吧...晕...
有意思.

win_hate

原帖由 dbcat 于 2005-11-8 16:22 发表
Not hard..........
The problem is:
x(1)+x(2)+.....+x(m)=n
find the maximum of x(1)*x(2)*...*x(m)

If u know x(1)+x(2)+...+x(m)>=m*pow(x(1)*x(2)*...*x(m),1/m)
then the result is max((n/m)^m ...

我觉得这个解答不够好：

1、把均值不等式用在离散的情形，其正确性有必要作一定的说明。
2、如果 n 很大，就要试很多次。
3、当 n> 1 时，拆分方式应该为 3*k + r, r=4 或 2 或 0。 上述代码并没能体现出这一点

这个题目以前讨论过的。

yarco1

原帖由 win_hate 于 2005-11-9 10:04 发表
我觉得这个解答不够好：

1、把均值不等式用在离散的情形，其正确性有必要作一定的说明。
2、如果 n 很大，就要试很多次。
3、当 n> 1 时，拆分方式应该为 3*k + r, r=4 或 2 或 0。 上述代码并没能体 ...

恩...不过问题是: 这样子能给出一种数学论zheng的方式.
虽然就xiang你说的那样毕竟这解应该是整数.
问题是关于拆分, 我能够想xiang得出, 应该是3:
1. 当n足够大时, n应当被cai分得个数越多越好
2. cai分1, 不如cai分2, 不如cai分3
在这两条规律中妥协很容易得到正确答案. 但我想不是那么有说服力.
不能凭以3的cai分而让人xin fu 吧.

yzc2002

原帖由 yarco1 于 2005-11-9 13:31 发表


恩...不过问题是: 这样子能给出一种数学论zheng的方式.
虽然就xiang你说的那样毕竟这解应该是整数.
问题是关于拆分, 我能够想xiang得出, 应该是3:
1. 当n足够大时, n应当被cai分得个数越多越好
2. cai分1 ...

这个...你不会自己证明一下么?
设n=a_1+a_2+...+a_k是使乘积最大的拆分,则有:
(1)每个a_i都<=4
    因为若某个a_i >=5,则a_i = 3 + (a_i - 3),而3*(a_i-3)=a_i + (2*a_i - 9) >=a_i + (2 * 5 - 9) = a_i + 1 > a_i,所以拆分a_1, a_2...3, a_i - 3...a_k的拆分将比原来的还要大,矛盾
(2)不可能有两个以上的4存在
    因为4+4=3+3+2,而3*3*2=18 > 4*4=16
(3)不可能有3个以上的2存在
    因为2+2+2=3+3,而3*3 > 2*2*2
(4)不可能有1存在
    因为1*a < a + 1