Условия задач

1. Permutation

Найти перестановку по её номеру в лексикографическом порядке. Сдать задачу.

Входные данные (stdin)

В первой строке входного содержится число N (1 <= N <= 12) – количество элементов (натуральных чисел от 1 до N) в перестановке, во второй – число K (1 <= K <= N!) – порядковый номер перестановки в лексикографическом порядке.

Выходные данные (stdout)

Вывести в строку N чисел через пробел – искомую перестановку.

Пример

входные данные:

3
2

выходные данные:

1 3 2 

2. CheapestPath

Напечатать путь наименьшей стоимости для ориентированного графа. Если таких путей несколько — напечатать любой из них. В случае, если пути не существует, напечатать -1. Сдать задачу.

Входные данные (stdin)

В первой строке содержатся три числа: N, S и F (1≤N≤100, 1≤S, F≤N), где N – количество вершин (обозначаемых натуральными числами от 1 до N) ориентированного графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N неотрицательных целых чисел, не превосходящих 100, образующих матрицу смежности графа, где -1 означает отсутствие дуги между вершинами, а любое неотрицательное число – присутствие дуги данного веса. На главной диагонали матрицы записаны нули. Так, неотрицательное число w в i-й строке и j-м столбце означает наличие дуги из вершины i в вершину j с весом w.

Выходные данные (stdout)

Номера вершин пути через пробел, включая начальную и конечную.

Пример

входные данные:

3 2 1
0 1 1
4 0 1
2 1 0

выходные данные:

2 3 1

3. Diagonal

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

Требования к решению и примеры

В качестве решения требуется отправить один файл, который экспортирует имя Diagonal, и который можно использовать следующим образом (приведен протокол работы с интерактивным интерпретатором Python 2.7.6):

>>> import mod
>>> for p in mod.Diagonal(iter([1,2,3]), iter([5,6])):
...   print p
... 
(1, 5)
(2, 5)
(1, 6)
(3, 5)
(2, 6)
(3, 6)
>>> for p in mod.Diagonal(iter([5,6]), iter([1,2,3])):
...   print p 
... 
(5, 1)
(6, 1)
(5, 2)
(6, 2)
(5, 3)
(6, 3)

4. Expendable

Написать декоратор, который позволяет любому newstyle классу придать следующее свойство: инстанциировать новые объекты этого класса (или любых его подклассов) можно лишь ограниченное число раз, после чего вместо создания объекта выбрасывается исключение ?ValueError. Имя класса должно сохраниться. Сдать задачу.

Требования к решению и примеры

В качестве решения требуется отправить один файл, который экспортирует имя expendable, и который можно использовать следующим образом (приведен незначительно сокращенный протокол работы с интерактивным интерпретатором Python 2.7.6):

>>> import mod
>>> class C(object):
...   pass
... 
>>> c = C()
>>> c = C()
>>> c = C()
>>> @mod.expendable(2)
... class C(object):
...   pass
... 
>>> c = C()
>>> c = C()
>>> c = C()
# ...
ValueError: too many instantiations
>>> c = C()
# ...
ValueError: too many instantiations

5. Undeletable

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

Требования к решению и примеры

В качестве решения требуется отправить один файл, который экспортирует имя Undeletable, и который можно использовать следующим образом (приведен незначительно сокращенный протокол работы с интерактивным интерпретатором Python 2.7.6):

#
# «до»
#
>>> import mod
>>> import gc
>>> class C(object):
...   def __del__(self):
...     print 'C deleted'
... 
>>> c = C()
>>> del c
C deleted
#
# возможен вариант: 
#
>>> c = C()
>>> del c # сходу не удалится
>>> gc.collect() # принудительно вызываем сборку мусора
...
C deleted
#
# «после»
#
>>> class C(mod.Undeletable):
...   def __del__(self):
...     print 'C deleted'
... 
>>> c = C()
>>> del c
>>> gc.collect()
12
>>> gc.collect()
0
>>> gc.collect()
0