| 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.
- None three sticks from the set can be used to construct a triangle.
- 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在這海量的數(shù)據(jù)面前也顯得有些蒼白無力，所以只能自己寫字節(jié)讀入函數(shù)來輸入數(shù)據(jù)
我寫的讀入函數(shù)在下面（參考過資料）
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
}
14 }
15 return 1;
16
}
而思路與原來一樣，可是這樣之后的提交就是一次AC 1110ms。
我的優(yōu)化思路還是沒有AC
思路如下：
Dissicion里面說
Fibnacci 函數(shù)來限制sort的范圍因為 1 1 2 3 5 8 13 21 可以是三角形的臨界情況，大概是 F(46)是int的上限
可是一直WA，實在是搞不明白自己哪里錯了。
輸入的時候我提取的最小的兩個數(shù)最大的一個數(shù)的代碼如下
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左右次吧，優(yōu)化思路還是沒有AC，有個牛人要請我吃飯了
posted on 2008-12-22 11:15
KNIGHT 閱讀(438)
評論(1) 編輯 收藏 引用