e841: P8. 幽靈寶藏(Treasure)
Tags :
Accepted rate : 2人/11人 ( 18% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-02-02 01:28

Content

y19m08a_p8_幽靈寶藏(Treasure)    2019年,08月,TOI, 新手同好會 {題目連結}

 問題敘述

探險隊在一座廢墟中找到了傳說中的藏寶箱,當他們正要取走寶藏時,出現了傳說中的海盜幽靈,幽靈決定和探險隊的成員玩一個遊戲。

遊戲的規則如下,幽靈會先變出N個空的藏寶箱,並進行以下兩種操作共M次:

(1) 在連續的數個藏寶箱內放入S枚硬幣。

(2) 使連續的數個藏寶箱內的硬幣價值變為S倍,包括事後放入的硬幣。

 當幽靈完成所有操作後,探險隊可以挑選一個寶箱帶走。請你幫探險隊找出價值最高的寶箱。

 

範例說明1:最後寶箱內價值為:2、5、10、10、12。

範例說明2:最後寶箱內價值為:1、6、6、6、6、1,輸出編號最小者。

評分說明本題共有三組測試題組,條件限制如下所示。每組的所有測試資料皆需答對才會獲得該組分數。

子任務1 分數10   額外輸入限制:1<=N, M <=10^2

子任務2 分數30   額外輸入限制:1<=N, M <=10^4

子任務3 分數60   額外輸入限制:1<=N, M <=10^6

 

 

Input

每筆測試資料為M+1列,第一列有兩個正整數NM(1<=N, M <=10^6),代表有N個空寶箱,編號為1至N,以及M個操作。緊接著M列,每列都有四個正整數PQRS(1<=P, Q<=N),R只有兩種值1或2,當R為1時,代表幽靈在第PQ個藏寶箱內放入了S枚硬幣,當R為2時,代表幽靈使第PQ個藏寶箱的硬幣價值變為S倍,一個寶箱的最終價值不會超過20億。

 

Output

對每筆資料請輸出一列共兩個數字,為最高價值寶箱的編號以及其價值。若有數個寶箱價值相等,請輸出編號最小者。

 

 

Sample Input #1
5 4
3 5 2 2
1 4 1 2
5 5 2 2
2 5 1 3
Sample Output #1
5 12
Sample Input #2
6 5
1 6 1 1
2 3 1 2
3 5 2 2
2 2 1 3
4 5 1 2
Sample Output #2
2 6
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1K
公開 測資點#2 (5%): 1.0s , <1K
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <1M
公開 測資點#7 (5%): 1.0s , <1M
公開 測資點#8 (5%): 1.0s , <1M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <10M
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <10M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <10M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :
Tags:
出處:
2019年08月TOI新手同好會 [管理者:
p3a_owhj (阿普二信)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」