高級程式測驗

[ETERNAL]

題目蠻難的喔

我也有給涅魂看過,也還沒解出來

連結是英文原來的題目,Test cases裡面有答案,可以下載回來看
http://www.coderloop.com/puzzles/chemicals

附件是中文翻譯

飲料.docx

飲料

(12.6 KiB) 被下載 1695 次

主要是考驗邏輯方面

看不懂題目意思的話可以隨時問我

在coderloop的難度等級
optimization x 9 (優化× 9)
algorithm x 10 (算法× 10)
programming x 3 (編程× 3)
set theory x 8 (集理論× 8 )

[ETERNAL]

我還是先解說一下整個意思好了

給你一份資料,資料結構是這樣

代碼: 選擇全部

<machine name>  <orig compound>  <new compound>  <price>
M0   C0   C2  2243
M1   C0   C4  2949
M2   C0   C5  2596
M3   C1   C0  2902
M4   C1   C3  2429
M5   C1   C4  2251
M6   C2   C1  2042
M7   C2   C5  2443
M8   C3   C0  2974
M9   C3   C5  2907
M10   C4   C1  2898
M11   C4   C2  2057
M12   C4   C5  2388
M13   C5   C0  2145
M14   C5   C1  2823
M15   C5   C4  2640

這一份資料在<orig compound>部份從C0~C5
<new compound>也是一樣從C0~C5
<machine name>是設備,每台的設備<price>(價格)都不同,放入orig compound後,產出的new compound也不同

現在要求是這樣:
1.找出一組設備,這組設備都能對應C0~C5的<orig compound>
2.承上面,這組設備還要能產生C0~C5的<new compound>
3.承上面,放入任何一個<orig compound>,都能做出全部的<new compound>,舉例:我放入C0<orig compound>,能夠做出C0~C5的<new compound>
4.這組設備的組合,加總起來價格,必須是最便宜的,價格最低

下面這是答案

代碼: 選擇全部

14529
1 4 6 9 11 13

14529 是價格
1 4 6 9 11 13 是設備
你可以對照題目,看一下我的解說就知道規則了

[stu6707]

題目是要用最低的價錢來買可以製作出所有compounds的machines combination嗎?

[stu6707]

喔喔 了解了 @@ 看來很消耗腦力..

[ETERNAL]

題目是要用最低的價錢來買可以製作出所有compounds的machines combination嗎?

是的 要組合出能製作任何compounds,且價錢是最低的

[stu6707]

現在卡在怎麼排列出組合.. 如果不管是否重複input compound，case 1組合有16X15X14X13X12....... 囧

一定要判斷input compound是否重複，不然會跑好久 =.=

[ETERNAL]

哈哈 這是考驗邏輯,以及腦力的題目

我花了兩天,也沒完整做出來

目前我這邊算出幾種組合

A1 A2 A3
B1 B2 B3
C1 C2 C3

可以算出
A1 -> B1 -> C1 (需要多少價格)
A1 -> B1 -> C2 (需要多少價格)
A1 -> B1 -> C3 (需要多少價格)

[stu6707]

哈 算出testcase a 了~

不過代碼很僵硬.. 只能算出6種compounds.. 在多就不行了

努力把代碼彈性化



附上代碼
想了10分鐘.. 想不出方法可以處理n個compounds，只能處理6個compounds OTL

代碼: 選擇全部

<?
$f=file("./input.txt");
$st_no=99999;
$ini_no=0;
foreach($f as $value)
{
   $value=trim($value);
   $value=preg_replace('/\s(?=\s)/','',$value);
   $value=preg_replace('/[\n\r\t]/',' ',$value);
   $values=explode(" ",$value);
   $no=str_replace("C","",trim($values[1]));
   if($no <= $st_no) $st_no=$no;
   if(!is_array(${m.$no}))
   {
      ${m.$no}=array();
   }
   ${m.$no}[]=array(0=>str_replace("M","",trim($values[0])),1=>$no,2=>str_replace("C","",trim($values[2])),3=>trim($values[3]));
   if($no <= $ini_no) $st_com_no=count(${m.$no});
}

$final_comb=array();
$comp_2=array();
for($i=0;$i<$st_com_no;$i++)
{
   $comp_2[${m.$st_no}[$i][2]]=1;
   for($j=0;$j<count(${m.($st_no+1)});$j++)
   {
      if(array_key_exists(${m.($st_no+1)}[$j][2],$comp_2))
      {
         continue;
      }else
      {
         $comp_2[${m.($st_no+1)}[$j][2]]=1;
      }
      for($k=0;$k<count(${m.($st_no+2)});$k++)
      {
         if(array_key_exists(${m.($st_no+2)}[$k][2],$comp_2))
         {
            continue;
         }else
         {
            $comp_2[${m.($st_no+2)}[$k][2]]=1;
         }
         for($l=0;$l<count(${m.($st_no+3)});$l++)
         {
            if(array_key_exists(${m.($st_no+3)}[$l][2],$comp_2))
            {
               continue;
            }else
            {
               $comp_2[${m.($st_no+3)}[$l][2]]=1;
            }
            for($n=0;$n<count(${m.($st_no+4)});$n++)
            {
               if(array_key_exists(${m.($st_no+4)}[$n][2],$comp_2))
               {
                  continue;
               }else
               {
                  $comp_2[${m.($st_no+4)}[$n][2]]=1;
               }
               for($o=0;$o<count(${m.($st_no+5)});$o++)
               {
                  if(array_key_exists(${m.($st_no+5)}[$o][2],$comp_2))
                  {
                     continue;
                  }else
                  {
                     $cost=${m.$st_no}[$i][3]+${m.($st_no+1)}[$j][3]+${m.($st_no+2)}[$k][3]+${m.($st_no+3)}[$l][3]+${m.($st_no+4)}[$n][3]+${m.($st_no+5)}[$o][3];
                     $machine=${m.$st_no}[$i][0].','.${m.($st_no+1)}[$j][0].','.${m.($st_no+2)}[$k][0].','.${m.($st_no+3)}[$l][0].','.${m.($st_no+4)}[$n][0].','.${m.($st_no+5)}[$o][0];
                     $final_comb[$cost]=$machine;
                  }
               }
               unset($comp_2[${m.($st_no+4)}[$n][2]]);
            }
            unset($comp_2[${m.($st_no+3)}[$l][2]]);
         }
         unset($comp_2[${m.($st_no+2)}[$k][2]]);
      }
      unset($comp_2[${m.($st_no+1)}[$j][2]]);
   }
   unset($comp_2[${m.$st_no}[$i][2]]);
}

ksort($final_comb);
echo print_r($final_comb);
?>

[ETERNAL]

呵呵 a我這邊也有過關

目前卡在b

[stu6707]

剛試了b也可以過關，其它也是可以過關，不過需要多套幾個for迴圈

不過這應該不算是完全過關，完圈過關應該是不管compounds有幾種，不修改程式碼都能找出optimal combination

這就很難了 @@

[ETERNAL]

剛試了b也可以過關，其它也是可以過關，不過需要多套幾個for迴圈

不過這應該不算是完全過關，完圈過關應該是不管compounds有幾種，不修改程式碼都能找出optimal combination

這就很難了 @@

哇 比我利害了

是你貼的那個程式能跑出來??

[stu6707]

對阿 不過只能跑出6種compounds，在多compounds就要在套幾層for迴圈

我寫的是有幾種compounds就要套幾層for迴圈

像testcase g就需要套16層............

缺陷是需要一直修改程式碼



哈 把代碼擴充到16層for迴圈，果然完美的超時30秒 囧



加上set_time_limit(0);
電腦當機.................................

[ETERNAL]

對阿 不過只能跑出6種compounds，在多compounds就要在套幾層for迴圈

我寫的是有幾種compounds就要套幾層for迴圈

像testcase g就需要套16層............

缺陷是需要一直修改程式碼



哈 把代碼擴充到16層for迴圈，果然完美的超時30秒 囧



加上set_time_limit(0);
電腦當機.................................

呵呵 那需要改進啦

不過還是比我好

我是用while來寫,雖然可以執行多數層,但跑出來的結果不正確 哈

[stu6707]

跑了1個小時還是沒算完...... OTL

看來需要想新辦法了...



16層迴圈算testcase h需要執行146,620,948,539,985,920...次..... 14京

雖然這方法沒錯，可以算出正確答案，不過花費的時間....

[ETERNAL]

你的程式我測試有問題喔

代碼: 選擇全部

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 13

Notice: Undefined variable: m1 in D:\web\web\test_1.php on line 13

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 15

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 17

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 13

Notice: Undefined variable: m2 in D:\web\web\test_1.php on line 13

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 15

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 17

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 13

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 17

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 13

Notice: Undefined variable: m3 in D:\web\web\test_1.php on line 13

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 15

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 17

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 13

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 17

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 13

Notice: Use of undefined constant m - assumed 'm' in D:\web\web\test_1.php on line 17

Notice: Undefined variable: st_com_no in D:\web\web\test_1.php on line 23
Array ( ) 1


會出現這樣的訊息

而且最前面的<? 沒有php
在php5以上的環境沒辦法執行