Welcome   HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online
Home
FAQs
Problem Set
Practices
Online Contests
Major Exercises
OI Special
Judgement
Submit
Online Status
User Ranklist
Users
Register new
Login
Web Links
Hunan Normal University
College of Mathematics and Computer Science
检查次品
Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:32768KB
Total submit users: 2, Accepted users: 0
Problem 10014 : Special judge
Problem description
  ACM公司最近收到很多投诉,说他们生产的产品中含有次品。这些次品从外形上看与正品没有区别,只有重量不同。
公司决定把次品找出来。ACM公司的产品装在包装盒中,每个包装盒中包装了N个产品(N=(3n-1)/2,n是一个正整数)。而且每个包装盒中只有一个次品。
现在公司准备派出人员把次品收回,给他们每人一个可以称量任意多个产品但无砝码和刻度的天平,以及一个具有标准重量的产品。还需要准备一个手册,告诉他们如何找出次品。
派出的人员不都是数理逻辑专家,如果不告诉他们如何找次品,他们会把产品一个一个的与标准产品在天平上比较,直至找到次品。显然这样的效率太低。
作为公司的顶级八卦数理逻辑专家,你被要求编写这样的手册。要求在知道包装盒中产品的数目,就给出一个找次品的方案。
当然,所有的产品都作了编号,从1到N,标准产品被编为0号。
即使这样,这个工作也很繁琐,你决定编写程序解决它。

Input
  输入有多组测试数据,每组测试数据占据一行。
每行只有一个正整数N,表示产品总数。(N<300000)
最后一行是一个0,表示输入结束且不要处理。

Output
  每组测试数据的输出都由三个部分组成:
第一部分只有一行,输出最少需要称量的次数k;
第二部分k行,是称量方案。每一行是一次称量,包含偶数个非负整数,前半部分是放在天平左端的产品编号,后半部分是放在天平右端的产品编号,每个数字间用空格隔开;
第三部分N行,是一个寻找次品的表。每一行分三个部分:首先是产品编号,空格后是该编号产品是次品且重量比标准重量重的情况下的k次称量结果:如果左边重,记为'>',右边重,记为'<',平衡,记为'='。最后是该编号产品是次品且重量比标准重量轻的情况下的k次称量结果。第三部分要按照产品编号升序输出。
每组测试数据的输出用一个空行隔开。

Sample Input
4
1
0
Sample Output
2
0 4 1 2
2 4 0 3
1 <=>=
2 <>><
3 =<=>
4 >><<

1
0 1
1 <>
Judge Tips
  解释样例的第一个测试数据的输出:
输入N是4,输出的k是2,表示需要2次称量;
下面2行是称量方案,第一次0,4号左边,1,2号右边,第二次2,4号左边,0,3号右边;
后面四行是查找表。如果称量结果是第一次左边轻,第二次平衡,则次品是1号且较重;


Problem Source
  DR.Wu

Submit   Discuss   Judge Status  Problems  Ranklist 

HUNAN NORMAL UNIVERSITY ACM/ICPC Judge Online, Version 2010.5.5.final.
Web visits:5910 today,10454011 total, since 2010-05-07