Дана следующая параллельная программа. Есть N процессов, i-ый процесс исполняет следующий псевдокод:
repeat ni times
yi := y
y := yi + 1
end repeat
Здесь y — общая переменная. Все остальное для каждого процесса является локальным. Каждое действие, записанное на отдельной строке, является атомарным, т. е. когда процесс исполняет некоторую строку, он не может быть прерван. Все остальные чередования возможны, т. е. каждый еще не завершивший свою работу процесс может получить право выполнить очередную строку своего кода. Вначале y = 0. Вам дано целое число W и ni, для i = 1, ... , N. Определите, возможно ли, что после выполнения всех процессов, y = W, и если это возможно, выведите любой порядок выполнения процессов, который приводит к этому.
В первой строке через пробел записаны два целых числа N (1 ≤ N ≤ 100) и W ( - 109 ≤ W ≤ 109). Во второй строке через пробел записано N целых чисел ni (1 ≤ ni ≤ 1000).
В первую строку выведите Yes если возможно, что в конце y = W, или No в противном случае. Если ответ No, второй строки быть не должно, но если ответ Yes, во вторую строку выведите через пробел список целых чисел, описывающих некоторый порядок выполнения процессов, который приводит к нужному результату (см. Примечание).
1 10
11
No
2 3
4 4
Yes
1 1 2 1 2 2 2 2 2 1 2 1 1 1 1 2
3 6
1 2 3
Yes
1 1 2 2 2 2 3 3 3 3 3 3
Предположим, что в коде процессов нет оператора цикла repeat, а код из тела цикла записан нужное число раз. Процессы пронумерованы начиная с 1. Каждое число из списка обозначает, какой процесс выполняет свое очередное действий на данном шаге. Например, рассмотрим порядок 1 2 2 1 3. Первый процесс 1 выполняет свое первое действие, затем процесс 2 свои первые два действия, потом процесс 1 выполняет свое второе действие, далее процесс 3 свое первое действие. Список должен содержать ровно 2·Σ i = 1...N ni чисел.
Название |
---|