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.

    设有n个互不相同的正整数{X1,X2,…Xn},任取两个Xi,Xj(i≠j),能算出Xi+Xj。现在所有取法共n*(n-1)/2个和,要你求出X1,X2,…Xn。

    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: 复制
    4
    3 5 4 7 6 5
    输出样例#1: 复制
    1
    1 2 3 4

    说明

    设有n个互不相同的正整数{X1,X2,…Xn},任取两个Xi,Xj(i≠j),能算出Xi+Xj。现在所有取法共n*(n-1)/2个和,要你求出X1,X2,…Xn。

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。