Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

Problem : 321 - 看診問題

Problem Statistics

Solved Member: 13  Submission: 34  User Tried: 13

Statement:

現在有n 個病患收到了醫療中心的通知,. 每個人都收到了三種資訊:

  • 每個人的號碼(依序由1, 2, ... , n 編號)
  • 每個人應抵達醫療中心的時間點
  • 一個關於他們檢查依序要去的房間編號順序列表

醫療中心的房間編號依序為1, 2, ... , m,而來到醫療中心做檢查的病患必須遵守下規則:

  • 如果說病患應抵達醫療中心的時間為 t,那麼他會在時間 t 時抵達他的房間列表的第一間。
  • 如果有多個病患同時抵達同個房間,他們會按照號碼由小到大排隊。若前面已有一個隊伍,則此時這個隊伍會接續在前一個隊伍後面。
  • 如果說時間 t 時有隊伍在房間 x 前,隊伍中的第一個人將在時間t 進入房間做檢查,並且會在時間 t+1 時離開並(瞬間)移動至他房間列表中的下一個房間的隊伍裡。而隊伍中的下一個人將會於 t+1 的時間點進入房間x。
  • 如果說病患在時間 t 進入房間 x 檢查,且這已經是他列表中的最後一個房間時,他將於 t+1 的時間點離開醫療中心。

你的任務是求出最後一個離開醫療中心的病患於何時離開。

Input:Output:

第一行有兩個整數n,m,表示病患數目與醫療中心的房間數目。

接下來有n行,每行會是:ti, ki, gi,1, gi,2, ... ,gi,ki,表示第i個病患應於時間ti抵達醫療中心,房間列表共有ki個,依序為gi,1, gi,2, ... ,gi,ki,此行所有整數將以空白隔開。

限制:
1 ≤ n,m ≤ 1000
0 ≤ ti ≤ 1000000
ki > 0
1 ≤ gi,j≤ m
k1 + k2 + ... + kn ≤ 100000
輸出一個數字,表示最後一個離開醫療中心的病患於何時離開。

Sample Input:Sample Output:

5 3
1 3 3 2 1
0 7 2 3 1 1 1 1 2
2 1 1
1 2 3 3
4 3 1 1 1
12

HINT:

Line 1:有5個人,醫院有3間診間
Line 2:編號1的人,在時間1來到醫院,依序要去3,2,1診間
Line 3:編號2的人,在時間0來到醫院,依序要去2,3,1,1,1,1,2診間
Line 4:編號3的人,在時間2來到醫院,依序要去1診間
Line 5:編號4的人,在時間1來到醫院,依序要去3,3診間
Line 6:編號5的人,在時間4來到醫院,依序要去1,1,1診間

Source:

102附中校內賽

Problem Setter

Testdata:

TestTimeMemoryScore
01000ms262144kb
1-11000ms262144kb10
1-21000ms262144kb
1-31000ms262144kb
1-41000ms262144kb
2-11000ms262144kb10
2-21000ms262144kb
2-31000ms262144kb
3-11000ms262144kb10
3-21000ms262144kb
3-31000ms262144kb
4-11000ms262144kb10
4-21000ms262144kb
5-11000ms262144kb10
5-21000ms262144kb
6-11000ms262144kb10
6-21000ms262144kb
7-11000ms262144kb10
7-21000ms262144kb
7-31000ms262144kb
7-41000ms262144kb
8-11000ms262144kb10
8-21000ms262144kb
8-31000ms262144kb
9-11000ms262144kb10
9-21000ms262144kb
9-31000ms262144kb
10-11000ms262144kb10
10-21000ms262144kb
10-31000ms262144kb
10-41000ms262144kb