Страница: << 53 54 55 56 57 58 59 >> Отображать по:
#111529
простое ЕГЭ
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

Даны два натуральных числа - количество строк N и количество столбцов M. Количество вопросов в варианте не превосходит 100, то есть 1 ≤ N·M ≤ 100.

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

Выведите одно число – максимальное количество вопросов с ответом «нет», которое можно включить в вариант.

Примеры тестов

Входные данные
1 2
Выходные данные
2
Входные данные
3 3
Выходные данные
6

#111636
Древние династии
  

История Татаро-монгольского ханства богата на правителей. Каждый из N правителей принадлежал к одной из двух династий, причём власть часто переходила от одной династии к другой. Каждое восхождение правителя на престол отмечалось праздником, проводимым 26 марта. В летописях зафиксированы годы проведения этих праздников, причем известно, что правители первой династии устраивали для народа праздник кумыса, а второй — праздник мёда.

На конференции по истории Татаро-монгольского ханства каждый из S учёных предложил свою версию толкования летописи. А именно, i-й историк утверждал, что от каждого праздника кумыса до следующего праздника кумыса проходило не менее KLi лет, но не более KRi лет, в то время как от каждого праздника мёда до следующего праздника мёда проходило не менее MLi лет, но не более MRi лет.

Каждой предложенной версии может соответствовать несколько распределений правителей по династиям. Ученые договорились считать показателем сомнительности распределения число переходов власти к представителю той же самой династии.

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

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

В первой строке входного файла записано число N (2 ≤ N ≤ 200 000) — количество праздников в летописи. Следующая строка содержит целые числа X1, X2, ..., XN (1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 109) — годы проведения праздников.

В третьей строке записано число учёных S (1 ≤ S ≤ 50). В каждой из последующих S строк записаны четыре натуральных числа KLi, KRi, MLi, MRi (1 ≤ KLi ≤ KRi ≤ 109), (1 ≤ MLi ≤ MRi ≤ 109).

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

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

Вторая строка должна состоять из N цифр 1 и 2, записанных без пробелов, означающих приход к власти представителя первой или второй династии соответственно. Если существует несколько решений с наименьшим показателем сомнительности Q, выведите любое из них.

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

Примечание

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

  1. Тесты из условия. Подзадача оценивается в 0 баллов.

  2. 2 ≤ N ≤ 15, 1 ≤ S ≤ 10. Подзадача оценивается в 20 баллов.

  3. 2 ≤ N ≤ 2000, 1 ≤ S ≤ 50, N × S ≤ 2000. Подзадача оценивается в 20 баллов.

  4. 2 ≤ N ≤ 10 000, 1 ≤ S ≤ 50, N × S ≤ 10 000. Подзадача оценивается в 20 баллов.

  5. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50, N × S ≤ 200 000. Подзадача оценивается в 20 баллов.

  6. 2 ≤ N ≤ 200 000, 1 ≤ S ≤ 50. Подзадача оценивается в 20 баллов.

Примеры
Входные данные
3
1 2 3
1
1 1 1 1
Выходные данные
1 1
211
Входные данные
4
1 6 9 13
2
1 2 2 3
6 7 3 3
Выходные данные
0
Входные данные
5
3 6 8 9 10
2
2 3 1 1
1 4 1 10
Выходные данные
2 0
21212
#111702
Оптимальная последовательность
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

У нас есть две кучки камней, изначально в каждой по одному камню. За один ход можно добавлять один камень в одну из кучек, если в ней меньше N камней. Игра заканчивается, когда в обеих кучках будет N камней.

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

Например, если в первой кучке 12 камней, а во второй – 7, то позиция хорошая, т.к. число 127 простое.

Ваша задача найти такую последовательность ходов, при которой можно перейти из начальной позиции (1, 1) в конечную (N, N) через максимально возможное число хороших позиций. Например, для N = 4 одна из искомых последовательностей такова: 1; 1 -> 2; 1 -> 3; 1 -> 4; 1 -> 4; 2 -> 4; 3 -> 4; 4

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

Входной файл содержит одно число N. Гарантируется, что 1 ≤ N ≤ 999.

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

Выведите максимально возможное число хороших позиций для данного N (в приведенном примере оно равно трем: 31, 41, 43).

Примеры
Входные данные
4
Выходные данные
3
#111712
Распил брусьев
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Вам нужно распилить деревянный брус на несколько кусков. Компания берет плату за пилку в зависимости от размера бруса, который нужно распилить. За разрезание бруса длиной l берется l у.е.

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

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

В первой строке число L(1 ≤ L ≤ 1000) — начальная длина бруса, следующая строка содержит число распилов n(1 ≤ n ≤ 160), которые нужно сделать. Следующая строка содержит n положительных чисел (0 ≤ ci ≤ L) — места, в которых нужно сделать распилы.

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

Выведите минимальную стоимость распила.

Примеры
Входные данные
10
3
2 4 7
Выходные данные
20
Входные данные
100
3
25 50 75
Выходные данные
200
#111715
Машина арифметика
  
ограничение по времени на тест
3.5 second;
ограничение по памяти на тест
64 megabytes

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

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

Входные данные содержат несколько тестовых случаев (не более 100000). Каждый тестовый случай расположен в отдельной строке и содержит 2 числа, разделённые пробелом: сначала n (1 ≤ n ≤ 1015), а потом m ().

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

Для каждого тестового примера в отдельной строке выведите искомое максимальное произведение.

Примеры
Входные данные
12345 2
12345 3
Выходные данные
6170
2460
Страница: << 53 54 55 56 57 58 59 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест