同和新媒体矩阵官网同和视频矩阵同和素材矩阵
同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

21017_FullyDiversifiedSequencesofSets

2022-5-16 18:18| 发布者: Hocassian| 查看: 44| 评论: 0|原作者: 肇庆学院ACM合集

摘要:
C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504757976500-Problem List-采集的数据-后羿采集器.html

Pro.ID

21017

Title

Fully Diversified Sequences of Sets

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=21017

AC

0

Submit

620

Ratio

0.00%

时间&空间限制

  • Time Limit: 1500/500 MS (Java/Others)     Memory Limit: 20000/10000 K (Java/Others)

    • 描述

    Given a positive integer n, let N be the set of integers from 1 to n. A finite sequence A1, ..., Ak of subsets of N is fully diversified if: 
    a. Each subset Ai has an even number of elements. 
    b. For each element m in N, there are exactly m sets Ai in the sequence with m as a member. 
    For example, the sequence of subsets {1,3}, {2,3}, {2,3} is a fully diversified sequence of subsets of {1,2,3}. (Note that subsets in the sequence may be the same.) 
    A fully diversified sequence of subsets of N is minimal if no other fully diversified sequence of subsets of N has a smaller sequence count. The example above is minimal since the element 3 must occur in 3 different sets. 
    Write a program, which, given an integer n, determines whether there is a fully diversified sequence of subsets of the corresponding set N and, if there is a fully diversified sequence, finds a minimal fully diversified sequence of subsets of N.

    输入

    The input will be a sequence of positive integers n, one per line followed by a zero (0) (on another line) indicating the end of the input.

    输出

    Description
    Given a positive integer n, let N be the set of integers from 1 to n. A finite sequence A1, ..., Ak of subsets of N is fully diversified if: 
    a. Each subset Ai has an even number of elements. 
    b. For each element m in N, there are exactly m sets Ai in the sequence with m as a member. 
    For example, the sequence of subsets {1,3}, {2,3}, {2,3} is a fully diversified sequence of subsets of {1,2,3}. (Note that subsets in the sequence may be the same.) 
    A fully diversified sequence of subsets of N is minimal if no other fully diversified sequence of subsets of N has a smaller sequence count. The example above is minimal since the element 3 must occur in 3 different sets. 
    Write a program, which, given an integer n, determines whether there is a fully diversified sequence of subsets of the corresponding set N and, if there is a fully diversified sequence, finds a minimal fully diversified sequence of subsets of N.
    Input
    The input will be a sequence of positive integers n, one per line followed by a zero (0) (on another line) indicating the end of the input.
    Output
    If there is no fully diversified sequence of subsets of the corresponding set N, output a 0 on one line followed by a blank line. 
    If there is a fully diversified sequence of subsets of the corresponding set N, output the number of sets in your minimal sequence on one line, followed by the sets, one per line, followed by a blank line. 
    The elements of each set should be output in increasing order with a single space between numbers. The sets of sequences should be output in lexicographical order. There may be many possible solutions to each problem.
    Sample Input
    8
9
11
17
23
0
    Sample Output
    8
1 3 5 6 7 8
2 4 5 6 7 8
2 4 5 6 7 8
3 4 5 6 7 8
3 4 5 6 7 8
6 8
7 8
7 8

0

11
1 5 7 8 9 11
2 5 7 8 10 11
2 5 7 8 10 11
3 5 7 9 10 11
3 6 7 9 10 11
3 6 7 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
5 7 8 9 10 11

0

23
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
12 13 14 15 16 17 18 19 20 21 22 23
13 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
16 17 18 19 20 21 22 23
17 19 20 21 22 23
18 19 20 21 22 23
18 19 20 21 22 23
20 21 22 23
21 23
22 23
22 23
    Hint
    Special Judge
    Source
    Greater New York 2003

    样例输入

    8
9
11
17
23
0

    样例输出

    8
1 3 5 6 7 8
2 4 5 6 7 8
2 4 5 6 7 8
3 4 5 6 7 8
3 4 5 6 7 8
6 8
7 8
7 8

0

11
1 5 7 8 9 11
2 5 7 8 10 11
2 5 7 8 10 11
3 5 7 9 10 11
3 6 7 9 10 11
3 6 7 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
4 6 8 9 10 11
5 7 8 9 10 11

0

23
1 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
9 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23
12 13 14 15 16 17 18 19 20 21 22 23
13 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
14 15 16 17 18 19 20 21 22 23
16 17 18 19 20 21 22 23
17 19 20 21 22 23
18 19 20 21 22 23
18 19 20 21 22 23
20 21 22 23
21 23
22 23
22 23

    提示

    Special Judge


    路过
    雷人
    握手
    鲜花
    鸡蛋
    收藏 邀请

    最新评论

    相关分类

    QQ|Archiver|手机版|小黑屋|同和创作矩阵 ( 粤ICP备20019636号-1 )

    GMT+8, 2025-2-2 08:00 , Processed in 0.017748 second(s), 14 queries .

    Powered by Discuz! X3.4 Licensed

    © 2001-2017 Comsenz Inc.

    返回顶部