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

            1029 Russian Dolls

            TimeLimit : 1 Second   Memorylimit : 32 Megabyte   Special Judge

            Totalsubmit : 68   Accepted : 15

            Russian nesting dolls are brightly painted hollow wooden figures. The dolls in a set have roughly the same shape, typically humanoid, but different sizes. When the set is assembled, the biggest doll contains the second-biggest doll, the second-biggest contains the third-biggest, and so on.

            We can approximate the shape of a doll as a cylinder of height h, diameter d, and wall thickness w. Such a doll would have a hollow of height h-2w and diameter d-2w.

            Boris and Natasha each has a set of dolls. The sets are nearly identical; each has the same number of dolls, which look the same but differ in their dimensions. Last night Boris and Natasha were playing with their dolls and left them in the living room. Their mother tidied them away, dumping them all in one box. Can you help Boris and Natasha separate their sets of dolls?


            Input

            Standard Input will consist of several test cases. The first line of each test case will contain n, the number of dolls in each set (1 < n <= 100). 2n lines follow; each gives the dimensions, h, d, w of a different doll (h,d >= 2w > 0). A line containing 0 follows the last test case.


            Output

            For each test case, separate the dolls into two sets of nesting dolls such that, within each set, the dolls fit within each other, standing straight up, as described above. The first n lines of output should give the dimensions of the dolls in one set, in decreasing order by height. The next line should contain a single hyphen, "-". The next n lines should give the dimensions of the dolls in the second set, also in decreasing order by height. There will always be a solution. If there are many solutions, any will do. Output an empty line between test cases.


            Sample Input

            3
            100 100 3
            97 97 3
            94 94 3
            91 91 3
            88 88 3
            85 85 3
            5
            100 100 1
            97 97 3
            98 98 1
            96 96 1
            94 94 1
            92 92 1
            90 90 1
            88 88 1
            86 86 1
            84 84 1
            0


            Sample Output

            100 100 3
            94 94 3
            88 88 3
            -
            97 97 3
            91 91 3
            85 85 3

            100 100 1
            98 98 1
            96 96 1
            94 94 1
            92 92 1
            -
            97 97 3
            90 90 1
            88 88 1
            86 86 1
            84 84 1



            分別給出2*N個套娃的 高,直徑,內(nèi)壁厚度。
            要求從這2*N個中分出兩套套娃來。
            xjm說是DP,不過我按照我的搜索思路也過了。


            #include <stdio.h>
            #include 
            <algorithm>
            using namespace std;

            struct doll
            {
                
            int h,d,w;    
            }
            ;
            doll all[
            200];
            int a[100],b[100],n;

            bool cmp(doll a,doll b)
            {
                
            if(a.h!=b.h)
                    
            return a.h>b.h;
                
            else
                    
            return a.d>b.d;    
            }


            bool dfs(int p1,int p2,int p)
            {
                
            if(p1==n&&p2==n) return true;
                
            int x;
                
            if(p1==n)
                
            {
                    
            if(p2==0)
                    
            {
                        b[p2]
            =p;
                        p2
            ++;
                        p
            ++;
                        
            if(dfs(p1,p2,p))
                            
            return true;
                        p2
            --;
                        p
            --;
                    }

                    
            else
                    
            {
                        x
            =b[p2-1];
                        
            if(all[x].d-2*all[x].w>=all[p].d&&all[x].h-2*all[x].w>=all[p].h)
                        
            {
                            b[p2]
            =p;
                            p2
            ++;
                            p
            ++;
                            
            if(dfs(p1,p2,p))
                                
            return true;
                            p1
            --;
                            p
            --;    
                        }
                
                    }

                    
            return false;
                }

                
            if(p2==n)
                
            {
                    
            if(p1==0)
                    
            {
                        a[p1]
            =p;
                        p1
            ++;
                        p
            ++;
                        
            if(dfs(p1,p2,p))
                            
            return true;
                        p1
            --;
                        p
            --;
                    }

                    
            else
                    
            {
                        x
            =a[p1-1];
                        
            if(all[x].d-2*all[x].w>=all[p].d&&all[x].h-2*all[x].w>=all[p].h)
                        
            {
                            a[p1]
            =p;
                            p1
            ++;
                            p
            ++;
                            
            if(dfs(p1,p2,p))
                                
            return true;
                            p1
            --;
                            p
            --;    
                        }
                
                    }

                    
            return false;            
                }

                
            if(p1!=0)
                
            {
                    x
            =a[p1-1];
                    
            if(all[x].d-2*all[x].w>=all[p].d&&all[x].h-2*all[x].w>=all[p].h)
                    
            {
                        a[p1]
            =p;
                        p1
            ++;
                        p
            ++;
                        
            if(dfs(p1,p2,p))
                            
            return true;
                        p1
            --;
                        p
            --;
                    }

                }

                
            else
                
            {
                    a[p1]
            =p;
                    p1
            ++;
                    p
            ++;
                    
            if(dfs(p1,p2,p))
                        
            return true;
                    p1
            --;
                    p
            --;
                }

                
            if(p2!=0)
                
            {
                    x
            =b[p2-1];
                    
            if(all[x].d-2*all[x].w>=all[p].d&&all[x].h-2*all[x].w>=all[p].h)
                    
            {
                        b[p2]
            =p;
                        p2
            ++;
                        p
            ++;
                        
            if(dfs(p1,p2,p))
                            
            return true;
                        p2
            --;
                        p
            --;
                    }

                }

                
            else
                
            {
                    b[p2]
            =p;
                    p2
            ++;
                    p
            ++;
                    
            if(dfs(p1,p2,p))
                        
            return true;
                    p2
            --;
                    p
            --;
                }

                
            return false;
            }


            int main()
            {
                
            int i,j;
                
            while(scanf("%d",&n)&&n)
                
            {
                    
            for(i=0;i<2*n;i++)
                        scanf(
            "%d %d %d",&all[i].h,&all[i].d,&all[i].w);
                    sort(all,all
            +2*n,cmp);
                    dfs(
            0,0,0);
                    
            for(i=0;i<n;i++)
                        printf(
            "%d %d %d\n",all[a[i]].h,all[a[i]].d,all[a[i]].w);
                    printf(
            "-\n");
                    
            for(i=0;i<n;i++)
                        printf(
            "%d %d %d\n",all[b[i]].h,all[b[i]].d,all[b[i]].w);
                    printf(
            "\n");            
                }

                
            return 0;    
            }

            posted on 2008-12-31 20:12 KNIGHT 閱讀(320) 評論(0)  編輯 收藏 引用
            <2008年12月>
            30123456
            78910111213
            14151617181920
            21222324252627
            28293031123
            45678910

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            伊人久久五月天| 香蕉久久AⅤ一区二区三区| 亚洲国产精品久久久久久| 精品国产乱码久久久久久浪潮| 国产精品久久国产精品99盘 | 久久人人爽人人爽人人片AV不| 中文精品久久久久人妻不卡| 无码AV波多野结衣久久| 一本色道久久88加勒比—综合| 久久se精品一区二区影院| 日本WV一本一道久久香蕉| 久久99精品久久久久久久不卡| 免费观看久久精彩视频| 久久免费观看视频| 99精品久久精品| 中文成人无码精品久久久不卡| 久久精品亚洲日本波多野结衣| 99久久精品国产毛片| 久久综合鬼色88久久精品综合自在自线噜噜| 亚洲午夜久久久久久久久久| 亚洲国产精品婷婷久久| 伊人久久综合无码成人网 | 久久国产免费直播| 91亚洲国产成人久久精品网址| 中文字幕久久亚洲一区| 国产精品欧美久久久天天影视 | 久久国产精品-国产精品| 久久亚洲国产成人影院网站| 久久亚洲AV成人无码国产| 性高湖久久久久久久久AAAAA | 久久水蜜桃亚洲av无码精品麻豆| 久久久精品久久久久久| 久久精品国产亚洲沈樵| 香蕉久久夜色精品升级完成| 久久伊人五月天论坛| 国产精品无码久久久久| 久久99国产精品一区二区| 久久久久久夜精品精品免费啦| 久久妇女高潮几次MBA| 狠狠色丁香久久婷婷综合蜜芽五月| 久久久久久国产精品无码下载 |