Вместо да слуша уроците в училище, Оги решава да подпомогне шахматната си кариера, тренирайки върху предварително подбрани 𝑛 шах-пъзела, номерирани с числата от 1 до 𝑛.
Той знае, че повторението е майка на знанието и решава да си изгради следния 𝑞-стъпков
тренировъчен план, състоящ се от две различни упражнения:
• Вид 1: Оги решава пъзелите с номера 𝑙, 𝑙 + 1, … , 𝑟 отново.
• Вид 2: Оги изпълнява стъпки с номера 𝑙, 𝑙 + 1, … , 𝑟 отново. Тук е вярно, че винаги ще
повтаряме вече изпълнени стъпки.
Забележете, че като резултат от тренировъчния си план, Оги ще реши някои пъзели многократно – това не е проблем, все пак повторението е майка на знанието.
Напишете програма chess.cpp, която определя за всеки пъзел колко пъти е бил решен в
следствие от тренировъчния план на Оги. Понеже всеки един пъзел може да бъде решен много
пъти, изведете остатъците на числата при деление на 109 + 7.
Вход
От първи ред на стандартния вход се въвеждат две числа 𝑛 и 𝑞 – броят на пъзелите, които
Оги ще решава и броят на стъпките в тренировъчния план на Оги. От всеки от следващите 𝑞
реда се въвеждат по три числа – 𝑡𝑖
𝑙
𝑖
𝑟𝑖
, които ни задават вида на поредната стъпка в плана и
интервала, върху който тя действа.
Изход
На единствен ред на стандартния изход изведете 𝑛 числа – за всеки пъзел колко пъти е бил
решен по модул 109 + 7.
Ограничения
• 1 ≤ 𝑛, 𝑞 ≤ 105
;
• 1 ≤ 𝑡𝑖 ≤ 2 за всяко 1 ≤ 𝑖 ≤ 𝑛;
• 1 ≤ 𝑙𝑖 ≤ 𝑟𝑖 ≤ 𝑛, когато 𝑡𝑖 = 1;
• 1 ≤ 𝑙𝑖 ≤ 𝑟𝑖 < 𝑖, когато 𝑡𝑖 = 2.
Подзадачи
Подзадача Точки Необходими подзадачи 𝑛, 𝑞 Други ограничения
0 0 − − Примерният тест.
1 10 − ≤ 103
𝑡𝑖 = 1
2 20 1 ≤ 105
3 10 0 ≤ 10 –
4 30 0 − 1, 3 ≤ 103 –
5 30 0 − 4 ≤ 105 –
Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.
1 / 2
XLI НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА
Национален кръг
Велико Търново, 7 - 10 март 2025 г.
Група С, 7 – 8 клас, Ден 2
Пример
Вход Изход Обяснение на примера
5 5
1 1 2
1 4 5
2 1 2
1 3 4
2 3 4
3 3 2 5 3 На първата стъпка Оги решава веднъж пъзели 1 и 2, а на втората
- веднъж 4 и 5. На третата стъпка повтаря миналите две, така че
пъзели 1, 2, 4 и 5 са решени по дваж всеки. На четвъртата стъпка
решава пъзели 3 и 4. Петата повтаря стъпки 3 (която пък повтаря
1 и 2) и 4, така че ефектът на стъпка 5 е всъщност еднократн