TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

28.6% (2/7)

Submission's AC Ratio

14.3% (3/21)

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$的0-1 字串,若第$i$列的第$j$個字元為1,代表第i 天的便當包含了第$j$道菜。
註:因目前TIOJ不支援連續給分,故若輸出的$N \neq N_{100}$則無法得到任何分數

Sample Input

5 3 2 5 10

Sample Output

5
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$分。
子任務分數輸入限制
0 3 $\small m = 5, k = 3, d = 2, N_{50} = 5, N_{100} = 10$
1 6 $\small m = 8, k = 5, d = 3, N_{50} = 7, N_{100} = 8$
2 10 $\small m = 20, k = 12, d = 7, N_{50} = 12, N_{100} = 16$
3 12$\small m = 64, k = 32, d = 16, N_{50} = 1, N_{100} = 125$
4 13 $\small m = 65, k = 32, d = 17, N_{50} = 50, N_{100} = 125$
5 13 $\small m = 49, k = 7, d = 3, N_{50} = 1200, N_{100} = 2401$
6 14 $\small m = 121, k = 11, d = 4, N_{50} = 3600, N_{100} = 161051$
7 14 $\small m = 1369, k = 37, d = 2, N_{50} = 7200, N_{100} = 50653$
8 15 $\small m = 49, k = 7, d = 5, N_{50} = 14400, N_{100} = 117649$

Problem Source

題目取自2019 TOI選訓第三次模擬考pD
Problem set by oToToT, Utaha, Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 3
For Testdata: 1 ~ 1, Score: 6
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 12
For Testdata: 4 ~ 4, Score: 13
For Testdata: 5 ~ 5, Score: 13
For Testdata: 6 ~ 6, Score: 14
For Testdata: 7 ~ 7, Score: 14
For Testdata: 8 ~ 8, Score: 15
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 12000 1048576 262144
1 12000 1048576 262144
2 12000 1048576 262144
3 12000 1048576 262144
4 12000 1048576 262144
5 12000 1048576 262144
6 12000 1048576 262144
7 12000 1048576 262144
8 12000 1048576 262144