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

            Google code jam 2008 R1A - Milkshakes

            Problem

            You own a milkshake shop. There are N different flavors that you can prepare, and each flavor can be prepared "malted" or "unmalted". So, you can make 2N different types of milkshakes.

            Each of your customers has a set of milkshake types that they like, and they will be satisfied if you have at least one of those types prepared. At most one of the types a customer likes will be a "malted" flavor.

            You want to make N batches of milkshakes, so that:

            • There is exactly one batch for each flavor of milkshake, and it is either malted or unmalted.
            • For each customer, you make at least one milkshake type that they like.
            • The minimum possible number of batches are malted.

            Find whether it is possible to satisfy all your customers given these constraints, and if it is, what milkshake types you should make.

            If it is possible to satisfy all your customers, there will be only one answer which minimizes the number of malted batches.

            Input

            • One line containing an integer C, the number of test cases in the input file.

            For each test case, there will be:

            • One line containing the integer N, the number of milkshake flavors.
            • One line containing the integer M, the number of customers.
            • M lines, one for each customer, each containing:
              • An integer T >= 1, the number of milkshake types the customer likes, followed by
              • T pairs of integers "X Y", one for each type the customer likes, where X is the milkshake flavor between 1 and N inclusive, and Y is either 0 to indicate unmalted, or 1 to indicated malted. Note that:
                • No pair will occur more than once for a single customer.
                • Each customer will have at least one flavor that they like (T >= 1).
                • Each customer will like at most one malted flavor. (At most one pair for each customer has Y = 1).
              All of these numbers are separated by single spaces.

            Output

            • C lines, one for each test case in the order they occur in the input file, each containing the string "Case #X: " where X is the number of the test case, starting from 1, followed by:
              • The string "IMPOSSIBLE", if the customers' preferences cannot be satisfied; OR
              • N space-separated integers, one for each flavor from 1 to N, which are 0 if the corresponding flavor should be prepared unmalted, and 1 if it should be malted.

            Limits

            Small dataset

            C = 100
            1 <= N <= 10
            1 <= M <= 100

            Large dataset

            C = 5
            1 <= N <= 2000
            1 <= M <= 2000

            The sum of all the T values for the customers in a test case will not exceed 3000.

            Sample


            Input
             

            Output
             
            2
            5
            3
            1 1 1
            2 1 0 2 0
            1 5 0
            1
            2
            1 1 0
            1 1 1
            Case #1: 1 0 0 0 0
            Case #2: IMPOSSIBLE

            In the first case, you must make flavor #1 malted, to satisfy the first customer. Every other flavor can be unmalted. The second customer is satisfied by getting flavor #2 unmalted, and the third customer is satisfied by getting flavor #5 unmalted.

            In the second case, there is only one flavor. One of your customers wants it malted and one wants it unmalted. You cannot satisfy them both.

            Analysis
            On the surface, this problem appears to require solving the classic problem "Satisfiability," the canonical example of an NP-complete problem. The customers represent clauses, the milkshake flavors represent variables, and malted and unmalted flavors represent whether the variable is negated.

            We are not evil enough to have chosen a problem that hard! The restriction that makes this problem easier is that the customers can only like at most one malted flavor (or equivalently, the clauses can only have at most one negated variable.)

            Using the following steps, we can quickly find whether a solution exists, and if so, what the solution is.

            1. Start with every flavor unmalted and consider the customers one by one.
            2. If there is an unsatisfied customer who only likes unmalted flavors, and all those flavors have been made malted, then no solution is possible.
            3. If there is an unsatisfied customer who has one favorite malted flavor, then we must make that flavor malted. We do this, then go back to step 2.
            4. If there are no unsatisfied customers, then we already have a valid solution and can leave the remaining flavors unmalted.

            Notice that whenever we made a flavor malted, we were forced to do so. Therefore, the solution we got must have the minimum possible number of malted flavors.

            With clever data structures, the above algorithm can be implemented to run in linear time.

            More information:

            The Satisfiability problem - Horn clauses


            Source Code
            #include <iostream>

            using namespace std;

            #define Rep(i,n) for (int i(0),_n(n); i<_n; ++i)

            struct Flavor{
                
            int X;
                
            char Y;
            }
            ;

            struct Customer{
                
            int T;
                Flavor
            * F;
                Customer() 
            {
                    F 
            = NULL;
                }

                
            ~Customer() {
                    
            if(NULL!=F) {
                        delete[] F;
                        F 
            = NULL;
                    }

                }

                
            void Init(int t) {
                    T 
            = t;
                    F 
            = new Flavor[T];
                }

                
            void SetFlavor(int i, int X, int Y) {
                    F[i].X 
            = X;
                    F[i].Y 
            = Y;
                }

                
            int GetFlavorX(int i) {
                    
            return F[i].X;
                }

                
            int GetFlavorY(int i) {
                    
            return F[i].Y;
                }

                
            bool IsSatisfied() {
                    
            return T==0;
                }

                
            void Satisfy() {
                    T
            =0;
                    
            if(NULL!=F) {
                        delete[] F;
                        F 
            = NULL;
                    }

                }

                
            bool IsSatisfing(int i, int *f) {
                    
            return f[F[i].X]==F[i].Y;
                }

                
            void SetMalted(int i, int *f) {
                    f[F[i].X] 
            = 1;
                }

            }
            ;

            int main()
            {
                
            int C;
                FILE 
            *fp = fopen("A.out""w");
                scanf(
            "%d"&C);
                Rep(c, C) 
            {
                    
            int N;
                    scanf(
            "%d"&N);
                    
            int* f = new int[N+1];
                    Rep(i ,N
            +1{
                        f[i]
            =0;
                    }

                    
            int M;
                    scanf(
            "%d"&M);
                    Customer
            * customer = new Customer[M];
                    Rep(m, M) 
            {
                        
            int T;
                        scanf(
            "%d"&T);
                        customer[m].Init(T);
                        Rep(t, T) 
            {
                            
            int X, Y;
                            scanf(
            "%d%d"&X,&Y);
                            customer[m].SetFlavor(t,X,Y);
                        }

                    }

                    
            bool findSolution = true;
                    
            int m = 0;
                    
            while(m<M) {
                        
            if(customer[m].IsSatisfied()) {
                            m
            ++;
                            
            continue;
                        }

                        
            bool malted = false;
                        
            int idx;
                        
            bool satisfied = false;
                        Rep(t, customer[m].T) 
            {
                            
            if(customer[m].GetFlavorY(t)==1{
                                malted 
            = true;
                                idx 
            = t;
                            }

                            
            if(customer[m].IsSatisfing(t,f)) {
                                satisfied 
            = true;
                            }

                        }

                        
            if(!satisfied) {
                            
            if(malted) {
                                customer[m].SetMalted(idx,f);
                                customer[m].Satisfy();
                                m
            =0;
                            }
             else {
                                findSolution 
            = false;
                                
            break;
                            }

                        }
             else {
                            m
            ++;
                        }

                    }

                    fprintf(fp,
            "Case #%d: ", c+1);
                    
            if(findSolution) {
                        Rep(i ,N) 
            {
                            fprintf(fp,
            "%d ", f[i+1]);
                        }

                        fprintf(fp,
            "\n");
                    }
             else {
                        fprintf(fp,
            "IMPOSSIBLE\n");
                    }

                    delete[] customer;
                    delete[] f;

                }

                fclose(fp);
            }

            posted on 2009-08-12 21:17 Chauncey 閱讀(409) 評論(0)  編輯 收藏 引用

            導航

            <2009年8月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            統計

            常用鏈接

            留言簿

            隨筆檔案(4)

            文章檔案(3)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久精品国产亚洲AV不卡| 91精品国产高清久久久久久io | 亚洲欧美日韩精品久久亚洲区| 久久综合亚洲色HEZYO国产| 久久久这里只有精品加勒比| 久久中文字幕人妻丝袜| 国产成人精品久久亚洲高清不卡| 人妻无码精品久久亚瑟影视| 久久66热人妻偷产精品9| 日韩久久无码免费毛片软件| 伊人久久大香线蕉亚洲五月天| 久久免费视频观看| 色偷偷偷久久伊人大杳蕉| 天天做夜夜做久久做狠狠| 久久无码人妻一区二区三区午夜| 国内精品欧美久久精品| 99久久精品影院老鸭窝| 久久青青草原精品国产不卡| 久久精品水蜜桃av综合天堂 | 欧美日韩精品久久久久| 九九久久99综合一区二区| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 久久免费大片| 91精品国产91久久久久久青草| 2021久久国自产拍精品| 香蕉aa三级久久毛片 | 久久久受www免费人成| 久久国产精品久久国产精品| 日韩人妻无码精品久久免费一| 久久受www免费人成_看片中文| 国产精品久久久久9999| 麻豆AV一区二区三区久久| 久久AV无码精品人妻糸列| 伊人 久久 精品| 一本一道久久a久久精品综合| 久久久黄片| 久久婷婷人人澡人人爽人人爱| 久久亚洲国产精品123区| 青草久久久国产线免观| 热久久国产欧美一区二区精品| 欧美大战日韩91综合一区婷婷久久青草|