Subset Dynamics


Plus
Pin


Problem description Progress
ID 40084. Dwarf
Темы: Subset Dynamics   

Once the dwarf Quark came across a treasure map. There are N points marked on the map where the treasure can be found. All points are numbered from 1 to N. For each pair of points, Quark knows the length of the road connecting them. Quark starts his search from point number 1. Before starting his long journey, the cunning dwarf crosses out points where, in his opinion, there can be no treasure. It is guaranteed that point number 1 is never crossed out. After that, Quark chooses some route that passes through all the remaining points on the map. The route does not pass through the same point more than once. A quark can only walk on roads that connect uncrossed points.

Quark wants to choose a route of minimum length. It is necessary to find such a route for Quark.

Input
The first line contains one integer N (1 ≤ N ≤ 15) — the number of points marked on the map. The next N lines contain the distances between the points. The (i+1)-th line contains N integers di1,di2, diN — lengths of roads from the i-th point to all the others. It is guaranteed that dij=dji, dii=0 and 0 <dij <100 . The (N+2)th line contains one integer Q (1 < Q ≤ 1000) — the number of options for deleting points for this map. The following Q lines contain a description of the options for deletion. The description starts with the number C (0 ≤ C < N) — the number of points where, according to Quark, the treasure cannot be. The next C numbers give the numbers of these points.

Imprint
Print Q lines. In each line print one integer — the length of the minimum route with the corresponding option of deleting points.

Examples
# Input Output
1 3
0  45 10
45 0  30
10 30 0
2
0
1 3 		40
45
2 5
0  14 20 17 14
14 0  15 19 18
20 15 0  15 16
17 19 15 0  14
14 18 16 14 0
2
3 5 4 3
0		 14
58

ID 40085. Permutations
Темы: Subset Dynamics   

Given a set of n different natural numbers. A permutation of elements of this set is called a k-permutation if for any two neighboring elements of this permutation their greatest common divisor is at least k. For example, if the set of elements S = {6, 3, 9, 8} is given, then the permutation {8, 6, 3, 9} is a 2-permutation, and the permutation {6, 8, 3, 9} – no.

The permutation {p1, p2, …, pn} will be lexicographically less than the permutation {q1, q2, …, qn} if there exists a positive integer i (1 ≤ i ≤ n) such that pj= qj when j < i and pi < qi.

As an example, let's order all k-permutations of the above set in lexicographic order. For example, there are exactly four 2-permutations of S: {3, 9, 6, 8}, {8, 6, 3, 9}, {8, 6, 9, 3}, and {9, 3, 6, 8} . Accordingly, the first 2-permutation in the lexicographic order is the set {3, 9, 6, 8}, and the fourth – set {9, 3, 6, 8}.

You are required to write a program that allows you to find the m-th k-permutation in this order.

Input
The input file in the first line contains three natural numbers – n (1 ≤ n ≤ 16), m and k (1 ≤ m, k ≤ 109). The second line contains n distinct natural numbers not exceeding 109. All numbers in the lines are separated by spaces.

Imprint
It is necessary to output the m-th k-permutation of the given set or –1 if there is none in the output file.

Examples
# Input Output
1 4 1 2
6 8 3 9 		3 9 6 8
2 4 4 2
6 8 3 9 		9 3 6 8
3 4 5 2
6 8 3 9 		-1