iT邦幫忙

1

【題解】google code jam 程式競賽 Round1-A 第二題

SouthRa 1 月前5300 瀏覽

之前看到有大大在分享qualify round的題目
想說也來分享一下round1的題目和題解~

google code jam是每年一次的google紀念衣爭奪戰!
在Round2拿到全世界前1000名的人都可以拿到一件使你走路有風的google襯衫>w<

Round1分成三個sub round,每次取1000個人晉級
上週的roundA能否晉級的分界線就差不多在於第二題的大測有沒有解出來
因此跟大家分享一下第二題的作法~

連結:
https://code.google.com/codejam/contest/5304486/dashboard#s=p1

題目:
給予一個料理的食譜,此料理由N種食材組合而成。
給予R1 R2 ... RN,代表一份料理每一種食材所需要的分量(公克)
現在你每一種食材都有P包,每一包的重量都不盡相同
將這N種食材各取1包,可以組合成一個製作K份料理的大補帖,只要每包的重量都是所需份量的K * 0.9倍至K * 1.1倍之間,就是合法的組合
請問最多可以包成幾包大補帖?

做法:

  • 每一包食材包,找出他所對應的份數的區間,例如洋蔥一份70克,那麼1500克的洋蔥可以當成20份、21份、22份、23份
  • 將同種類的材料包依照重量大小排序好
  • 選一種食材當起始點,對於其他食材做搜索,能選小包就盡量小包,每次選擇都會縮小可行區間,若再也沒有符合的選擇,則回溯到上一層選較大包的
  • 記得用一個boolean陣列紀錄該包食材是否已經在上一次包大補帖用掉了
  • 看起來像DFS,但因為每次都能夠快速決定是否合法,因此複雜度能保證在P * N左右

希望有幫到人唷>W<


2 則留言

0
海綿寶寶
iT邦超人 1 級 ‧ 1 月前

我沒通過 Qualification/images/emoticon/emoticon52.gif
只怪自己少年不努力,DP沒學好

好分享
給你拍拍手
繼續前進下一Round
/images/emoticon/emoticon08.gif/images/emoticon/emoticon08.gif/images/emoticon/emoticon08.gif

SouthRa iT邦新手 5 級 ‧ 1 月前 檢舉

謝謝你呦>w<
明年再接再厲

海綿寶寶 iT邦超人 1 級 ‧ 1 月前 檢舉

我是參加好玩的
為了讓腦筋活動一下
DP不會就是不會
明年我想還是不會
/images/emoticon/emoticon10.gif

0
bizpro
iT邦大師 1 級 ‧ 1 月前

關於"請問最多可以包成幾包大補帖?", 這並非Google所問的問題, 依據:

A kit consists of exactly one package of each ingredient, and a label with the integer number of servings of ratatouille that the kit makes. 
...
What is the largest number of kits that you can form? Note that you are not required to maximize the total number of servings of ratatouille formed. 

Google問的是kit(成套), 而不是包成多少份(servings):
以樣本三為例, 此:
2 2
50 100
450 449
1100 1101
看起來重量多, 但只能成ㄧ套(kit):
因為(449,1101)違反90%和110%, 所以只能給消費者一套: (450,1100), 而消費者可以依(45,110)分為十份

邏輯先判斷是否在90%和110%之間, 不管能分多少份, 剔除不合格的, 再組合能成套的輸出.

看更多先前的回應...收起先前的回應...
SouthRa iT邦新手 5 級 ‧ 1 月前 檢舉

哈囉~
抱歉我的表達可能不太清楚QQ
我原意中的"一包"就是你的"一套"的意思
並不是在講"份"喔~

至於為甚麼要考慮份數,是因為要知道是在幾份的90%~110%阿
不知道這樣有沒有比較清楚?

海綿寶寶 iT邦超人 1 級 ‧ 1 月前 檢舉

因為題目本身就很複雜
為了怕誤會題意
所以我才不翻譯
直接轉貼原文
/images/emoticon/emoticon01.gif

bizpro iT邦大師 1 級 ‧ 1 月前 檢舉

題目是標準的美國大學數學考題的寫法, 為了題意清楚, 寫得落落長.
找出正確的kit的邏輯不難, 就是比較不同ingredients的在不同packages中的可能分配份數(reservings, 在90%~110%之間)的交集. 全部ingredients有交集的packages就成套(kit). 計算時餘數需為0.
但是還要排列出最多的kit數...

SouthRa iT邦新手 5 級 ‧ 1 月前 檢舉

對呀競賽題的敘述都會寫到讓人看到昏
(其實這套題組的第一題讓人看了更昏哈哈哈)
我原本以為直接幫翻譯會比較清楚
沒想到會因為kit跟searving翻成中文的套跟包等等造成更混淆QQ

如果有其他邦友看不懂我對題目的翻譯
可以去看bizpro的解釋唷
看懂題目後再去看我的做法應該會比較好懂~

我要留言

立即登入留言