Bài trên SPOJ

Từ tập các bài có trên SPOJ 2117. Bus(Mã bài: NKBUS) : Một xe buýt của công ty có nhiệm vụ đón nhân viên đến trụ sở làm việc. Trên hành trình, xe buýt sẽ tiếp nhận nhân viên đứng chờ ở các điểm hẹn nếu như xe còn chỗ trống. Xe buýt có thể đỗ lại để chờ những công nhân chưa kịp đến điểm hẹn. Cho biết thời điểm mà mỗi nhân viên đến điểm hẹn của mình và thời điểm qua mỗi điểm hẹn của xe buýt. Giả thiết rằng xe buýt đến điểm hẹn đầu tiên tại thời điểm 0 và thời gian xếp khách lên xe được bằng 0. Xe buýt cần phải chở một số lượng nhiều nhất các nhân viên có thể được đến trụ sở. Hãy xác định khoảng thời gian ngắn nhất để xe buýt thực hiện công việc.
Dữ liệu vào: Dòng đầu tiên chứa 2 số nguyên dương n, m theo thứ tự là số điểm hẹn và số chỗ ngồi của xe buýt .Dòng thứ i trong số n dòng tiếp theo chứa số nguyên ti là thời gian cần thiết để xe buýt di chuyển từ điểm hẹn thứ i đến điểm hẹn thứ i+1 (điểm hẹn thứ n+1 sẽ là trụ sở làm việc của công ty) và số nguyên k là số lượng nhân viên đến điểm hẹn i, tiếp theo k số nguyên là các thời điểm đến điểm hẹn của k nhân viên.
Kết qủa : Gồm một dòng duy nhất, là thời gian ngắn nhất tìm được.
Giới hạn :1 ≤ n ≤ 200000, 1 ≤ m ≤ 20000. Tổng số nhân viên ko vượt quá 200000. Kquả ko vượt quá 231-1.
Ví dụ
Dữ liệu mẫu
3 2
3 2 4 3
1 3 6 3 7
5 1 5
Kết qủa
10
Giải thích: Trên đường đến công ty có 3 trạm xe buýt. Từ trạm 1 đến trạm 2, trạm 2 đến trạm 3, và từ trạm 3 đến công ty lần lượt mất 3, 1 và 5 đơn vị thời gian. Xe buýt có thể đi như sau: đến thẳng trạm 2, đón người thứ 2, đến trạm 3, chờ 1 đơn vị thời gian để đón người duy nhất ở trạm này, và cuối cùng đến công ty. Tổng cộng xe buýt đi mất 3 + 1 + 1 + 5 = 10 đơn vị thời gian.
2118.Chuỗi đối xứng(Mã bài: NKPALIN):1 chuỗi đgl đối xứng (palindrome) if như khi đọc chuỗi này từ phải sang trái cũng thu được chuỗi ban đầu.
Yêu cầu:Tìm 1 chuỗi con đối xứng dài nhất of một chuỗi s cho trước. Chuỗi con là chuỗi thu được khi xóa đi 1 số ký tự từ chuỗi ban đầu.
Dữ liệu vào:Gồm một dòng duy nhất chứa chuỗi s, chỉ gồm những chữ cái in thường.
Kết qủa:Gồm 1 dòng duy nhất là 1 xâu con đối xứng dài nhất of xâu s. If có nhiều kết quả, chỉ cần in ra 1 kết quả bất kỳ.
Giới hạn: Chuỗi s có độ dài không vượt quá 2000.
Ví dụ
Dữ liệu mẫu
lmevxeyzl
Kết qủa
Level
2163.Kiểm tra chương trình(Mã bài: NKTEST): Test tuy ko phải là phương pháp để chứng minh tính đúng đắn of chương trình, nhưng vẫn được sử dụng rộng rãi để phát hiện lỗi sai và tăng độ tin cậy. Có nhiều phương pháp hiệu chỉnh chương trình, nhưng nội dung chủ yếu vẫn dựa trên cơ sở chọn các bộ tests để đi vào các nhánh khác nhau của chương trình. Cho mô tả chương trình dưới dạng các dòng lệnh. Các lệnh tuyến tính được ký hiệu là S, lệnh rẽ nhánh không đầy đủ được xác định bởi 2 câu lệnh IF và END_IF, lệnh rẽ nhánh đầy đủ được xác định bởi 3 câu lệnh IF, ELSE, và END_IF. Điều kiện sau IF được bỏ qua trong mô tả. Chương trình kết thúc bằng lệnh ENDPROGRAM.
Yêu cầu:Xđịnh số lượng tests cần thiết để kiểm tra tất cả các nhánh of chương trình.
Dữ liệu: Gồm nhiều dòng, mô tả một chương trình theo định dạng đã nêu.
Kết qủa:Gồm 1 dòng duy nhất, chứa số lượng tests cần thiết để kiểm tra tất cả các nhánh của chương trình.
Giới hạn :Kết quả không vượt quá 231-1
Ví dụ
Dữ liệu:
S
IF
S
S
ELSE
IF
IF
S
ELSE
S
END_IF
S
ELSE
S
END_IF
END_IF
S
ENDPROGRAM
Kết qủa
4
Dữ liệu:
S
IF
END_IF
ENDPROGRAM
Kết qủa
2
Dữ liệu:
S
S
ENDPROGRAM
Kết qủa
1
2187.Hội trường(MB: NKREZ)Nhà trường có 1 phòng hội trường. Có những yêu cầu muốn sử dụng phòng hội trường này, mỗi yêu cầu cho biết thời điểm bắt đầu & thời