posts - 74,  comments - 33,  trackbacks - 0
 
Time Limit: 3000MS Memory Limit: 65536K
Total Submissions: 5593 Accepted: 878

Description

triDesign company produces different logical games and puzzles for children. One of the games called triSuper is basically a set of sticks. The length of a stick is measured in millimeters and some of sticks in a set may be of the same length.

Authors of the game think for some reason that a child being given a triSuper game set uses the sticks to construct triangles. Doing so, the child will eventually realize that it is not always possible to construct a triangle from any three sticks. This is the educational value of the game – to study “the inequality of a triangle”.

A particular feature of the game is that each game set is unique. Furthermore, each game set is tested after production. The game set is rejected if it breaks any of the following rules.

  1. None three sticks from the set can be used to construct a triangle.
  2. Any three sticks from the set can be used to construct a triangle.

As far as a game set may contain a lot of sticks, it is necessary to develop special program to help testing game sets. This is what you need to do.

Input

The input describes one game set. The first line of the input contains an integer number N (1 ≤ N ≤ 1 000 000). The second line contains N integer numbers A1, A2, …, AN, separated by spaces (1 ≤ Ai ≤ 2 000 000 000). Ai is the length of the stick number i in the set. Sticks in the set a so thin, that you can disregard their thickness.

Output

The output has to contain a single line. If a game set is rejected than the line is “The set is rejected.”. Otherwise, the line is “The set is accepted.”

Sample Input

sample input #1
3
1 2 3
sample input #2
4
4 4 4 4
sample input #3
4
1 2 3 4

Sample Output

sample output #1
The set is rejected.
sample output #2
The set is rejected.
sample output #3
The set is accepted.

如果说这是道水题的话,前提是你能提高输入的效率!
C++的cin肯定是不行的,C的scanf在这海量的数据面前也显得有些苍白无力,所以只能自己写字节读入函数来输入数据
 
我写的读入函数在下面(参考过资料)
 1int in(int a)
 2{
 3    int sum=0;
 4    char ch;
 5    getchar();
 6    while((ch=getchar())!=EOF)
 7    {
 8        if(ch<='9'&&ch>='0')sum=sum*10+ch-'0';
 9        else 
10        {
11            s[a++]=sum;
12            sum=0;    
13        }

14    }

15    return 1;    
16}

而思路与原来一样,可是这样之后的提交就是一次AC 1110ms。
 我的优化思路还是没有AC
思路如下:
Dissicion里面说Fibnacci 函数来限制sort的范围因为 1 1  2  3  5  8  13  21 可以是三角形的临界情况,大概是 F(46)是int的上限
可是一直WA,实在是搞不明白自己哪里错了。
输入的时候我提取的最小的两个数最大的一个数的代码如下
 1 int in(int a)
 2 {
 3     int sum=0;
 4     char ch;
 5     getchar();
 6     while((ch=getchar())!=EOF)
 7     {
 8         if(ch<='9'&&ch>='0')sum=sum*10+ch-'0';
 9         else 
10         {
11             s[a++]=sum;
12             sum=0;
13             if(s[a-1]>Max)Max=s[a-1];
14             if(s[a-1]<min1)
15             {
16                 min2=min1;
17                 min1=s[a-1];
18             }
19             else if(s[a-1]<min2)min2=s[a-1];    
20         }
21     }
22     return 1;    
23 }

提交很多次大概有40左右次吧,优化思路还是没有AC,有个牛人要请我吃饭了
posted on 2008-12-22 11:15 KNIGHT 阅读(412) 评论(1)  编辑 收藏 引用

FeedBack:
# re: POJ 2967 Triangles
2008-12-25 12:37 | Knight
思路没错,因为写的时候
有了min1+min2<=MAX存在了溢出问题。。。。所以WA了
改了之后排名第四516msAC  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2008年12月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(8)

随笔档案

文章档案

Friends

OJ

搜索

  •  

最新评论

阅读排行榜

评论排行榜