HSGTP #1 - Tặng quà (GIFT)

View as PDF

Submit solution


Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: GIFT.INP
Output: GIFT.OUT

Problem type
Allowed languages
C++, Pascal

Bác Hai là một người rất rộng lượng nên bác đã quyết định sẽ tặng quà cho mọi đứa trẻ trong xóm. Xóm bác gồm có ~n~ nhà được đánh dấu từ ~1~ đến ~n~, mỗi nhà đều có một đứa trẻ.

  • Để thuận tiện, bác Hai sẽ tặng quà trong ~q~ lượt, mỗi lượt Bác tặng quà cho một dãy các ngôi nhà liên tiếp.
  • Sau tất cả ~q~ lượt, các bạn nhỏ được tặng quà ít hơn bạn trong xóm mình (hoặc không được tặng quà) sẽ không hài lòng và tới nhà bác Hai để phàn nàn. Những bạn nhỏ không thuộc trường hợp trên sẽ được coi là đã hài lòng.

Vì bác muốn cho các bạn vui, bác Hai sẽ cố gắng đáp ứng yêu cầu của tất cả bạn trẻ, phát quà cho các bạn nhỏ cho đến khi tất cả mọi người đều hài lòng.

Yêu cầu:

Hãy giúp bác Hai tính số quà tặng ít nhất cần phát thêm, sau ~q~ lượt phát ban đầu, để làm cho các bạn nhỏ trong xóm hài lòng

Dữ liệu (Vào từ tệp GIFT.INP)

  • Dòng đầu tiên chứa ~n~ và ~q~ lần lượt là là số ngôi nhà trong xóm và số lượt phát quà của bác Hai.
  • ~q~ dòng tiếp theo chứa ~a~ và ~b~ là đại diện cho một lượt phát quà của bác Hai: bác phát từ ngôi nhà thứ ~a~ đến ngôi nhà thứ ~b~, mỗi nhà ~1~ phần quà (~1 \le a \le b \le n)~

Kết quả (Xuất ra tệp GIFT.OUT)

  • In ra một số nguyên duy nhất là số lượng phần quà bác cần chuẩn bị thêm để tất cả những đứa trẻ trong xóm hài lòng.

Ví dụ:

Sample Input 1
5 3
1 2
1 3
3 5
Sample Output 1
2
Note
  • Bác Hai đã phát quà cho các ngôi nhà theo thứ tự như trên.
  • Ở mỗi ngôi nhà số phần quà bạn nhỏ nhận được là:
Nhà ~1~ Nhà ~2~ Nhà ~3~ Nhà ~4~ Nhà ~5~
~2~ ~2~ ~2~ ~1~ ~1~
  • Như vậy, đứa trẻ ở nhà số ~4~ và số ~5~ đã đến khiếu nại bác Hai, vì thế bác Hai cần phát thêm ~2~ phần quà, ~1~ cho nhà số ~4~ và ~1~ cho nhà số ~5~.

Subtask:

  • ~20\%~ số test tương ứng với ~20\%~ số điểm có ~n \le 10^3, q \le 10^3~.
  • ~40\%~ số test tương ứng với ~40\%~ số điểm có có ~n \le 10^5, q \le 10^5~.
  • ~40\%~ số test tương ứng với ~40\%~ số điểm có có ~n \le 10^9, q \le 10^5~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.