P3540 [POI2012]SQU-Squarks

    • 53通过
    • 227提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 贪心 POI 2012 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB


  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示


    A famous Byteotian physicist Byteasar is studying a new constituent of matter - squarks.

    These are quite exotic particles that never exist alone but always in pairs.

    Moreover, squarks of a particular kind form pairs only with squarks of different kinds.

    After years of studies Byteasar has established that there are different kinds of squarks.

    Squarks of each kind have a unique mass, which is a positive integer multiple of (an appropriate) unit.

    Byteasar has also measured the total mass of each of the possible pairs of squarks.

    According to standard Byteotian model of physics, the mass of a pair of squarks equals the sum of the masses of the two squarks forming it.

    Now Byteasar desires to determine the individual masses of squarks of every kind.

    He has asked your help in writing a program that will determine all solutions to this puzzle, i.e., will reconstruct all configurations of squark masses that are consistent with his previous measurements.


    3<=n<=300, 每个正整数不超过10^8



    In the first line of the standard input there is a single integer () that denotes the number of different kinds of squarks.

    In the second line there are positive integers, separated by single spaces, that denote the total masses of all possible pairs of squarks.

    The mass of every pair does not exceed .

    For each two different kinds of squarks, the mass of the pair they form is given on the input exactly once.

      The masses on the input are given in a random order.

    In tests worth 32% of the points the following conditions hold in addition:

    and the mass of every pair of squarks does not exceed .


    In the first line of the standard output your program should print the number of possible solutions to the problem.

    In the lines that follow it should report successive solutions, one per line.

    Each solution should consist of different positive integers, namely the masses of squarks of all kinds.

    In every solution these should be given in increasing order and separated by single spaces.

    Solutions can be reported in arbitrary order, but they cannot be repeated.

    You may assume that for each test data there exists at least one solution, i.e., .


    输入样例#1: 复制
    3 5 4 7 6 5
    输出样例#1: 复制
    1 2 3 4



    3<=n<=300, 每个正整数不超过10^8