• <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個套娃的 高,直徑,內壁厚度。
            要求從這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 閱讀(317) 評論(0)  編輯 收藏 引用
            <2025年6月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            293012345

            常用鏈接

            留言簿(8)

            隨筆檔案

            文章檔案

            Friends

            OJ

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            久久偷看各类wc女厕嘘嘘| 久久精品国产亚洲综合色 | 久久91这里精品国产2020| 久久综合欧美成人| 国产精品成人久久久久三级午夜电影| 久久se精品一区二区| 久久精品无码一区二区app| 狠狠色丁香久久婷婷综合蜜芽五月| 2020久久精品亚洲热综合一本| 蜜臀av性久久久久蜜臀aⅴ| 久久本道综合久久伊人| 亚洲伊人久久大香线蕉综合图片| 精品无码久久久久国产| 一本色道久久综合狠狠躁篇| 精品久久久久久久| 久久精品aⅴ无码中文字字幕不卡| 国产精品久久久久久福利漫画| 精品无码久久久久久久动漫| 久久人人爽人人爽人人片av麻烦 | 久久婷婷色香五月综合激情| 久久久一本精品99久久精品88| 久久久久久av无码免费看大片| 熟妇人妻久久中文字幕| 久久影院午夜理论片无码| 99久久777色| 久久综合精品国产二区无码| 无码人妻久久一区二区三区蜜桃| 91精品国产综合久久香蕉| 久久精品国产亚洲精品2020| 成人综合久久精品色婷婷| 久久久久无码国产精品不卡| 9191精品国产免费久久| 久久精品夜夜夜夜夜久久| 少妇熟女久久综合网色欲| 久久人人爽人人爽人人片AV东京热| 国产精品久久国产精品99盘| 99久久人妻无码精品系列| 久久精品人人做人人爽97| 久久精品人成免费| 久久久精品午夜免费不卡| 久久精品国产影库免费看|