PKU Judge Online 1013 Counterfeit Dollar

■1013 Counterfeit Dollar

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

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

□Code

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();
    }
}