# Counterfeit Dollar

 This problem has been solved by nina.

 Sorter: Uncategorized Unknown 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)
```