Страница: 1 2 >> Отображать по:
#517
Дробь
  
Источники: [ Командные олимпиады, ВКОШП, 2003, Задача B ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Дано выражение p1/p2/.../pn. Требуется определить, сколько различных значений и целых значений оно может принимать при всевозможных расстановках скобок.

Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1\) + \(a_2\) +...+ \(a_n\) и \(a_1\) . \(a_2\) . ... . \(a_n\) не зависит от порядка выполнения в них действий и, следовательно, не меняется при произвольной расстановке в этих выражениях скобок.

В отличие от сложения и умножения, деление – операция не ассоциативная. Так, значение выражения вида \(a_1\)/\(a_2\)/ ... /\(a_n\) может меняться при расстановке в нем скобок.

Рассмотрим выражение вида

\(p_1\)/\(p_2\)/ ... /\(p_n\),

где все \(p_i\) – простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений. Например, выражение 3/2/2 после расстановки скобок может принять два значения: 3/4 = (3/2)/2 и 3 = 3/(2/2).

В первой строке вводится число \(n\) ( 1\( \le\)n\( \le\)200). Следующая строка содержат \(n\) натуральных чисел – \(p_1\), \(p_2\),..., \(p_n\). Все числа \(p_i\) простые и не превосходят \(10^4\).

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

В первой строке выведите количество возможных значений, которые может принять выражение \(p_1\)/\(p_2\)/ ... /\(p_n\) при заданных \(p_i\) после расстановки в нем скобок. Во второй строке выведите количество целых чисел среди этих значений.

Примеры
Входные данные
3
3 2 2
Выходные данные
2
1
#1114
Оптимизация
  
Источники: [ Командные олимпиады, ВКОШП, 2008, Задача G ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

В компании QQQ работает n человек. Очередной проект компании состоит из m независимых частей. Управляющий компании оценил время, которое требуется для выполнения каждой из частей проекта (предполагается, что это время не зависит от того, кто будет выполнять эту часть). После чего он некоторым образом распределил все m частей между n работниками. В результате оказалось, что некоторым из работников потребуется потратить на выполнение своей работы больше времени, чем другим (поскольку им досталась более объемная работа).

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

Например, пусть проект состоит из пяти частей со временами выполнения 3,6,4,8,2, и в компании есть три работника. Пусть распределение работ выглядит следующим образом: первый работник части 1 и 2 (суммарное время 3 + 6 = 9), второй работник часть 4 (суммарное время 8) и третий работник части 3 и 5 (суммарное время 4 + 2 = 6). Тогда если первое задание (назначенное первому работнику) назначить третьему, а пятое задание (назначенное третьему) назначить первому, то у первого работника суммарное время станет равно 6 + 2 = 8, а у третьего 3 + 4 = 7. Поскольку max(9,6) > max(8,7), то эта операция будет оптимизирующей.

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

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

Первая строка входного файла содержит два натуральных числа n и m (1 ≤ n,m ≤ 105) число работников в компании и число частей в проекте соответственно. Вторая строка содержит m натуральных чисел i-ое число равно времени выполнения i-ой части проекта (части проекта нумеруются, начиная с 1). Времена выполнения частей не превосходят 109. Далее идут n строк, описывающих распределение частей по работникам. Каждая строка содержит описание частей проекта, которые получил соответствующий работник. Описание состоит из числа частей, которые достались работнику, и их номеров.

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

В выходной файл выведите искомое число оптимизирующих операций.

Примеры
Входные данные
3 5
3 6 4 8 2
2 1 2
1 4
2 3 5
Выходные данные
2
Входные данные
5 13
1 2 7 5 8 7 5 4 1 5 1 5 7
3 1 2 3
2 4 5
2 6 7
3 8 9 10
3 11 12 13
Выходные данные
5
#1136
Азбука для слепых
  
Требуется определить количество вариантов заполнить таблицу черными и белыми клетками так, чтобы одна фигура не получалась из другой с помощью сдвига.

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

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

Рисунок 1.

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

Требуется подсчитать количество различных букв, которые можно представить таким способом, если прямоугольник имеет размер M∙N.

В качестве примера, все буквы размера 2∙2 приведены на рисунке 2. (Среди комбинаций, отвечающих одной букве, приведена только одна)

Рисунок 2.

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

Входной файл содержит числа M и N, разделенный пробелом. Поскольку человек одновременно не может воспринимать слишком много информации, M∙N ≤ 30.

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

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

Примеры
Входные данные
2 3
Выходные данные
44
#1618
Кодовый замок
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Кодовый замок состоит из \(N\) рычажков, каждый из которых может быть установлен в любое из \(K\) положений, обозначенных натуральными числами от 1 до \(K\). Известно, что для того чтобы открыть замок, нужно, чтобы сумма положений любых трех последовательных рычажков была равна \(K\).

Два рычажка уже установлены в некоторые положения, и их переключать нельзя. Рычажок с номером \(p_1\) установлен в положение \(v_1\), а рычажок \(p_2\) – в положение \(v_2\).

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

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

Вводятся натуральные числа \(N\), \(K\), \(p_1\), \(v_1\), \(p_2\), \(v_2\). 3 ≤ \(N\) ≤ 100 000, 3 ≤ \(K\) ≤ 100 000, \(p_1\) ≠ \(p_2\), 1 ≤ \(p_1\) ≤ \(N\), 1 ≤ \(p_2\) ≤ \(N\), 1 ≤ \(v_1\) ≤ \(K\), 1 ≤ \(v_2\) ≤ \(K\).

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

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

Примеры
Входные данные
3 3 1 1 2 1
Выходные данные
1
Входные данные
3 3 1 1 3 2
Выходные данные
0
#1628
Кодовый замок
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Кодовый замок состоит из \(N\) рычажков, каждый из которых может быть установлен в любое из \(K\) положений, обозначенных натуральными числами от 1 до \(K\). Известно, что для того чтобы открыть замок, нужно, чтобы сумма положений любых трех последовательных рычажков была равна \(K\).

Два рычажка уже установлены в некоторые положения, и их переключать нельзя. Рычажок с номером \(p_1\) установлен в положение \(v_1\), а рычажок \(p_2\) – в положение \(v_2\).

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

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

Вводятся натуральные числа \(N\), \(K\), \(p_1\), \(v_1\), \(p_2\), \(v_2\). Рычажки пронумерованы числами от 1 до \(N\).

3 ≤ \(N\) ≤ 10000, 3 ≤ \(K\) ≤ 6, \(p_1\)≠\(p_2\), 1 ≤ \(p_1\) ≤ \(N\), 1 ≤ \(p_2\) ≤ \(N\), 1 ≤ \(v_1\) ≤ \(K\), 1 ≤ \(v_2\) ≤ \(K\).

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

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

Страница: 1 2 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест