• <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>

            Problem F : Glenbow Museum

            The famous Glenbow Museum in Calgary is Western Canada’s largest museum, with exhibits ranging from art to
            cultural history to mineralogy. A brand new section is being planned, devoted to brilliant computer programmers just
            like you. Unfortunately, due to lack of space, the museum is going to have to build a brand new building and relocate
            into it.

            The size and capacity of the new building differ from those of the original building. But the floor plans of both
            buildings are orthogonal polygons. An orthogonal polygon is a polygon whose internal angles are either 90° or 270°.
            If 90° angles are denoted as R (Right) and 270° angles are denoted as O (Obtuse) then a string containing only R and
            O can roughly describe an orthogonal polygon. For example, a rectangle (Figure 1) is the simplest orthogonal
            polygon and it can be described as RRRR (the angles are listed in counter-clockwise order, starting from any corner).
            Similarly, a cross-shaped orthogonal polygon (Figure 2) can be described by the sequence RRORRORRORRO,
            RORRORRORROR, or ORRORRORRORR. These sequences are called angle strings.

                    Figure 1: A rectangle              Figure 2: A cross-shaped polygon
            Of course, an angle string does not completely specify the shape of a polygon – it says nothing about the length of
            the sides. And some angle strings cannot possibly describe a valid orthogonal polygon (RRROR, for example).

            To complicate things further, not all orthogonal polygons are acceptable floor plans for the museum. A museum
            contains many valuable objects, and these objects must be guarded. Due to cost considerations, no floor can have
            more than one guard. So a floor plan is acceptable only if there is a place within the floor from which one guard can
            see the entire floor. Similarly, an angle string is acceptable only if it describes at least one acceptable polygon. Note
            that the cross-shaped polygon in Figure 2 can be guarded by someone standing in the center, so it is acceptable. Thus
            the angle string RRORRORRORRO is acceptable, even though it also describes other polygons that cannot be
            properly guarded by a single guard.

            Help the designers of the new building determine how many acceptable angle strings there are of a given length.

            Input
            The input file contains several test cases. Each test case consists of a line containing a positive integer L (1≤L≤1000),
            which is the desired length of an angle string.

            The input will end with a line containing a single zero.

            Output
            For each test case, print a line containing the test case number (beginning with 1) followed by the number of
            acceptable angle strings of the given length. Follow the format of the sample output.

            Sample Input
            4
            6
            0

            Output for the Sample Input
            Case 1: 1
            Case 2: 6

                從一個(gè)所有邊都平行于坐標(biāo)系的多邊形的任一頂點(diǎn)出發(fā),逆時(shí)針遍歷,記錄每次經(jīng)過(guò)的頂點(diǎn)處的轉(zhuǎn)角,組成的字符串叫做angle string。求指定長(zhǎng)度的angle string中,能表示至少一個(gè)星形多邊形的串個(gè)數(shù)。 
                顯然當(dāng)l=2k+1時(shí),解不存在;當(dāng)l=2k時(shí),設(shè)m=(l+4)/2,根據(jù)組合數(shù)的知識(shí),所求結(jié)果為C(m,4)+C(m-1,4)。
            400016  2009-04-24 04:51:44  Accepted  0.000  Minimum  19193  C++  4123 - Glenbow Museum
             1 #include <iostream>
             2 using namespace std;
             3 
             4 typedef long long LL;
             5 inline LL cal(LL n){             //C(n,4) 
             6     return n*(n-1)*(n-2)*(n-3)/24;
             7 }
             8 int main(){
             9     int ca=1;
            10     LL n;
            11     while(cin>>n,n){
            12         if(n & 1)
            13             cout<<"Case "<<ca++<<""<<0<<endl;
            14         else{
            15             n=(n+4)>>1;
            16             cout<<"Case "<<ca++<<""<<cal(n)+cal(n-1)<<endl;
            17         }
            18     }
            19     return 0;
            20 }

            posted on 2009-04-24 11:32 極限定律 閱讀(1026) 評(píng)論(0)  編輯 收藏 引用 所屬分類: ACM-ICPC World Final 2008題解

            <2009年7月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(10)

            隨筆分類

            隨筆檔案

            友情鏈接

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久无码av三级| 久久久久无码精品国产app| 影音先锋女人AV鲁色资源网久久 | 久久久亚洲裙底偷窥综合| 国产成人无码精品久久久性色| 久久www免费人成看片| 亚洲一区中文字幕久久| 一级做a爰片久久毛片看看| 久久国产精品无码一区二区三区| 亚洲欧美精品伊人久久| 中文字幕无码久久久| 精品久久久久久中文字幕| 人人狠狠综合久久亚洲| yellow中文字幕久久网| 色狠狠久久AV五月综合| 久久久精品久久久久特色影视| 无码日韩人妻精品久久蜜桃| 久久久久亚洲精品中文字幕| 91精品国产91久久久久福利| 欧美日韩精品久久免费| 久久播电影网| 久久青草国产手机看片福利盒子| 国产亚洲美女精品久久久2020| 久久夜色撩人精品国产| 国产精品久久一区二区三区| 亚洲国产精品无码久久SM| 蜜臀久久99精品久久久久久| 国产精品99久久久久久人| 中文国产成人精品久久不卡 | 91久久福利国产成人精品| 色诱久久久久综合网ywww | 色8激情欧美成人久久综合电| 久久久91精品国产一区二区三区| 久久综合噜噜激激的五月天| 亚洲va国产va天堂va久久| 久久婷婷五月综合色奶水99啪| 久久人人爽人爽人人爽av| 久久国产精品免费一区| 热久久国产欧美一区二区精品| 久久综合久久鬼色| 久久久久亚洲AV无码观看|