2077 . 自助餐（Buffet）
TopCoder
Tags
Description
選訓營的同學每一天都要吃自助餐。每一天，餐廳裡面都提供了一模一樣的 $m$ 道菜可以選擇，但因為預算有限的關係，助教只能幫同學們挑選恰好 $k$ 道菜打包成一個便當。
為了讓同學能均衡攝取營養，助教決定對於任何 $m$ 道菜中的 $d+1$ 道菜 $(d + 1 \leq k)$ 組合，只能在選訓營舉辦期間出現在便當至多一次。為了能讓選訓營舉辦越多天越好，你決定要幫助教寫一支程式產生出盡量多的便當組合。
Input Format
輸入的第一列有五個正整數 $m, k, d, N_{50}, N_{100}$，其中 $m, k, d$ 之定義請參考問題敘述，而 $N_{50}$ 與 $N_{100}$ 之定義請參考評分說明。
Output Format
請於第一列輸出一個正整數 $N$，代表你輸出的便當數量。接下來的 $N$ 列，每一列都輸出一個長度恰好為 $m$ 的 01 字串，若第 $i$ 列的第 $j$ 個字元為 1，代表第 $i$ 天的便當包含了第 $j$ 道菜。
註：因目前TIOJ不支援連續給分，故若輸出的 $N \neq N_{100}$ 則無法得到任何分數
Sample Input 1
5 3 2 5 10
Sample Output 1
5
00111
01011
10011
10101
11100
00111
01011
10011
10101
11100
Hints
本題共有 $9$ 個子任務，條件限制如下所示。若你的輸出不滿足題目敘述之要求，則得分為 $0$。若你的輸出滿足題目敘述之要求，而該子任務所佔分數為 $X$，此時得分規則如下：
- 如果輸出的 $N$ 滿足 $N < N_{50}$ 或 $N > N_{100}$，那麼得分為 $0$。
- 如果輸出的 $N$ 滿足 $N_{50} \leq N < N_{100}$，那麼你將獲得 $(0.5 + 0.5 \frac{N-N_{50}}{N_{100}-N_{50}})X$ 分。
- 如果輸出的 $N = N_{100}$，那麼你可以獲得 $X$ 分。
Problem Source
題目取自2019 TOI選訓第三次模擬考pD
Problem set by oToToT, Utaha, Yihda Yol
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | $\small m = 5, k = 3, d = 2, N_{50} = 5, N_{100} = 10$ | 3 |
| 2 | 1 | $\small m = 8, k = 5, d = 3, N_{50} = 7, N_{100} = 8$ | 6 |
| 3 | 2 | $\small m = 20, k = 12, d = 7, N_{50} = 12, N_{100} = 16$ | 10 |
| 4 | 3 | $\small m = 64, k = 32, d = 16, N_{50} = 1, N_{100} = 125$ | 12 |
| 5 | 4 | $\small m = 65, k = 32, d = 17, N_{50} = 50, N_{100} = 125$ | 13 |
| 6 | 5 | $\small m = 49, k = 7, d = 3, N_{50} = 1200, N_{100} = 2401$ | 13 |
| 7 | 6 | $\small m = 121, k = 11, d = 4, N_{50} = 3600, N_{100} = 161051$ | 14 |
| 8 | 7 | $\small m = 1369, k = 37, d = 2, N_{50} = 7200, N_{100} = 50653$ | 14 |
| 9 | 8 | $\small m = 49, k = 7, d = 5, N_{50} = 14400, N_{100} = 117649$ | 15 |