1772: Цукеркоман
View as PDFАндрiй, як справжнiй цукеркоман, коли приходить в магазин купляє все, що бачить. А саме, у кожний свiй вiзит вiн купляє цукерки з послiдовними номерами вiд \(l\) до \(r\).
Завтра Андрiй вирушає на дуже вiдповiдальний захiд — фiнал ВЮДОI, а тому хоче взяти з собою як можна бiльше цукерок. Вiн знає, що цукерка з номером \(i\) важить \(i\) грамiв, а його рюкзак може витримувати вагу до \(w\) грамiв. Всього було \(n\) вiзитiв до магазину, в кожен з яких вiн може придбати цукерки з iнтервалу \([l_i,r_i]\).
Скажiть максимальну кiлькiсть цукерок, яку вiн може взяти з собою, якщо вiдомо, що вiн може брати не бiльше \(i\) цукерок з номером \(i\).
Формат вхiдних даних
Перший рядок мiстить два цiлi числа \(n\) (\(1 \le n \le 10^6\)) та \(w\) (\(1 \le w \le 10^{12}\)) — кiлькiсть вiзитiв до магазину та максимальна вага, яку може витримати рюкзак Андрiя у грамах.
Наступнi \(n\) рядкiв мiстять кожен по два цiлi числа \(l_i\) та \(r_i\) (\(1 \le l_i \le r_i \le 10^5\)).
Формат вихiдних даних
Виведiть одне цiле число — вiдповiдь на задачу.
Приклад вхідних даних
3 14
1 4
2 3
4 5Приклад вихідних даних
5Приклад вхідних даних
3 20
1 10
1 10
1 10Приклад вихідних даних
7Зауваження
Пояснення до першого прикладу:
Список усiх цукерок, якi купив Андрiй — [1, 2, 3, 4, 2, 3, 4, 5].
Один з варiантiв взяти 5 цукерок — [2, 3, 4, 3, 2].
Пояснення до другого прикладу:
Один з варiантiв взяти 7 цукерок буде наступним — [1, 2, 2, 3, 3, 4, 5], сумарна вага буде 20 грамiв.
Comments
Трохи запутана, але прочитавши умову декілька разів можна зрозуміти суть. Якраз і пропонується дітям на олімпіадах, якщо не зрозумів умову читай ще раз
Задача класна. Тільки як завжди все заплутано і некоректно сформульовано. Варто розбити умову на дві частини: 1) закупівля в магазині, 2) похід на фінал. А ось запитання по задачі: Чи впливає вага рюкзака на 1 похід в магазин? Чи передбачено це вхідними даними? Чи допустима вага рюкзака впливає тільки на "похід на фінал"?
Автор задачі є призером Міжнародної олімпіади з інформатики і неодноразово пропонував свої задачі на 4-му етапі. Отже, претензії щодо некоректності відхилені. Запутаність задачі - ну, так :).