Bạn đang nghiên cứu lịch sử của Vạn Lý Trường Thành, được xây dựng để chống lại các cuộc xâm lược quân sự từ phương Bắc. Trong bài toán này, ta giả định Vạn Lý Trường Thành kéo dài từ vô tận ở phía Đông đến âm vô tận ở phía Tây. Vì khoảng cách quá lớn, bức tường không được xây dựng cùng một lúc. Thay vào đó, người xây dựng sử dụng chiến lược phản ứng: bất cứ khi nào một phần biên giới bị tấn công thành công, bức tường ở phần đó sẽ được nâng lên độ cao đủ để ngăn chặn một cuộc tấn công tương tự trong tương lai.

Biên giới phía Bắc thường xuyên bị các bộ lạc du mục tấn công. Mỗi bộ lạc tấn công biên giới trên một đoạn nhất định với cường độ \(S\). Để đẩy lùi cuộc tấn công, bức tường phải có độ cao ít nhất là \(S\) trên toàn bộ đoạn bị tấn công. Nếu chỉ cần một đoạn nhỏ của bức tường thấp hơn mức cần thiết, cuộc tấn công sẽ xuyên thủng bức tường tại điểm đó và thành công. Lưu ý rằng ngay cả một cuộc tấn công thành công cũng không làm hỏng bức tường. Sau cuộc tấn công, mọi đoạn tường bị tấn công có độ cao thấp hơn \(S\) sẽ được nâng lên độ cao \(S\) — nói cách khác, bức tường được nâng lên theo cách tối thiểu để có thể ngăn chặn cuộc tấn công đó. Nếu hai hoặc nhiều cuộc tấn công xảy ra trong cùng một ngày, bức tường chỉ được nâng lên sau khi tất cả các cuộc tấn công đó đã kết thúc, và được nâng lên theo cách tối thiểu để có thể ngăn chặn tất cả chúng.

Các bộ lạc du mục không nhất thiết chỉ tấn công một lần. Họ có xu hướng di chuyển (sang phía Đông hoặc phía Tây) và định kỳ tấn công bức tường. Để đơn giản hóa, ta giả định họ di chuyển với tốc độ không đổi và tấn công bức tường theo các khoảng thời gian đều đặn; hơn nữa, cường độ tấn công của một bộ lạc thay đổi một lượng không đổi sau mỗi lần tấn công (giảm do tiêu hao hoặc tăng do kinh nghiệm).

Giả sử ban đầu (năm 250 TCN) bức tường chưa tồn tại (độ cao bằng 0 ở mọi nơi), và cho biết mô tả đầy đủ về tất cả các bộ lạc du mục, hãy xác định có bao nhiêu cuộc tấn công đã thành công.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo, mỗi bộ bắt đầu bằng một dòng chứa một số nguyên \(N\): số lượng bộ lạc tấn công bức tường. \(N\) dòng tiếp theo, mỗi dòng mô tả một bộ lạc. Dòng thứ \(i\) chứa tám số nguyên \(d_i, n_i, w_i, e_i, s_i, delta\_d_i, delta\_p_i\) và \(delta\_s_i\) cách nhau bởi dấu cách:

• \(d_i\) – ngày diễn ra cuộc tấn công đầu tiên của bộ lạc (ngày 1 tháng 1 năm 250 TCN được coi là ngày 0).
• \(n_i\) – số lần tấn công của bộ lạc này.
• \(w_i, e_i\) – điểm cực Tây và cực Đông của đoạn tường bị tấn công trong lần đầu tiên.
• \(s_i\) – cường độ của cuộc tấn công đầu tiên.
• \(delta\_d_i\) – số ngày giữa các cuộc tấn công liên tiếp của bộ lạc này.
• \(delta\_p_i\) – khoảng cách bộ lạc di chuyển về phía Đông giữa các cuộc tấn công liên tiếp (nếu âm, bộ lạc di chuyển về phía Tây).
• \(delta\_s_i\) – sự thay đổi cường độ giữa các cuộc tấn công liên tiếp.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số cuộc tấn công thành công.

Ràng buộc

• \(1 \le T \le 20\).
• \(0 \le d_i\).
• \(1 \le delta\_d_i \le 676060\).
• \(d_i + (n_i - 1) \times delta\_d_i \le 676060\).
• \(1 \le s_i \le 10^6\).
• \(-10^5 \le delta\_s_i \le 10^5\).
• \(s_i + (n_i - 1) \times delta\_s_i \ge 1\).

Phân nhóm

• Small dataset (Test set 1):
  • \(1 \le N \le 10\).
  • \(1 \le n_i \le 10\).
  • \(-100 \le w_i < e_i \le 100\).
  • \(-10 \le delta\_p_i \le 10\).
• Large dataset (Test set 2):
  • \(1 \le N \le 1000\).
  • \(1 \le n_i \le 1000\).
  • \(-10^6 \le w_i < e_i \le 10^6\).
  • \(-10^5 \le delta\_p_i \le 10^5\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
2
0 3 0 2 10 2 3 -2
10 3 2 3 8 7 2 0
3
1 2 0 5 10 2 8 0
0 3 0 1 7 1 2 2
3 3 0 5 1 1 4 0

Case #1: 5
Case #2: 6

Nguồn

Google Code Jam 2013, Vòng 1C, bài The Great Wall.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.