貴育成了 $3N+1$ 位賽馬娘,編號由 $0$ 到 $3N$ 。
賽馬娘們有三種主要的營養來源:白飯、漢堡排、紅蘿蔔。
編號為 $i$ 的賽馬娘在每餐都必定會食用總共 $i$ 份的白米飯、漢堡排、紅蘿蔔,而且每種餐點都一定會食用整數份。
編號為 $i$ 的賽馬娘在時間 $t$ 時(這裡的時間是相對時間,所以 $t$ 可能為任意實數)的固有馬力為 $it$ 。
若在時間 $t$ 舉辦一場賽跑,每位賽馬娘都會在時間 $t$ 前預先吃飽(即,貴會讓編號 $i$ 的賽馬娘任意食用白米飯、漢堡排、紅蘿蔔再讓她在時間 $t$ 參賽)。
一位賽馬娘食用了 $i$ 份白米飯就會在她當前的固有馬力之上額外獲得 $f_i$ 大小的馬力。
一位賽馬娘食用了 $i$ 份漢堡排就會在她當前的固有馬力之上額外獲得 $g_i$ 大小的馬力。
一位賽馬娘食用了 $i$ 份紅蘿蔔就會在她當前的固有馬力之上額外獲得 $h_i$ 大小的馬力。
也就是說,編號為 $i$ 的賽馬娘在於時間 $t$ 舉辦的賽跑中所能表現出的馬力是 $it+\max \limits_{0\leq a,b,c \leq N, a+b+c=i}{(f_a+g_b+h_c)}$ 。
在時間 $t$ 舉辦的賽跑的勝者,就是在時間 $t$ 時馬力最大的賽馬娘,若有不只一名賽馬娘達到最大的馬力,就會判定為沒有勝者。
貴想去特別關心那些從未取勝的賽馬娘,也就是說貴想知道那些無論在任何時間 $t$ 賽跑都無法取勝的賽馬娘們她們的編號。
請你告訴貴這個問題的答案吧!(你肯定不會讓貴失望的吧?)
第一行輸入一個正整數 $N$,代表貴育成了 $3N+1$ 位賽馬娘。
第二行輸入 $N+1$ 個整數,分別代表 $f_0$ 到 $f_N$。
第三行輸入 $N+1$ 個整數,分別代表 $g_0$ 到 $g_N$。
第四行輸入 $N+1$ 個整數,分別代表 $h_0$ 到 $h_N$。
第一行輸出一個整數 $M$ ,代表從未取勝的賽馬娘的個數。
第二行輸出 $M$ 個整數,代表所有從未取勝的賽馬娘的編號從小到大排序後的結果。
IOICamp 2021 Day5 pL
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 0~41 | 無額外限制 | 100 |