Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BCACM11I - Đường một chiều

Có một quãng đường rất hẹp chỉ đủ cho một chiếc xe ô tô có thể qua tại một thời điểm. Các xe không thể vượt nhau và cũng thể đi ngược chiều nhau trên quãng đường này. Tại hai đầu của quãng đường (giả sử là đầu A và đầu B) người ta muốn sắp xếp một cách tối ưu các xe ô tô sao cho các xe đều qua được quãng đường này và thời điểm xe cuối cùng kết thúc hành trình là nhỏ nhất. Với mỗi chiếc xe sẽ có ba giá trị là: điểm xuất phát, thời gian bắt đầu đến tổng thời gian cần thiết để đi qua đường. Để đảm bảo an toàn, hai xe cùng chiều phải đi cách nhau ít nhất 10 giây.  

Ví dụ với 4 xe đến được mô tả là:     

Xe thứ nhất: A 0 60

Xe thứ hai:   B 19 10

Xe thứ ba:    B 80 20

Xe thứ tư:    A 85 100

Ta sẽ có cách sắp xếp tốt nhất là:  Xe thứ nhất đi tại thời điểm 0, xe thứ hai đi tại thời điểm 60, xe thứ ba đi tại thời điểm 80 và xe thứ 5 đi tại thời điểm 100. Thời điểm xe cuối cùng kết thúc hành trình là 100 + 100 = 200.

 Input: Dòng đầu tiên ghi số bộ test, không lớn hơn 200. Mỗi bộ test gồm:

  • Dòng đầu tiên ghi số nguyên dương n không lớn hơn 200.
  • n dòng tiếp theo ghi thông tin về mỗi chiếc xe trong đó gồm 1 ký tự (A hoặc B) cho biết hướng đi, tiếp theo là hai số nguyên t và d với t là thời điểm đến còn d là thời gian cần thiết (ít nhất) để đi hết quãng đường (t và d không lớn hơn 105)

Chú ý: các ô tô đã được sắp xếp theo thời gian đến tăng dần và không có hai xe nào đến cùng nhau. 

Output: Với mỗi bộ test, output đưa ra một số nguyên duy nhất là thời gian mà chiếc xe cuối cùng đã rời khỏi quãng đường theo cách sắp xếp tối ưu. 

Example

Input:

2

4

A 0 60

B 19 10

B 80 20

A 85 100

4

A 0 100

B 50 100

A 100 1

A 170 100 Output:

200

270
Giải thích test 2:
Xe 2 xuất phát trước.
Xe 1 xuất phát lúc t = 150, đến đích lúc t = 250.
Xe 3 xuất phát lúc t = 160, đến đích lúc t = 260 (d = 1 chỉ là thời gian tối thiểu để đi hết quãng đường).
Xe 4 xuất phát lúc t = 170, đến đích lúc t = 270.

ID RESULT TIME
code...



Được gửi lên bởi:adm
Ngày:2011-10-20
Thời gian chạy:1s-1.894s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA
Nguồn bài:ACM PTIT 2011

hide comments
2019-08-15 15:12:57
toi la tran duc manh xin chao hoang nghia hiep
2012-09-16 07:00:16 Trần Vãn Dương D10CN2
tai sao bo test 2 la 270 ma khog phai la KQ khac
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.