TopCoder

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

User's AC Ratio

27.3% (3/11)

Submission's AC Ratio

11.4% (4/35)

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$分。

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 12000 1048576 262144 1
1 12000 1048576 262144 2
2 12000 1048576 262144 3
3 12000 1048576 262144 4
4 12000 1048576 262144 5
5 12000 1048576 262144 6
6 12000 1048576 262144 7
7 12000 1048576 262144 8
8 12000 1048576 262144 9