Дан двумерный массив целых чисел n × m, все элементы которого — нули или единицы. Найти в нём наибольший по площади квадрат, состоящий только из единиц. Гарантируется, что в нём есть хотя бы одна единица.
Вводятся два целых числа n и m (1 ≤ n, m ≤ 1000), а потом n строк по m чисел 0 или 1 — элементы массива.
Вывести три числа — длину стороны квадрата и координаты его левого верхнего угла.
1 1 1
1 1 1
3 5 1 1 0 0 0 1 1 1 1 1 0 0 0 1 1
2 1 1
Экзамен по берляндскому языку проходит в узкой и длинной аудитории. На экзамен пришло N студентов. Все они посажены в ряд. Таким образом, позиция каждого человека задается координатой на оси Ox (эта ось ведет вдоль длинной аудитории). Два человека могут разговаривать, если расстояние между ними меньше или равно D. Какое наименьшее количество типов билетов должен подготовить преподаватель, чтобы никакие два студента с одинаковыми билетами не могли разговаривать? Выведите способ раздачи преподавателем билетов.
В первой строке входного файла содержится два целых числа N, D (1 ≤ N ≤ 10000; 0 ≤ D ≤ 106). Вторая строка содержит последовательность различных целых чисел X1, X2, ..., XN, где Xi (0 ≤ Xi ≤ 106) обозначает координату вдоль оси Ox i-го студента
В первую строчку выходного файла выведите количество вариантов, а во вторую, разделяя пробелами, номера вариантов студентов в том порядке, в каком они перечислены во входном файле.
4 1 11 1 12 2
2 1 1 2 2
4 0 11 1 12 2
1 1 1 1 1
Дана возрастающая последовательность целых чисел 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, ... Она сформирована следующим образом: берется одно нечетное число, затем два четных, затем три нечетных и так далее. Выведите \(N\)-й элемент этой последовательности.
Одно целое число \(N\) (1 \(\le\) \(N\) \(\le\) 10100).
Выведите одно целое число - \(N\)-й элемент последовательности.
1
1
4
5
Всем известно, что основной целью любого крупного правительственного проекта во Флатландии является освоение бюджетных средств (разумеется, по назначению). В настоящее время во Флатландии ведется работа над m национальным проектами, i-й проект может освоить \(s_i\) миллионов Флатландских тугриков в день.
Правительство Флатландии планирует выделить \(n\) грантов для финансирования проектов, каждый по p миллионов Флатландских тугриков. Деньги i-го из грантов будут доступны для освоения, начиная с дня \(r_i\). Когда очередной грант становится доступен для освоения, его можно отдать некоторому проекту. Этот проект осваивает деньги гранта в течение \(\lceil\frac{p}{s_i}\rceil\) дней. Проект не может одновременно осваивать деньги нескольких грантов.
Премьер-министр Флатландии господин Тупиков хочет выяснить, за какое время удастся освоить все деньги, выделенные в рамках грантов. Помогите ему выяснить самый ранний день, когда можно полностью освоить все деньги грантов.
Первая строка входного файла "budget.in" содержит числа m, n и p (1 ≤ m ≤ 100, 1 ≤ n ≤ 100, 1 ≤ p ≤ \(10^9\)). Вторая строка содержит m целых чисел: \(s_1\), \(s_2\), . . . , \(s_m\) (1 ≤ \(s_i\) ≤ \(10^9\)). Третья строка содержит n целых чисел: \(r_1\),\(r_2\),...,\(r_n\) (1 ≤ ri ≤ \(10^9\)).
Первая строка выходного файла "budget.out" должна содержать одно целое число — минимальный день, к которому можно полностью освоить все деньги грантов.
Одна из возможных оптимальных схем освоения устроена следующим образом: грант 1 отдается первому проекту, который осваивает его в течение 11 дней. Остальные гранты отдаются второму проекту, грант 2 осваивается в течение дней 3–7, грант 3 в течение дней 8–12 и грант 4 в течение дней 13–17. Заметим, что грант 4 появляется в день 12, но назначается только в день 13.
2 4 22 2 5 1 3 8 12
17
Империя обнаружила мятежников на ледяной планете Хот! По сведениям разведки все командование Альянса Повстанцев сейчас скрывается на базе «Эхо», спрятанной в горах на севере этой суровой планеты.
Для того, чтобы окончательно подавить силы восстания, необходимо в ходе стремительной атаки уничтожить эту базу и скрывающихся на ней мятежников. К сожалению, укрытие хорошо укреплено: в частности, его защищает мощное силовое поле, препятствующее бомбардировкам с орбиты. Силовое поле имеет форму выпуклого многоугольника с вершинами в N специальных станциях-ретрансляторах. Никакие три станции не располагаются на одной прямой.
Перед тем как начинать операцию по уничтожению повстанцев, требуется лишить их базу силового поля, уничтожив эти N станций точечным бомбометанием. Однако точные координаты этих станций нам неизвестны. Ваша цель — узнать расположение станций-ретрансляторов, чтобы наши войска смогли начать наступление.
На планете введена система координат, устроенная таким образом, что все станции-ре-транс-ля-торы находятся в точках с целыми координатами, не превосходящими C по модулю.
В вашем распоряжении есть зонд-разведчик, оснащенный специальным оборудованием, позволяющим регистрировать станции-ретрансляторы. Если запустить его по прямой над базой повстанцев, по его информации можно будет узнать, сколько станций-ретрансляторов располагаются слева, и сколько — справа от прямой его движения. Станции, находящиеся на его пути, зонд не регистрирует.
С повстанцами надо расправиться как можно скорее: у вас есть время не более чем на 105 запусков этого зонда. Восстановите по полученной от него информации точные координаты станций-ретрансляторов, чтобы мы могли начать наступление, и Империя вас не забудет!
Это интерактивная задача.
При запуске решения на вход подаются два целых числа N (3 ≤ N ≤ 1 000) и C (5 ≤ C ≤ 1 000 000) — количество станций и ограничение на абсолютную величину их координат.
На каждый запуск зонда-разведчика вводится полученная им информация — два целых числа l и r, разделенных пробелом, — количество станций-ретрансляторов слева и справа от траектории его движения соответственно.
Для запуска зонда выведите строку «? x1 y1 x2 y2», где (x1, y1) и (x2, y2) — две точки с целочисленными координатами, лежащие на прямой, по которой должен лететь зонд. Зонд будет лететь в направлении от первой точки ко второй. Точки не должны совпадать. Координаты точек не должны превосходить 5C по модулю.
Как только вы найдете ответ, выведите строку «Ready!», и в следующих N строках выведите координаты станций в любом порядке. После этого ваша программа должна завершиться.
4 5
0 4
0 3
0 3
0 2
1 1
3 1
3 0
3 0
? -1 3 1 3
? -1 2 1 2
? -1 1 0 2
? -1 0 0 2
? 0 0 0 2
? 1 0 1 2
? 2 0 2 2
? 3 0 1 2
Ready!
0 -1
2 1
0 2
-1 0
В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
Программа не должна делать более 105 запросов запуска зонда. При превышении этого количества, тест будет не пройден с вердиктом «Wrong Answer».
Тесты к этой задаче состоят из четырех групп.
Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
4 5 -1 0 0 -1 2 1 0 2
28