PKU Judge Online 1013 Counterfeit Dollar

■1013 Counterfeit Dollar

□Problem
12枚の銀貨があり，その内の1つは偽物である．偽物と本物とは重さが違うが，軽いか重いかはわからない．あなたは，天秤を3回用いて幾つかの銀貨の重さを比較し，左の皿に乗せたn枚，右の皿に乗せたn枚，右の皿が上がるor下がるor変わらない，という情報を得た．これより，偽物の銀貨を探し出し，かつ，それが本物より軽いか重いかを判定せよ．

□Solution
解は1つのみある，という制約があるため，12枚の銀貨それぞれが軽いor重い偽物だと想定し，与えられた情報にマッチするか判定するだけ．

□Code

view plainprint?

1. package p1013;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc;  
14.   
15.     final int INF=Integer.MAX_VALUE;  
16.     final double EPS=1e-9;  
17.   
18.     void run(){  
19.         sc=new Scanner(System.in);  
20.         int n=sc.nextInt();  
21.         int[] a=new int[12];  
22.         for(int t=0; t<n; t++){  
23.             Case[] cases=new Case[3];  
24.             for(int j=0; j<3; j++){  
25.                 cases[j]=new Case();  
26.                 String s=sc.next();  
27.                 for(char c : s.toCharArray())  
28.                     cases[j].left.add(c-'A');  
29.                 s=sc.next();  
30.                 for(char c : s.toCharArray())  
31.                     cases[j].right.add(c-'A');  
32.                 s=sc.next();  
33.                 if(s.equals("up"))  
34.                     cases[j].res=-1;  
35.                 else if(s.equals("down"))  
36.                     cases[j].res=1;  
37.                 else  
38.                     cases[j].res=0;  
39.             }  
40.             fill(a, 2);  
41.             for(int j=0; j<24; j++){  
42.                 int coin=j/2;  
43.                 // heavy  
44.                 if(j%2==0)  
45.                     a[coin]=3;  
46.                 // light  
47.                 else  
48.                     a[coin]=1;  
49.                 boolean f=true;  
50.                 for(Case c : cases){  
51.                     int leftSum=0, rightSum=0;  
52.                     for(int i : c.left)  
53.                         leftSum+=a[i];  
54.                     for(int i : c.right)  
55.                         rightSum+=a[i];  
56.                     if(leftSum>rightSum){  
57.                         if(c.res!=-1){  
58.                             f=false;  
59.                             break;  
60.                         }  
61.                     }else if(leftSum<rightSum){  
62.                         if(c.res!=1){  
63.                             f=false;  
64.                             break;  
65.                         }  
66.                     }else{  
67.                         if(c.res!=0){  
68.                             f=false;  
69.                             break;  
70.                         }  
71.                     }  
72.                 }  
73.                 if(f){  
74.                     println((char)(coin+'A')  
75.                             +" is the counterfeit coin and it is "  
76.                             +new String[]{"heavy", "light"}[j%2]+".");  
77.                     break;  
78.                 }  
79.                 a[coin]=2;  
80.             }  
81.         }  
82.     }  
83.   
84.     class Case{  
85.         LinkedList<Integer> left=new LinkedList<Integer>();  
86.         LinkedList<Integer> right=new LinkedList<Integer>();  
87.         // right  
88.         // up=-1, down=1, even=0  
89.         int res;  
90.     }  
91.   
92.     void print(String s){  
93.         System.out.print(s);  
94.     }  
95.   
96.     void println(String s){  
97.         System.out.println(s);  
98.     }  
99.   
100.     public static void main(String[] args){  
101.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
102.         new Main().run();  
103.     }  
104. }  

package p1013;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

    Scanner sc;

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[] a=new int[12];
        for(int t=0; t<n; t++){
            Case[] cases=new Case[3];
            for(int j=0; j<3; j++){
                cases[j]=new Case();
                String s=sc.next();
                for(char c : s.toCharArray())
                    cases[j].left.add(c-'A');
                s=sc.next();
                for(char c : s.toCharArray())
                    cases[j].right.add(c-'A');
                s=sc.next();
                if(s.equals("up"))
                    cases[j].res=-1;
                else if(s.equals("down"))
                    cases[j].res=1;
                else
                    cases[j].res=0;
            }
            fill(a, 2);
            for(int j=0; j<24; j++){
                int coin=j/2;
                // heavy
                if(j%2==0)
                    a[coin]=3;
                // light
                else
                    a[coin]=1;
                boolean f=true;
                for(Case c : cases){
                    int leftSum=0, rightSum=0;
                    for(int i : c.left)
                        leftSum+=a[i];
                    for(int i : c.right)
                        rightSum+=a[i];
                    if(leftSum>rightSum){
                        if(c.res!=-1){
                            f=false;
                            break;
                        }
                    }else if(leftSum<rightSum){
                        if(c.res!=1){
                            f=false;
                            break;
                        }
                    }else{
                        if(c.res!=0){
                            f=false;
                            break;
                        }
                    }
                }
                if(f){
                    println((char)(coin+'A')
                            +" is the counterfeit coin and it is "
                            +new String[]{"heavy", "light"}[j%2]+".");
                    break;
                }
                a[coin]=2;
            }
        }
    }

    class Case{
        LinkedList<Integer> left=new LinkedList<Integer>();
        LinkedList<Integer> right=new LinkedList<Integer>();
        // right
        // up=-1, down=1, even=0
        int res;
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}