Темы --> Информатика --> Алгоритмы --> Перебор --> Комбинаторные структуры --> Разные комбинаторные структуры
---> 2 задач <---
Источники --> Командные олимпиады --> ВКОШП
    1999(7 задач)
    2000(8 задач)
    2001(8 задач)
    2002(9 задач)
    2003(9 задач)
    2004(10 задач)
    2005(10 задач)
    2006(10 задач)
    2007(11 задач)
    2008(10 задач)
    2009(11 задач)
    2010(11 задач)
    2011(11 задач)
    2012(11 задач)
    2013(11 задач)
    2014(11 задач)
    2015(11 задач)
    2016(11 задач)
Страница: 1 Отображать по:
#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
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест