PHÁT ĐỒNG XU (5 ĐIỂM) TRONG MỘT TRÒ CHƠI, CÓ 𝑁 NGƯỜI CHƠI XẾP T...

Bài 3. Phát đồng xu (5 điểm)

Trong một trò chơi, có 𝑁 người chơi xếp thành một vòng tròn và được đánh số từ 1 đến 𝑁 theo

chiều kim đồng hồ. Trước khi trò chơi bắt đầu, sẽ có 𝑀 lượt phát đồng xu cho người chơi với nguyên

tắc như sau: mỗi lượt, chọn ngẫu nhiên hai số nguyên dương 𝐿 và 𝑅 (𝐿 ≤ 𝑁, 𝑅 ≤ 𝑁), phát một đồng xu

cho những người chơi từ số 𝐿 đến số 𝑅 theo chiều kim đồng hồ.

Yêu cầu: Cho trước 𝑁, 𝑀 và các cặp số 𝐿, 𝑅. Tìm số đồng xu lớn nhất mà người chơi được phát và số

lượng người chơi đạt được số đồng xu như vậy.

Dữ liệu vào từ tệp BAI3.INP:

• Dòng đầu tiên gồm hai số nguyên dương 𝑁 và 𝑀 là số lượng người chơi và số lượt phát đồng

xu.

• 𝑀 dòng sau, mỗi dòng gồm hai số nguyên dương 𝐿 và 𝑅 mô tả lượt phát đồng xu.

Kết quả ra ghi vào tệp BAI3.OUT:

Gồm hai số nguyên dương là số đồng xu lớn nhất mà người chơi được phát và số lượng người

chơi đạt được số đồng xu như vậy.

Ví dụ:

BAI3.INP BAI3.OUT Giải thích

2 4 Số đồng xu của mỗi người ở mỗi lượt phát đồng xu:

5 2

Ban đầu: 0 0 0 0 0

1 5

4 2

Lượt thứ nhất: 1 1 1 1 1

Lượt thứ hai: 2 2 1 2 2

Vậy số lượng đồng xu lớn nhất là 2 và có 4 người được 2 đồng xu.

Lưu ý: Mỗi số nguyên cách nhau một dấu cách.

• Có 60% số test: 𝑁, 𝑀 ≤ 10 ^" ;

• Có 20% số test khác: 𝑁, 𝑀 ≤ 10 ^$ ;

• Có 20% số test còn lại: 𝑁 ≤ 10 ^! , 𝑀 ≤ 10 ^$ .