Страница: << 30 31 32 33 34 35 36 >> Отображать по:
#1920
Квадратик
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

На клетчатом поле \(N\times N\), некоторые клетки которого закрашены, требуется найти размер максимального квадрата, состоящего из закрашенных клеток.

Входные данные

В первой строке входного файла содержится единственное целое число \(N\) (\(1\le N\le 3\,000\)). В каждой из следующих \(N\) строк содержится по \(N\) символов «#» и «.» (соответствующих закрашенным и незакрашенным клеткам соответственно), описывающих таблицу.

Выходные данные

Выведите единственное целое число — максимальный размер полностью закрашенного квадрата.

Система оценки

Каждая программа тестируется на четырёх тестах:

чтобы пройти первый тест, достаточно написать решение, работающее за \(O(N^5)\), чтобы пройти второй, требуется решение уже за \(O(N^4)\), третий — за \(O(N^3)\), четвёртый — за \(O(N^2\log N)\).

За каждый успешно пройденный тест начисляется 25 баллов.

Посылка, набирающая \(x\) баллов по сумме баллов за тесты, считается принятой, если выполняются следующие два условия:

* во-первых, если \(x>25\), должна существовать более ранняя принятая посылка, балл за которую по сумме баллов за тесты равен \(x-25\),

* во-вторых, программа не должна содержать отсечений по \(N\), искусственных замедлений работы и т. п.

Если посылка не принята, через некоторое время после её отправки результат её проверки станет «Дисквалифицирован». Балл за принятую попытку вычисляется как сумма баллов за каждый тест минус 5 баллов за каждую более раннюю дисквалифицированную посылку.

Задача считается решённой, если существует принятая посылка, получившая не менее 100 баллов.

Проще говоря, нужно честно последовательно сдать сначала решение, проходящее только первый тест, затем решение, проходящие первые два теста, затем — все тесты, кроме последнего, и, наконец, решение, проходящее все тесты. При этом допускаются ошибки в программах, уменьшающие балл, но для каждой асимптотики должно быть сдано хотя бы одно своё верное решение.

#1924
Булева функция
  
ограничение по времени на тест
4.0 second;
ограничение по памяти на тест
64 megabytes

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция \(f\) сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции \(f\).

Если задана булева функция \(f\) и набор из \(N\) булевых значений \(a_1,a_2,\ldots,a_N\), то результат цепного вычисления этой булевой функции определяется следующим образом:

* если \(N=1\), то он равен \(a_1\);

* если \(N>1\), то он равен результату цепного вычисления булевой функции \(f\) для набора из \((N-1)\) булевого значения \(f(a_1,a_2),a_3,\ldots,a_N\), который получается путём замены первых двух булевых значений в наборе из \(N\) булевых значений на единственное булево значение — результат вычисления функции \(f\) от \(a_1\) и \(a_2\).

Например, если изначально задано три булевых значения: \(a_1=0\), \(a_2=1\), \(a_3=0\), а функция \(f\) — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию \(f\) и попросила одного из учеников выбрать такие \(N\) булевых значений \(a_i\), чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно бо́льшим.

Требуется написать программу, которая решала бы поставленную учительницей задачу.

Входные данные

Первая строка входного файла содержит одно натуральное число \(N\) (\(2\le N\le100\,000\)).

Вторая строка входного файла содержит описание булевой функции в виде четырёх чисел, каждое из которых — ноль или единица. Первое из них есть результат вычисления функции в случае, если оба аргумента — нули, второе — результат в случае, если первый аргумент — ноль, второй — единица, третье — результат в случае, если первый аргумент — единица, второй — ноль, а четвёртый — в случае, если оба аргумента — единицы.

Выходные данные

В выходной файл необходимо вывести строку из \(N\) символов, определяющих искомый набор булевых \(a_i\) с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу «No solution».

Пояснения к примерам

В первом примере процесс вычисления цепного значения булевой функции \(f\) происходит следующим образом: \(1011\to111\to01\to1\)

Во втором примере вычисление цепного значения булевой функции \(f\) происходит следующим образом: \(11111\to0111\to111\to01\to1\)

В третьем примере получить цепное значение булевой функции \(f\), равное 1, невозможно.

Примеры
Входные данные
4
0110
Выходные данные
1011
Входные данные
5
0100
Выходные данные
11111
Входные данные
6
0000
Выходные данные
No solution
#1938
ЕГЭ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

С целью упрощения ЕГЭ по литературе, было решено оставить в нем вопросы только с ответами «да» или «нет». Бланк ответов представляет клетчатое поле из \(N\) строк и \(M\) столбцов, в котором каждая клеточка соответствует своему вопросу. Ученику необходимо один раз перечеркнуть по диагонали те клеточки, которые, по его мнению, соответствуют вопросам с ответом «нет» (перечеркивать можно по любой из двух диагоналей). При этом во избежание ошибок при сканировании, никакие две диагонали не должны "сливаться", то есть иметь общий конец.

Авторам варианта необходимо знать, какое наибольшее количество вопросов с ответом «нет» можно вставить в вариант, чтобы бланк с правильными ответами мог быть верно распознан компьютером.

Входные данные

Вводится два натуральных числа – количество строк \(N\) и количество столбцов \(M\). Количество вопросов в варианте не превосходит 100, то есть \(1 ≤ N ∙ M ≤ 100\).

Выходные данные

В первую строку выведите одно число — максимальное количество вопросов с ответом «нет», которое можно включить в вариант. В следующие N строк выведите по M символов – пример такого бланка с правильными ответами, верно распознаваемый компьютером. Никакие две диагонали не должны иметь общих концов. Руководствуйтесь следующими обозначениями: . (точка) — пустая клетка, соответствующая ответу «да»; / или \ — перечеркнутые по диагонали справа налево или слева направо клетки, соответствующие ответу «нет». Если существует несколько вариантов заполнения бланка, выведите любой.

Примеры
Входные данные
1 1
Выходные данные
1
/
Входные данные
2 1
Выходные данные
2
/
/
Входные данные
3 3
Выходные данные
6
///
../
\\.
#1942
Авангардная архитектура
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Один из столичных девелоперов решил построить жилой дом по проекту известного авангардного архитектора. Жилой дом будет состоять из квартир-кубиков и иметь причудливую форму. Есть два ограничения, одно из которых наложено архитектором, а второе — законами физики.

Архитектор хочет, чтобы каждый этаж представлял собой связанную последовательность кубиков (разделенные этажи — это мода 1990х). В то же время необходимо, чтобы хотя бы под одним из кубиков этажа находился кубик предыдущего этажа. Первый этаж должен опираться о землю.

Кроме законов физики архитектора ограничивает также необходимость все это творчество продать. Поскольку покупатели неохотно покупают недвижимость, необходимо привлечь их хоть чем-нибудь, в частности, видом из окна. Специалисты компании-девелопера составили таблицу, в которой для каждого возможного расположения квартиры указана привлекательность вида из окна для этого расположения. Необходимо максимизировать суммарную привлекательность видов из окна.

В приведенном примере показаны привлекательности видов из окна и наилучшее здание из 10 кубиков в данном случае.

По известному количеству кубиков и таблице привлекательности видов из окна вам необходимо выбрать лучший проект (с максимальной суммарной привлекательностью), удовлетворяющий условиям архитектора и законам физики.

Входные данные

В первой строке входного файла указаны натуральные числа \(N\), \(H\) и \(W\) (1 ≤ \(H\) ≤ 30, 1 ≤ \(W\) ≤ 30, 1 ≤ \(N\) ≤ \(HW\)) — количество имеющихся кубиков, максимальная высота и максимальная ширина здания. Следующие H строк содержат по \(W\) натуральных чисел, задающих привлекательность соответствующего расположения квартиры. Привлекательность измеряется в пределах от 1 до 100 000 включительно.

Выходные данные

Выведите одно число — наибольшую суммарную привлекательность.

Примеры
Входные данные
10 6 7
9 3 6 4 8 1 3
2 9 2 5 3 2 6
1 1 8 4 6 5 4
1 9 6 5 3 4 5
6 2 5 6 7 1 2
2 6 7 5 6 4 3
Выходные данные
65
#1979
Контрольная работа
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Студенты пришли на занятия в большую аудиторию и все сели на какие-то места первого ряда аудитории. Пришедший преподаватель объявил, что сейчас состоится контрольная работа, и решил пересадить студентов так, чтобы никакие два студента не сидели на двух подряд идущих местах (чтобы между любыми двумя студентами всегда было как минимум одно свободное место).

Помогите преподавателю пересадить минимальное число студентов, чтобы достичь нужного результата.

Входные данные

Сначала вводится натуральное число N — количество мест в первом ряду аудитории, а затем число K — количество студентов. Далее в порядке возрастания перечислены номера мест, на которые студенты сели изначально (все места пронумерованы числами от 1 до N).

1 ≤ K ≤ 1000, 2K–1 ≤ N ≤ 109.

Выходные данные

Выведите одно число — минимальное количество студентов, которых придется пересадить.

Решение для n <= 15 будет набирать 30 баллов, для n <= 3000 будет набирать 60 баллов.

Примеры
Входные данные
7 4
2 4 6 7
Выходные данные
3
Входные данные
8 4
2 4 6 7
Выходные данные
1
Страница: << 30 31 32 33 34 35 36 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест