CYCLE - Cycles, More Cycles
A m-cycle in a directed graph is defined to be a sequence of vertices v0-v1-v2-v3-...-vm where an edge (vi, vi+1) exists for each 0 <= i < n, vi != vj for all 0 <= i < j < m and vm = v0. For a given graph of n vertices we can count the number of cycles in it. Now you task is a little harder: find the maximum value among all graphs with certain constraints, that is, your graph should contain an edge from either vertex x to y or y to x, but not both.
Assume there are R m-cycles in your output, your solution will be awarded by w * R points, where w is related to n and m. Your score will be the sum of scores of all test cases. Note your source must not be larger than 10000 bytes.
Input
One line containing two blank-separated integers, n and m, where 3 <= m <= n <= 17.
Output
Adjacent matrix A of the graph you found. Numbers must be separated by spaces. Edge (i, j) exists when and only when Aij = 1. Aij + Aji <= 1 and Aii = 0 for any 0 <= i, j < n, or your solution will be judged as wrong answer.
Example
Input:
3 3
Output:
0 0 1
1 0 0
0 1 0
Assume w = 0.2, this solution will get 0.2 * 1 = 0.2 points for this case.
hide comments
Robert Gerbicz:
2011-03-29 05:49:59
Yes. |
|
Wolfram:
2011-03-29 05:49:59
In a cycle, must v_0, v_1, v_2, ..., v_{m-1} all be different? |
|
Tony Beta Lambda:
2011-03-29 05:49:59
Note: the author's solution is about 20 lines long and gets about 300000 points. Last edit: 2010-08-29 08:12:38 |
Added by: | Tony Beta Lambda |
Date: | 2010-08-10 |
Time limit: | 0.200s-3.400s |
Source limit: | 10000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: PERL6 |
Resource: | Yau-awards 2008 |