• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            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在這海量的數(shù)據(jù)面前也顯得有些蒼白無力,所以只能自己寫字節(jié)讀入函數(shù)來輸入數(shù)據(jù)
             
            我寫的讀入函數(shù)在下面(參考過資料)
             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。
             我的優(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 閱讀(421) 評論(1)  編輯 收藏 引用

            FeedBack:
            # re: POJ 2967 Triangles
            2008-12-25 12:37 | Knight
            思路沒錯,因為寫的時候
            有了min1+min2<=MAX存在了溢出問題。。。。所以WA了
            改了之后排名第四516msAC  回復(fù)  更多評論
              

            只有注冊用戶登錄后才能發(fā)表評論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


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

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲国产成人乱码精品女人久久久不卡| 思思久久99热只有频精品66| 久久精品国产亚洲AV嫖农村妇女| 99久久人妻无码精品系列| 国产精品永久久久久久久久久 | 久久精品国产亚洲αv忘忧草| 久久久久久无码Av成人影院| 国产成人精品久久一区二区三区av | 久久人人爽人人爽人人片AV高清| 久久狠狠高潮亚洲精品| 久久精品国产99久久香蕉| 久久久久久久波多野结衣高潮| 久久精品国产69国产精品亚洲| 午夜精品久久久久久久无码| 国产精品一久久香蕉国产线看| 人人妻久久人人澡人人爽人人精品| 色88久久久久高潮综合影院 | 精品久久久久久亚洲精品 | 久久性精品| 激情伊人五月天久久综合| 久久精品中文字幕一区| 欧洲性大片xxxxx久久久| 人人狠狠综合久久亚洲婷婷 | 久久99亚洲综合精品首页 | 久久天天躁夜夜躁狠狠| 久久久久综合中文字幕| 久久综合狠狠综合久久激情 | 亚洲欧洲精品成人久久曰影片 | 亚洲狠狠久久综合一区77777| 无码国内精品久久人妻| 久久精品成人欧美大片| 一本色道久久88精品综合| 久久久久亚洲国产| 久久精品国产亚洲AV忘忧草18| 欧美精品九九99久久在观看| 热久久视久久精品18| 亚洲午夜无码久久久久小说| 亚洲一区精品伊人久久伊人| 久久人人添人人爽添人人片牛牛| 久久久久久精品成人免费图片| 亚洲级αV无码毛片久久精品|