DYNASTIES - Các triều đại cổ
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: nguyenxuanhaa3

Đã có rất nhiều lãnh chúa trị vì đế chế Tactar – Mông cổ, mỗi người trong số n lãnh chúa thuộc một trong hai triều đại và các triều đại thường xuyên thay nhau cầm quyền. Mỗi lần lãnh chúa lên ngôi lại tổ chức một ngày lễ ăn mừng vào 26 tháng 3. Biên niên sử có ghi lại những năm tổ chức lễ mừng và cho biết triều đại thứ nhất tổ chức ăn mừng bằng sữa ngựa, còn triều đại thứ hai – mật ong.

Trong hội thảo về lịch sử đế chế Tactar – Mông cổ mỗi người trong s nhà khoa học tham dự trình bày cách giải mã các ghi chép tìm được. Nhà sử học thứ i cho rằng khoảng cách giữa hai lễ sữa ngựa liên tiếp nhau là không ít hơn kli năm và không nhiều hơn kri năm, còn hai lễ mật ong liên tiếp thì cách nhau không ít hơn mli năm và không nhiều hơn mri năm.

Mỗi giả thuyết sẽ tương ứng với một lịch trị vì của các triều đại. Các nhà khoa học thống nhất lấy số lần chuyển quyền cai trị của các lãnh chúa của một triều đại là chỉ số nghi ngờ độ chuẩn xác.

Hãy xác định giả thiết nào cho chỉ số nghi ngờ độ chuẩn xác nhỏ nhất. Nếu không tìm được giải thiết nào thì in số 0.

Dữ liệu: Vào từ file văn bản DYNASTIES.INP:

*      Dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 2×105),

*      Dòng thứ 2 chứa n số nguyên x1, x2, . . ., xn – các năm có ngày lễ (1 ≤ x1 < x2 <. . . < xn ≤ 109),

*      Dòng thứ 2 chứa số nguyên s (1 ≤ s ≤ 50),

*      Dòng thứ i trong s dòng sau chứa 4 số nguyên kli, kri, mlimri (1 ≤ klikri ≤ 109,1 ≤ mlimri ≤ 109).

Kết quả: Đưa ra file văn bản DYNASTIES.OUT, dòng thứ nhất chứa 2 số nguyên pq, trong đó p – số thứ tự của giả thuyết được chọn, q – chỉ số nghi ngờ.

Ví dụ

  • input
    5
    3 6 8 9 10
    2
    2 3 1 1
    1 4 1 10
    output
    2 0
Back to Top