之前看到有大大在分享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倍之間，就是合法的組合
請問最多可以包成幾包大補帖?
做法：
希望有幫到人唷>W<
我沒通過 Qualification
只怪自己少年不努力，DP沒學好
好分享
給你拍拍手
繼續前進下一Round
謝謝你呦>w<
明年再接再厲
我是參加好玩的
為了讓腦筋活動一下
DP不會就是不會
明年我想還是不會
關於"請問最多可以包成幾包大補帖?", 這並非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%之間, 不管能分多少份, 剔除不合格的, 再組合能成套的輸出.
哈囉~
抱歉我的表達可能不太清楚QQ
我原意中的"一包"就是你的"一套"的意思
並不是在講"份"喔~
至於為甚麼要考慮份數，是因為要知道是在幾份的90%~110%阿
不知道這樣有沒有比較清楚?
因為題目本身就很複雜
為了怕誤會題意
所以我才不翻譯
直接轉貼原文
題目是標準的美國大學數學考題的寫法, 為了題意清楚, 寫得落落長.
找出正確的kit的邏輯不難, 就是比較不同ingredients的在不同packages中的可能分配份數(reservings, 在90%~110%之間)的交集. 全部ingredients有交集的packages就成套(kit). 計算時餘數需為0.
但是還要排列出最多的kit數...
對呀競賽題的敘述都會寫到讓人看到昏
(其實這套題組的第一題讓人看了更昏哈哈哈)
我原本以為直接幫翻譯會比較清楚
沒想到會因為kit跟searving翻成中文的套跟包等等造成更混淆QQ
如果有其他邦友看不懂我對題目的翻譯
可以去看bizpro的解釋唷
看懂題目後再去看我的做法應該會比較好懂~
iThome鐵人賽
看影片追技術