User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

57.9% (22/38)

Description


ayu是住在北方小鎮的一個女孩,平時最喜歡在商店街散步,然後去商店街最深處的一家鯛魚燒店買熱騰騰的鯛魚燒吃。

雖然說是小鎮,其實這個小鎮還蠻大的,ayu可以每天換一條不一樣的路線走去鯛魚燒店,走了一個多月還沒重複。
走著走著她想到一個問題:這個小鎮有很整齊的棋盤狀街道,如果把ayu的出發點當做座標原點 (0, 0),商店街的位置在 (n, 2n)。
如果每天都選不一樣的路,而且走最短路線(只能向北和東走),要幾天才能走完所有的路線呢?

雖然心智年齡只有十歲,聰明的 ayu 馬上就算出有 C(3n, n) 種走法。當 n 很大的時候,就算走一輩子也走不完。
所以 ayu 想要對路線再加一點條件限制,讓可以挑的路線少一點:在 (0, 0) 到 (n, 2n) 間連一條直線,ayu 走的路只能在這條線的下方,可以踩到線,但是不能超過。
加了限制之後問題突然變的很複雜,超過 ayu 的能力範圍,聰明的你能不能幫他計算呢?

Ex: n=2時有3種走法如下圖

這是NPSC 2006比賽的決賽題目,因為事後實在有太多參賽者向主辦單位反映「我不認識ayu,為什麼聰明的我要幫她計算呢?」
於是在主辦單位的討論下,我們決定,今年將請你檢查主辦單位的計分系統是否是正確的,自己的幸福自己爭取!
雖然知道聰明的你一定了解,程式比賽的計分方式,但最近評審誤食了「邪惡PG詛咒之碎碎唸果實」所以免不了,還是要碎碎唸一下。

程式比賽的得分是根據你提交答案的時間來計算(愈早交卷就愈高分!),例如參賽隊伍PGtheEvil在時間t,提交了第x題的答案,經過評審一邊看柯南一邊仔細的檢查該程式後,PGtheEvil提交的程式是正確的,評審就會標記該隊伍在時間t所解的題數比時間t-1所解題多一,並更新使用者解題時間為原來的時間加上提交的時間t。

但為了懲罰那些不好好檢查程式就把答案提交上來,害得辛苦的評審沒有時間吃點心的參賽者(且害評審錯過了柯南最精采的推理!),生氣的評審就會標記該參賽隊伍的x題有答錯的紀錄,一旦最後參賽者第x題答對,除了上一段落描述的提交時間t外,需要在解題時間上外加上 (20*答錯次數) 做為對不乖參賽者的懲罰。
另外,為了爭取到吃最多點心的時間,一旦參賽者提交的第x題答對後,第x題在之後提交的成績將會被貪吃的評審給忽略。

Input Format

輸入檔中有許多組輸入(一組輸入代表某一次比賽時某隊伍的提交紀錄),每組輸入佔一個區塊,每一組輸入裡,會以一組整數M、N做為開始,當M=0且N=0 時代表輸入結束。其中M代表該次比賽時全部的題目總數,N代表該隊伍總共提交了幾次答案。其中0< M <=100(評審的程式最多可以處理一百題的大比賽!),0<=N<=500。
接著N行輸入代表該隊伍的提交紀錄,分別由三個整數T、W、G代表該隊伍「在時間T提交了第W題,並且評審給了G的回覆」,評審的回答G=0 代表錯誤的答案,G=1代表正確的答案,測試資料保證1<=T<=20000,1<=W<=M,G=0 or 1,1<=x<=N,且對於任意的時間T,最多只會有一個提交紀錄。

Output Format

對每一組測試資料,你應該輸出一列,該列包含兩個數字,依序表示該隊解題所花的時間(包含懲罰加計的時間)和該隊所解的題數。

Sample Input

8 7
30 3 0
32 2 1
48 1 0
77 3 1
99 1 0
116 1 1
118 1 0
0 0

Sample Output

285 3

Hints

Problem Source

原TIOJ1487 / NPSC2007決賽(prob C)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144