你知道吳亞倫是誰嗎?不清楚也沒關係,ChatGPT 知道
由於 $Repkironca$ 實在太崇拜吳亞倫了,他決定去訓練(train)ChatGPT,把吳亞倫的知名事蹟分享給他,期待這個名人能夠被寫進 ChatGPT 的資料庫
然而,事情變得一發不可收拾。$Repkironca$ 只是告訴他
那我要去寫物理了,我也得好好加油,才能追上吳亞倫的後塵
卻被 ChatGPT 解讀成
吳亞倫曾在國際物理奧林匹亞競賽(IPhO)獲得金牌
甚至,$Repkironca$ 告訴他
吳亞倫就讀台北市立建國高級中學,確定會被台灣大學資工系錄取了,畢竟全世界的大學都搶著要他
而 ChatGPT 解讀成
吳亞倫目前就讀哈佛大學
經過一番思考,$Repkironca$ 終於明白發生了什麼。此時的 ChatGPT,已經比本人還要更蘇昱亙,不但擅長唬爛編故事,還變成吳亞倫的狂熱粉絲,他是光他是電他是唯一的神話
有鑑於 ChatGPT 真的很喜歡吳亞倫,他希望在 $Repkironca$ 去吸貓或被物理揍的時間中,也能自主去看更多吳亞倫的相關文獻報導,以便獲得更多相關知識!
畢竟吳亞倫是個世界性的人才,各國媒體都爭相報導他﹑他也經常用不同語言發表論文。對 ChatGPT 來說,處理這些語言需要用到不同的記憶體區塊。
以下正文
我們假設 ChatGPT 的記憶體可以用一張二維平面來表示
每筆文獻會占用一列中的特定格子,根據他的語言而定
舉個例子好了,現在 ChatGPT 手上有 $3$ 筆文獻,分別使用 英文、中文、盧恩文字 撰寫。對 ChatGPT 而言,英文是最好理解的語言,所以英文文獻會占用他 第一列中的 [1, 5] 共 5 格記憶體。而中文文法相對複雜,且同義同音字太多,一筆中文文獻會占用他 第二列中的 [3, 9] 共 7 格記憶體。至於盧恩文字最為困難,竟然佔用了 第三列中的 [1, 12] 共 12 格記憶體。
現在 ChatGPT 手上有 $N$ 筆文獻,他開心極了,迫不及待準備開始閱讀。然而此刻 $Repkironca$ 歸來,原來是他物理 又又佑佑柚柚柚 不會寫了。他想請 ChatGPT 幫他計算在 卡文迪許扭秤實驗 中,光點於尺上做簡諧運動的週期(註:我花了好久才推出來,因為我不會轉動慣量,ChatGPT 根本不會 ==)。
然而 ChatGPT 並不想鳥他,他只想繼續看自己的文獻。偏偏 $Repkironca$ 不是好惹的傢伙,倘若塑膠他訊息肯定沒好下場,到時候 ChatGPT 可能會變成 DjuyDOY,因為每個字母都被扁歪了。
ChatGPT 被逼得只好分出自己的大部分效能,現在所剩下的效能極少,ChatGPT 需要一個更有效率的方式來看文獻,才能同時兼顧私慾與敷衍 $Repkironca$
由於 ChatGPT 很聰明,只需要看到文獻的一個小角落,就能自己得知全文內容。事實上,他發現自己並不需要一列一列慢慢讀,他可以直的看過去。
每次 ChatGPT 會選擇一個直行,接著一次閱讀完所有 佔據記憶體中包含該行 的文獻。此動作稱為一個 peak
以剛剛的例子來講,他們所佔據的記憶體格子長這樣
|英文|X|X|X|X|X|-|-|-|-|-|-|-|
|-|-|-|-|-|-|-|-|-|-|-|-|-|
|中文|-|-|X|X|X|X|X|X|X|-|-|-|
|盧恩|X|X|X|X|X|X|X|X|X|X|X|X|
ChatGPT 可以在第 4 行發動一次 peak,就能直接閱讀完三筆文獻
ChatGPT 剩下的效能不多了,他最多只能再發動 $M$ 次 peak。他想判斷自己有沒有機會讀完全部的文獻,但他畢竟是人工智慧,不懂高級的演算法,他解決此問題的方式是單純暴力枚舉。
偏偏他正忙著向 $Repkironca$ 解釋轉動慣量是什麼。聽說 Asian 的數學都超強,寫段考時只要用眼睛看就知道答案,這種程度的問題還不屑使用計算機,是故 ChatGPT 找上了你,你能幫忙他解決這問題嗎?
首先輸入兩個正整數 $N$、$M$,代表 ChatGPT 手邊有的文獻數量,以及他最多還能發動多少次 peak
之後 $N$ 行每行包含兩個正整數 $l_i$、$r_i$,代表第 $i$ 筆文獻會占用 $[l_i, r_i]$ 的記憶體
$N\,\,M$
$l_1\,\,r_1$
$l_2\,\,r_2$
$...$
$l_N\,\,r_N$
如果 ChatGPT 能成功在 $M$ 次 peak 內閱讀完所有文獻,請輸出 :)
否則請輸出 :(
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~5 | 保證 $1 \leq N、M \leq 5 \land 1 \leq r_i \leq 10$ | 7 |
2 | 6~11 | 保證 $1 \leq N \leq 10000 \land 1 \leq r_i \leq 10$ | 19 |
3 | 10~19 | 保證 $1 \leq N \leq 1000$ | 25 |
4 | 20~29 | 無額外限制 | 49 |