Гітара#492

Гітара (Розбір)

Автор, розробник, автор розбору: Тимур Дегтеарі

Ця задача вимагає прямого моделювання умов, описаних у заявці. Ми просто проходимо через кожен момент часу і перевіряємо, чи є позиції пальців можливими.

Для кожної секунди від до виконайте наступну перевірку:

  1. Серед трьох значень s_{1,i}, s_{2,i}, s_{3,i} визначте всі позитивні значення (тобто значення, більші за ). Нехай позначає мінімум цих позитивних значень, а - максимум.

  2. Якщо в момент часу немає позитивних значень (всі струни або не грають, або грають відкрито), тоді пан Т може тривіально впоратися з цим моментом—перейдіть до наступної секунди.

  3. В іншому випадку перевірте, чи задовольняється вимога розтягування: y - x \le 3. Якщо ця умова виконується, продовжте до наступної секунди. Якщо вона не виконується, виведіть "Ні" разом з як першим моментом, коли розтягування стає неможливим.

Якщо всі секунд проходять перевірку, виведіть "Так"—пан Т може зіграти всю пісню.

Часова складність: , оскільки ми виконуємо перевірку постійного часу для кожної з секунд.