Counterfeit Dollar

From Progteam

Revision as of 22:16, 7 September 2009 by Nina (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by nina.



Counterfeit Dollar
Problem Number 1013
Sorter: Uncategorized
Source: Unknown
Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1013



Counterfeit Dollar is problem number 1013 on the Peking University ACM site.

Strategy

1. Have an array of the 12 coins that keeps track of whether they are real or not.
2. Have an array that checks to see if the coins are presently being weighed (usage explained in program).
3a. If the scales are even, all of the coins presently being weighed are real coins.
3b. If the scales are not even, all of the coins NOT being weighed are real coins.
4a. If "up", then the coins on the left scale are potentially heavier, and the coins on the right are potentially lighter.  SO:
     1. If the coin has already been marked as real, ignore it.
     2. If the coin has already been marked as heavy (for example), and we want to mark it as heavy, ignore it.
     3. If the coin has already been marked as light, and we want to mark it as heavy, it is a real coin.
        Why?  Because the coin can't possibly be both heavy and light, so it must be real.
4b. vice versa for "down"
5. By the end, all coins except for one are marked as real, in theory.  Print output.

Code (it's kind of confusing, sorry)

import java.util.*;

public class Main {

    public static Scanner in;
 
    public static void main(String[] args){
        in=new Scanner(System.in);

        doStuff();
    }

    public static void doStuff(){
        int N=in.nextInt();

        for(int i=0;i<N;i++){
            solve();
        }
    }

    public static void solve(){
	int[] theCoins = new int[12]; //array that keeps track of real, heavy, or light
        //if 0, then the coin hasn't marked as anything
        //if 1, then coin is real
        //if -9, then coin is lighter
        //if 9, then coin is heavier
        //these numbers are arbitrary markers

	int index; //index of array

	for(int k=0; k<3; k++) {
                int[] coinsIncluded = new int[12]; //keeps track of which coins are presently being weighed
		String left = in.next();  //read left balance
		String right = in.next(); //read right balance
		String balance = in.next(); //read whether scales balance

		if(balance.equals("even")) { //all the coins being weighed are real!
			for(int i=0; i<left.length(); i++) {
				index = left.charAt(i) - 'A'; //'A' is at index 0
				theCoins[index] = 1; //the coin is real!
				index = right.charAt(i) - 'A';
				theCoins[index] = 1; //the coin is real!
			}
		} else if(balance.equals("up")) {
			for(int i=0; i<left.length(); i++) {
                                //left side is heavier, mark as 9
				index = left.charAt(i) - 'A';
				coinsIncluded[index] = 1; //mark this coin as being weighed
				if(theCoins[index] == 0) { //only mark it as heavy if it has not been flagged yet 
					theCoins[index] = 9;
				} else if(theCoins[index] == -9) { //coin has been marked light, but we're trying to mark it as heavy.
                                                                   //two different weights, therefore must be real
					theCoins[index] = 1;
				}

                                //right side is lighter, mark as -9
				index = right.charAt(i) - 'A';
				coinsIncluded[index] = 1;
				if(theCoins[index] == 0) {
					theCoins[index] = -9;
				} else if(theCoins[index] == 9) { //
					theCoins[index] = 1;
				}

			}
			//mark coins not presently being weighed as real
			for(int i=0; i<12; i++) {
				if(coinsIncluded[i] == 0) { //coin was not included
					theCoins[i] = 1; //mark as real coin
				}
			}
		} else if(balance.equals("down")) {
			for(int i=0; i<left.length(); i++) {
                                //left side is lighter, mark as -9
				index = left.charAt(i) - 'A';
				coinsIncluded[index] = 1;
				if(theCoins[index] == 0) {
					theCoins[index] = -9;
				} else if(theCoins[index] == 9) { //
					theCoins[index] = 1;
				}

                                //right side is heavier, mark as 9
				index = right.charAt(i) - 'A';
				coinsIncluded[index] = 1;
				if(theCoins[index] == 0) {
					theCoins[index] = 9;
				} else if(theCoins[index] == -9) { //
					theCoins[index] = 1;
				}
			}
			//mark coins not included as real
			for(int i=0; i<12; i++) {
				if(coinsIncluded[i] == 0) { //coin was not included
					theCoins[i] = 1; //mark as real coin
				}
			}
		}
	}

	//PRINT WHICH COIN IS FAKE
	char fakeCoin = '0';
	String weight = "";
	for(int i=0; i<12; i++) {
		int coin = theCoins[i]; //get the flag from the coin list
		if(coin < 0) { //fake coin lighter, because it's -9
			fakeCoin = (char)(i + 'A');
			weight = "light";
		} else if (coin > 1) { //fake coin heavier, because it's 9 (and not 1, which means it's real)
			fakeCoin = (char)(i + 'A');
			weight = "heavy";
		}
	
	//	System.out.println(theCoins[i]);
	}

	System.out.println(fakeCoin + " is the counterfeit coin and it is " + weight + ".");

	}
}

Test input

5
BCD FGH even
BCI FJK up
BIJ FGH even

ABCD EFGH even
ABCI EFJL down
ABIJ EFGH even

ABCD EFGH even
EFJK ABCI up
ABIJ EFGH up

B C down
ABCDEF GHIJKL up
DEF GHI even

A B down
ABCDEF GHIJKL down
DEF GHI even

*****

output (not formatted correctly):
(K light)
(L heavy)
(J heavy)
(C heavy)
(A light)
Personal tools