Покраска забора Время: 1000ms, Память: 128MB, Сложность: 15% В одной далекой стране жил был Виталик-Гитарист, да к тому же и народный певец да на дуде игрец. Его мама постоянно заставляла делать дела по дому, и на этот раз она попросила его покрасить забор. Забор состоит из прямоугольных панелей одинаковой длины и единичной ширины. Виталик знает, что мама решила сэкономить на краске и купила самую дешевую, методом экспериментов он смог определить что если нанести краску не менее чем A слоев и не более чем B слоев, забор будет выглядеть как раз нормально. Виталя был достаточно хитер и решил свалить всю работу на младшего брата, который согласился с этим делом. Для простоты брат решил красить забор секциями, нанося на панели забора текущей секции краску в один слой. Завершив покраску секции он произвольно выбирал другую секцию (и не факт, что эта секция не совпадала полностью или частично с уже покрашенной частью забора) и приступал к ее покраске. Таким образом некоторые панели забора он мог покрасить несколько раз, в то время как другие - ни разу. Пока брат красил забор Виталик ушел играть на гитаре и петь свои любимые песни, а когда вернулся, он был повергнут в шок! Местами забор был покрыт очень большим слоев краски, а местами и вовсе не покрашен. К счастью его брат обладал хорошей памятью и помнил какие секции и в каком порядке он красил. Теперь Виталик должен понять сколько панелей забора он не должен переделывать. Чтобы дефекты покраски были менее заметно, брат обязательно покрасил первую и последнюю панели забора. Входные данные: Во входном потоке в первой строке записано натуральное число N (N <= 106) - количество закрашенных секций. Во второй строке - натуральные числа A и B (A, B <= 100) - допустимое количество слоев краски. Далее идет список координат N секций в порядке их окрашивания (номер первой Xi и последней Xj панели забора, составляющее текущую секцию Значения номеров панелей (координат) не превышают 1000. Пример входного файла (input.txt): 4 1 1 1 2 3 4 5 8 3 6 Выходные данные: Вывести единственное число - количество панелей которые не придется перекрашивать Виталику-гитаристу. Пример выходного файла (output.txt): 4
Ответы
Ответить на вопрос
Поделитесь своими знаниями, ответьте на вопрос:
Популярные вопросы в разделе
Написать программу для вывода на экран всех маленьких латинских букв в паскаль
Автор: lionmost6979
Укажи общее понятие a. береза b. москва c. иван грозный. заранее !
Автор: Максим_Нина
Напишите АЯ алгоритм вычисления у по формуле у=(1-х2+5х4)2(степень), где х- заданное число. Учтите следующие ограничения:
1) в арифмитических выражения можно использовать только операции сложения, вычитания и умножения. 2) Каждое выражение может содержать только одну арифметическую операцию. Выполните трассировку алгоритма при х= 2.
у(х) = (1 - х^2 + 5*х^4)^2 - я правильно записал выражение используйте знаки умножения "*" и возведения в степень "^" при записи выражений!
Пусть запись // означает, что последующая часть строки является комментарием.
С учетом ограничений (1) и (2), алгоритм может выглядеть следующим образом:
1. Вычислить tmp1 = х*х // tmp1 = х^2
2. Вычислить tmp2 = tmp1*tmp1 // tmp2 = х^4
3. Вычислить tmp2 = 5*tmp2 // tmp2 = 5*х^4
4. Вычислить tmp1 = 1 - tmp1 // tmp1 = 1 - x^2
5. Вычислить tmp1 = tmp1 + tmp2 // tmp1 = 1 - x^2 + 5*х^4
6. Вычислить y = tmp1*tmp1 // y = (1 - x^2 + 5*х^4)^2
При x = 2 получим:
1. Вычислить tmp1 = 2*2 = 4 // tmp1 = 4
2. Вычислить tmp2 = 4*4 = 16 // tmp2 = 16
3. Вычислить tmp2 = 5*16 = 80 // tmp2 = 80
4. Вычислить tmp1 = 1 - 4 = -3 // tmp1 = -3
5. Вычислить tmp1 = -3 + 80 = 77 // tmp1 = 77
6. Вычислить y = 77*77 = 5929 // y = 5929
Вычислим у(х) при х = 2: y(2) = (1 - 2^2 + 5*2^4)^2 = (1 - 4 - 5*16)^2 = 5929. Т.е. наш алгоритм дает верный результат при х = 2.