COCI 2019/2020 - Contest 2 - ACM

View as PDF

Submit solution

Points: 0.20 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2019/2020 - Contest 2
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Một cuộc thi lập trình cổ đại sắp sửa được diễn ra và nó được tổ chức bởi ~ACM~ (Trung Tâm Hàng Không Metković - Aeronautic Centre of Metković). Cuộc thi có ~N~ đội tham gia tranh tài, mỗi đội sẽ cần phải hoàn thành ~M~ bài toán từ Ban Tổ chức cuộc thi.

Các đội được sắp xếp không tăng bởi số lượng bài toán đã hoàn thành. Những đội có số lượng bài toán đã hoàn thành bằng nhau được sắp xếp không giảm bởi cái gọi là thời gian penalty. Thời gian penalty của một đội là tổng thời gian penalty đội đó nhận được sau khi hoàn thành chính xác một bài toán. Thời gian penalty của một đội hoàn thành chính xác một bài toán bằng với thời gian đội đó giải quyết bài toán (tính từ lúc bắt đầu cuộc thi) và sẽ bị tăng thêm ~20~ phút phạt với mỗi lần nộp sai lời giải của bài toán đó. Không đội nào được phép nộp lời giải cho bài toán mà họ đã giải quyết chính xác trước đó và mỗi đội sẽ có tối đa ~9~ lần nộp bài cho mỗi bài toán. Nếu tồn tại một số đội nào đó có cùng số bài toán đã hoàn thành và cùng thời gian penalty, họ sẽ được sắp xếp theo thứ tự bảng chữ cái trong bảng xếp hạng cuối cùng.

Cuộc thi sẽ kết thúc sau ~5~ giờ đồng hồ. Trong suốt ~4~ giờ đầu bảng xếp hạng sẽ cho tất cả các đội biết thông tin về trạng thái của mỗi bài toán của từng đội khác (số lần nộp bài, đã được giải quyết hay chưa, giải quyết khi nào). Trong suốt ~4~ giờ đó, thứ tự của các đội sẽ được cập nhật một cách tự động sau mỗi lần nộp. Trong ~1~ giờ đồng hồ cuối cùng, bảng xếp hạng sẽ bị đóng băng, nghĩa là, thứ tự của các đội sẽ không được cập nhật sau từng lần nộp nữa. Suốt thời gian đó, mỗi đội sẽ chỉ biết kết quả của các bài nộp của họ, nhưng họ không biết kết quả bài nộp của các đội khác. Họ chỉ biết bài toán được nộp bởi một đội nào đó, số lần mà họ nộp và thời điểm nộp bài cuối cùng của từng bài toán.

Cuộc thi sẽ kết thúc và bảng xếp hạng sẽ sớm được ngừng đóng băng. Những vị anh hùng của chúng tôi, NijeZivotJedanACM, cần bạn giúp. Họ muốn biết vị trị tệ nhất họ sẽ đứng trên bảng xếp hạng sau khi bảng xếp hạng ngừng đóng băng. Hãy giúp họ!

Input

Dòng đâu tiên chứa số nguyên ~N~ ~(1 \le N \le 1000)~ và ~M~ ~(1 \le M \le 15)~.

~N~ dòng tiếp theo biểu thị bảng xếp hạng bị đóng băng. Mỗi dòng bắt đầu bằng tên đội (là xâu được tạo từ các chữ cái tiếng Anh viết hoa và viết thường, tối đa ~20~ kí tự, tên của các đội phân biệt) được tách bởi dấu cách từ ~M~ xâu (cũng được tách nhau bởi dấu cách) chứa thông tin về trạng thái của từng bài của đội đó.

Các xâu đó sẽ có dạng ~SX/V~, trong đó:

  • ~S~ tượng trưng cho trạng thái của bài toán ~–~ + nghĩa là bài đó đã được giải quyết chính xác, - nghĩa là bài đó được giải quyết chưa chính xác và ? nghĩa là bài nộp cuối cùng khi bảng xếp hạng đã bị đóng băng.

  • ~X~ biểu thị số lần nộp của đội đó cho riêng bài toán này. Nó được phép bỏ qua nếu không có bài nộp nào cho bài đó.

  • ~V~ biểu thị thời gian bài nộp cuối cùng nộp bởi đội đó cho riêng bài toán này. Nó được nhập theo dạng HH:MM:SS (tồn tại số ~0~ vô nghĩa) và nhỏ hơn ~5~ giờ. Toàn bộ phần ~/V~ được phép bỏ qua nếu bài toán được giải quyết chưa chính xác (trạng thái -).

Dòng cuối cùng chứa xếp hạng không bị đóng băng của những vị anh hùng của chúng tôi, NijeZivotJedanACM.

Output

Gồm ~1~ dòng duy nhất là vị trí tệ nhất những vị anh hùng NijeZivotJedanACM sẽ đứng trên bảng xếp hạng sau khi bảng xếp hạng ngừng đóng băng.

Sample Input 1

2 1
NijeZivotJedanACM -
ZivotJESTJedanACM -
NijeZivotJedanACM –

Sample Output 1

1

Sample Input 2

3 2
StoJeZivot ?1/04:00:00 +1/02:04:06
JeLiZivotJedanACM ?1/04:59:59 -
NijeZivotJedanACM ?1/04:42:43 -
NijeZivotJedanACM +1/04:42:43 –

Sample Output 2

2

Sample Input 3

7 4
NisamSadaNistaDonio +1/03:59:59 +3/03:42:02 +2/00:14:59 ?1/04:56:12
JeLiMojKockaSeUmio ?4/04:00:00 -3 +1/00:10:01 +9/03:04:42
OstaviDobroJe ?4/04:59:59 -1 +2/00:24:15 +8/03:24:45
DobroJeOstavi +1/01:42:53 - ?9/04:58:23 ?1/04:34:43
NijeZivotJedanACM ?2/04:50:05 ?4/04:32:12 +2/01:32:45 ?1/04:59:59
KoSeToSeta ?1/04:23:32 - +9/01:00:00 -9
SipSipSipSipSipSip - - - ?9/04:00:00
NijeZivotJedanACM -2 +4/04:32:12 +2/01:32:45 +1/04:59:59

Sample Output 3

3

Subtask

  • ~2~ test đầu tiên input không chứa kí tự ?.
  • ~3~ test cuối cùng không có điều kiện gì thêm.

Giải thích ví dụ 1:

Không có gì thay đổi sau khi bảng xếp hạng ngừng đóng băng. Vì vậy, những vị anh hùng của chúng tôi sẽ về đích ở vị trí thứ nhất!

Giải thích ví dụ 2:

Trong trường hợp xấu nhất những vị anh hùng của chúng tôi sẽ chỉ thua đội StoJeZivot, vì vậy về đích ở vị trí thứ hai.

Giải thích ví dụ 3:

Trong trường hợp xấu nhất những vị anh hùng của chúng tôi sẽ thua đội NisamSadaNistaDonioJeLiMojKockaSeUmio, vì vậy về đích ở vị trí thứ ba.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.