# Counterfeit Dollar

### From Progteam

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)