Байтмен владеет красивейшим садом в Байттауне, в котором он посадил n роз. Пришло лето, и цветы выросли большими и красивыми. Байтмен понял, что он не в состоянии самостоятельно ухаживать за всеми розами, и решил нанять двух садовников в помощь. В этом случае ему нужно выбрать две прямоугольные области, чтобы каждый из садовников ухаживал за розами в одной их них. Области не должны пересекаться, и в каждой должно быть ровно \(k\) роз.
Байтмен хочет установить забор, огораживающий прямоугольные области. Для экономии денег забор должен быть как можно короче. Ваша задача – помочь Байтмену выбрать две прямоугольные области.
Сад представляет собой прямоугольник длиной \(l\) метров и шириной \(w\) метров, который разделен на \(l\)·\(w\) одинаковых единичных квадратов размером 1x1 метр каждый. Зафиксируем координатную систему так, чтобы оси координат были параллельны сторонам сада. Все квадраты имеют целые координаты (\(x\),\(y\)), удовлетворяющие ограничениям 1 <= \(x\) <= \(l\), 1 <= \(y\) <= \(w\). В каждом единичном квадрате может содержаться любое количество роз.
Стороны прямоугольных областей, которые выбираются, должны быть параллельны сторонам сада, а их угловые единичные квадраты – иметь целые координаты. Прямоугольная область с угловыми единичными квадратами (\(l_1\),\(w_1\)), (\(l_1\),\(w_2\)), (\(l_2\),\(w_1\)) и (\(l_2\),\(w_2\)) (для 1 <= \(l_1\) <= \(l_2\) <= \(l\) и 1 <= \(w_1\) <= \(w_2\) <= \(w\)):
• содержит все единичные квадраты с координатами (\(x\),\(y\)), которые удовлетворяют условию \(l_1\) <= \(x\) <= \(l_2\) и \(w_1\) <= \(y\) <= \(w_2\), и
• имеет периметр 2 · (\(l_2\)−\(l_1\)+1)+ 2 · (\(w_2\)−\(w_1\)+1).
Две прямоугольных области не должны пересекаться, то есть, они не должны иметь ни одного общего квадрата. Даже если они имеют общую сторону или её часть, они ограждаются разными заборами.
Напишите программу, которая:
• читает из стандартного ввода размеры сада, общее количество роз в саду, количество роз, которое должно находиться в каждой прямоугольной области, и позицию каждой розы в саду, определяемую координатами единичного квадрата, в котором она находится;
• находит угловые единичные квадраты двух таких прямоугольных областей с минимальной суммой периметров, которые удовлетворяют заданным условиям;
• выводит в стандартный вывод минимальное значение суммы периметров двух непересекающихся прямоугольных областей, каждая из которых содержит точно заданное количество роз (или единственное слово NO, если такой пары прямоугольных областей не существует).
Первая строка стандартного ввода содержит два числа: \(l\) и \(w\) (1 <= \(l\),\(w\) <= 250), разделенных одним пробелом – длину и ширину сада. Во второй строке задаются два числа: \(n\) и \(k\) (2 <= \(n\) <= 5000, 1 <= \(k\) <= \(n\)/2), записанных через пробел и обозначающих общее количество роз в саду и количество роз, которое должно быть в каждой из прямоугольных областей. Следующие \(n\) строк содержат позиции роз, по одной розе в строке. Каждая (\(i\)+2)-я строка содержит два числа \(l_i\), \(w_i\) (1 <= \(l_i\) <= \(l\), 1 <= \(w_i\) <= \(w\)), разделенных одним пробелом – координаты квадрата, содержащего \(i\)-ю розу.
В одном квадрате может содержаться две или большее количество роз.
В первую и единственную строку стандартного вывода ваша программа должна вывести одно число – минимальную сумму периметров двух неперекрывающихся прямоугольных областей, каждая из которых содержит ровно \(k\) роз, или единственное слово NO, если таких прямоугольников нет.
6 5 7 3 3 4 3 3 6 1 1 1 5 5 5 5 3 1
22
Рассмотрим неубывающую последовательность \(s_1\), ..., \(s_n\) + 1 ( \(s_i\) <= \(s_i\) + 1 для 1 <= \(i\) <= \(n\) ). Последовательность \(m_1\), ..., \(m_n\), в которой каждый член определен как \(m_i\) = ½ * ( \(s_i\) + \(s_i\) + 1 ) для 1 <= \(i\) <= \(n\), назовем “средней последовательностью” для последовательности \(s_1\), ... \(s_n\) + 1. Например, средняя последовательность для последовательности 1, 2, 2, 4 есть 1.5, 2, 3. Заметим, что элементы средней последовательности могут быть дробными числами. Тем не менее, в данной задаче используются только те средние последовательности, в которых все числа целые. Для заданной неубывающей последовательности из \(n\) целых чисел \(m_1\), ..., \(m_n\) необходимо вычислить количество всех неубывающих последовательностей из \(n\) + 1 целых чисел \(s_1\), ..., \(s_n\) + 1, для которых заданная последовательность \(m_1\), ..., \(m_n\) является средней последовательностью.
Напишите программу, которая:
• читает из стандартного ввода неубывающую последовательность целых чисел;
• вычисляет количество всех неубывающих последовательностей целых чисел, для которых заданная последовательность является средней последовательностью;
• выводит ответ в стандартный вывод.
Первая строка стандартного ввода содержит одно целое число \(n\) (2 <= \(n\) <= 5000000). Оставшиеся n строк содержат значения последовательности \(m_1\), ..., \(m_n\). Строка \(i\) + 1 содержит одно целое число \(m_i\) (0 <= \(m_i\) <= 1000000000).
Ваша программа должна вывести в стандартный вывод ровно одно целое число – количество всех неубывающих последовательностей целых чисел, для которых входная последовательность является средней последовательностью.
3 2 5 9
4
В Горном Парке Развлечений открылся новый аттракцион с американскими горками. Трек в аттракционе состоит из n рельсов, соединенных последовательно друг с другом, причем первый рельс начинается на высоте 0. Оператор Байтмэн может изменять конфигурацию трека по своему усмотрению, корректируя наклон некоторых последовательно соединенных рельсов. Наклон остальных рельсов при этом не изменяется. Всякий раз, когда наклон некоторых рельсов изменяется, все следующие за ними рельсы соответственно поднимаются или опускаются. При этом высота начала трека всегда остается равной 0.
Каждый заезд начинается с того, что кабина запускается из начала трека с энергией, достаточной для достижения высоты \(h\) . Иными словами, кабина будет продолжать движение по рельсам, пока ее высота не превысит \(h\) или пока она не достигнет конца трека. Вычислите по записям о всех заездах и изменениях конфигураций трека число рельсов, которые были полностью пройдены кабиной в каждом из заездов до ее остановки.
В аттракционе трек описывается последовательностью из \(n\) наклонов, по одному для каждого рельса. \(i\) -е число \(d_i\) равно разнице высот (в сантиметрах) между концом \(i\) -го рельса и его началом. Иными словами, если после прохождения по первым \(i\) − 1 рельсам кабина оказывается на высоте \(h\) сантиметров, то после прохождения по \(i\) рельсам она будет на высоте \(h\) + \(d_i\) сантиметров. Изначально все рельсы горизонтальны, то есть \(d_i\) = 0 для всех \(i\) . Заезды и изменения конфигурации происходят в течение дня. Каждое изменение конфигурации описывается тремя числами: \(a\) , \(b\) и \(D\) . Такое изменение затрагивает рельсы с \(a\) -го по \(b\) -й (включительно). Наклон каждого из этих рельсов устанавливается равным \(D\) . Иными словами, \(d_i\) = \(D\) для всех \(a\) <= \(i\) <= \(b\) . Каждый заезд задается одним числом \(h\) – максимальной высотой, на которую может подняться кабина.
Напишите программу, которая:
• читает из стандартного ввода последовательность описаний изменений конфигурации трека и заездов,
• для каждого заезда вычисляет количество рельсов, которые пройдены кабиной,
• выводит результаты в стандартный вывод.
Первая строка входных данных содержит одно положительное целое число n – количество рельсов в треке, 1 <= \(n\) <= 1000000000 . Последующие строки содержат описания изменений конфигурации и заездов. Последняя строка входных данных содержит признак окончания. Каждая строка, начиная со второй, может содержать:
• Описание изменения конфигурации трека – один символ ‘I’ и целые числа \(a\) , \(b\) и \(D\) , разделенные одним пробелом (1 <= \(a\) <= \(b\) <= \(n\) , − 1000000000 <= \(D\) <= 1000000000).
• Описание заезда – один символ ‘Q’ и целое число \(h\) ( 0 <= \(h\) <= 1000000000 ), разделенные одним пробелом.
• Один символ “E” – признак окончания входных данных.
Вы можете предполагать, что в каждый момент высота любой точки трека содержится в промежутке [0 , 1000000000] . Входные данные содержат не более 100000 строк.
\(i\) -я строка выходных данных должна содержать единственное целое число – количество рельсов, которые пройдены кабиной в \(i\) -м заезде.
4 Q 1 I 1 4 2 Q 3 Q 1 I 2 2 -1 Q 3 E
4 1 0 3