高級程式測驗

[stu6707]

我不知道 @@ 剛運形時電腦還可以操作，過了十幾分鐘後就不行了，CPU被吃掉了90%

點個瀏覽器都要1,2分鐘，再等個1,2分鐘網頁才開好....

[ETERNAL]

http://zh.wikipedia.org/wiki/NP%E5%AE%8C%E5%85%A8

NP hard 可能要從這邊下手去研究了 @@

[ETERNAL]

對了 網站上的C是不是有問題?

他的答案是
17576
0 12 13 23 27 34 41 48

但是我解出來都是
17391
0 8 13 23 27 36 41 48

價格比他的更低

[stu6707]

恩 超出我的認知了，完全看不懂 @@ 哈哈

網站
0 1 2 3 4 5 6 7
1 7 0 6 2 3 4 5

ET大
0 1 2 3 4 5 6 7
1 3 0 6 2 7 4 5

兩個方法都符合條件，不過網站給的較貴一些

看來是網站錯了 @@

[ETERNAL]

我下午改了一些邏輯

現在d可以0秒或1秒跑完

但是e還是一樣跑不出來 = =

這是我跑d的結果

need time : 0 秒
========================
21097
1 13 20 30 33 48 51 63 68 78
loop 次數 : 14917

[ETERNAL]

恩 超出我的認知了，完全看不懂 @@ 哈哈

網站
0 1 2 3 4 5 6 7
1 7 0 6 2 3 4 5

ET大
0 1 2 3 4 5 6 7
1 3 0 6 2 7 4 5

兩個方法都符合條件，不過網站給的較貴一些

看來是網站錯了 @@

我也看不懂,大概要數學系的人才能理解吧 哈哈

[stu6707]

唔.. 數學中為解決的問題.. 還有100萬美金耶 @@ 不過真是難理解阿..

剛想到一個可能解決發方，把價錢加起來，選出最少價錢的幾個組合，在判斷組合成不成立

不知可不可以在短時間內解完

[ETERNAL]

唔.. 數學中為解決的問題.. 還有100萬美金耶 @@ 不過真是難理解阿..

剛想到一個可能解決發方，把價錢加起來，選出最少價錢的幾個組合，在判斷組合成不成立

不知可不可以在短時間內解完

你可以試試看阿

我也在想其他解決方法 @@

[stu6707]

要等一段時間了 @@ 這星期五有essay要交，下星期有2篇作業要交，考試又快要到了.....

[ETERNAL]

要等一段時間了 @@ 這星期五有essay要交，下星期有2篇作業要交，考試又快要到了.....

@@ 加油

我繼續奮戰..

[公子，請留步]

[ETERNAL]

e我跑出來了

need time : 519 秒
========================
25130
0 15 25 39 46 62 75 80 94 109 110 130
loop 次數 : 81425023

不過跟網站上的答案不一樣耶

25189
0 15 28 43 46 62 75 80 92 105 110 130

我的比網站上價格低了59元

網站上的答案是錯的嗎 @@?

[ETERNAL]

下午我寫信去問coderloop

對方回信給我了

Hi,

the solution you have found is not correct since it does not respect the following condition.

"Coderloop’s lab must acquire enough machinery to ensure it can create all the necessary compounds no matter what compounds are available on the market."

This means that, even with only one compound available must be possible to create all the other ones.
With your solution in the first test case (c.out) it is not possible to create C5 and C7 if they are not available (if they are available all the others but not C5 and C7).
Same thing for the testcase (e.out): it is not possible to create C2/C4 C3/C7 C9/C11 if they are not available (if C0 is the only available I cannot recreate all the other components).


See the representation below.


Best Regards,


Luca Bonmassar






Result c.out should be
17391
0 8 13 23 27 36 41 48


M0 C0 C1 2066
M8 C1 C3 2026
M13 C2 C0 2033
M23 C3 C6 2618
M27 C4 C2 2061
M36 C5 C7 2504
M41 C6 C4 2006
M48 C7 C5 2077

<===============================
C4 => C2 => C0 => C1 => C3 => C6

C5 <=> C7


Result e.out should be
25130
0 15 25 39 46 62 75 80 94 109 110 130


M0 C0 C1 2000
M15 C1 C5 2014
M25 C2 C4 2087
M39 C3 C7 2069
M46 C4 C2 2007
M62 C5 C8 2038
M75 C6 C10 2014
M80 C7 C3 2167
M94 C8 C6 2322
M109 C9 C11 2212
M110 C10 C0 2155
M130 C11 C9 2045

<==============================
C0 => C1 => C5 => C8 => C6 => C10

C2 <=> C4

C3 <=> C7

C9 <=> C11

看起來我理解的規則不對 @@

[stu6707]

哇 @@ 這樣又更花時間了... 要多做判斷了.......

[ETERNAL]

哇 @@ 這樣又更花時間了... 要多做判斷了.......

是阿 規則更複雜了,不過更省時間了喔

過濾掉不符合規則的組合,讓迴圈的次數變少

我現在e能跑出來了

need time : 261 秒
========================
25189
0 15 28 43 46 62 75 80 92 105 110 130
loop 次數 : 20140247

另外把if的前後順序對調一下,在時間上快了4倍

原本跑d需要16-17秒,現在只要3秒左右