Multi-core Processor [Codeforces Coder-Strike 2014 Qualification Round] Problem B [Java]

B. Multi-core Processor

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

The research center Q has developed a new multi-core processor. The processor consists of n cores and has k cells of cache memory. Consider the work of this processor.

At each cycle each core of the processor gets one instruction: either do nothing, or the number of the memory cell (the core will write an information to the cell). After receiving the command, the core executes it immediately. Sometimes it happens that at one cycle, multiple cores try to write the information into a single cell. Unfortunately, the developers did not foresee the possibility of resolving conflicts between cores, so in this case there is a deadlock: all these cores and the corresponding memory cell are locked forever. Each of the locked cores ignores all further commands, and no core in the future will be able to record an information into the locked cell. If any of the cores tries to write an information into some locked cell, it is immediately locked.

The development team wants to explore the deadlock situation. Therefore, they need a program that will simulate the processor for a given set of instructions for each core within m cycles . You're lucky, this interesting work is entrusted to you. According to the instructions, during the m cycles define for each core the number of the cycle, during which it will become locked. It is believed that initially all cores and all memory cells are not locked.

Input

The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 100). Then follow n lines describing instructions. The i-th line contains mintegers: xi1, xi2, ..., xim (0 ≤ xij ≤ k), where xij is the instruction that must be executed by the i-th core at the j-th cycle. If xij equals 0, then the corresponding instruction is «do nothing». But if xij is a number from 1 to k, then the corresponding instruction is «write information to the memory cell number xij».

We assume that the cores are numbered from 1 to n, the work cycles are numbered from 1 to m and the memory cells are numbered from 1 to k.

Output

Print n lines. In the i-th line print integer ti. This number should be equal to 0 if the i-th core won't be locked, or it should be equal to the number of the cycle when this core will be locked.

Sample test(s)

input

4 3 5
1 0 0
1 0 2
2 3 1
3 2 0

output

1
1
3
0

input

3 2 2
1 2
1 2
2 2

output

1
1
0

input

1 1 1
0

output

0

My Solution [Java]:

→ Source

import java.util.*;

public class MultiCoreProcessor {

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int c = s.nextInt();
        int in = s.nextInt();

        int arr[][] = new int[n + 1][c + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= c; ++j) {
                arr[i][j] = s.nextInt();
            }
        }

        int bp[] = new int[n + 1];
        int ins[] = new int[in + 1];

        for (int i = 1; i <= c; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (bp[j] == 0) {
                    if(arr[j][i]==0){
                        continue;
                    }
                    if (ins[arr[j][i]] == 1) {
                            bp[j] = i;
                            continue;
                    }
                    for (int k = j+1; k <= n; ++k) {
                        if (arr[j][i] == arr[k][i]&&bp[k]==0) {
                            bp[j] = i;
                            bp[k] = i;
                            ins[arr[j][i]] = 1;
                        }
                    }
                }

            }
        }
        for (int i = 1; i <= bp.length - 1; ++i) {
            System.out.println(bp[i]);
        }

    }
}

Magic Trick [Google Code Jam 2014: (Qualification Round Problem)]

Problem

Recently you went to a magic show. You were very impressed by one of the tricks, so you decided to try to figure out the secret behind it!

The magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.

Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose. Amazing, right?

You decide to write a program to help you understand the magician's technique. The program will be given the two arrangements of the cards, and the volunteer's answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.

Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there's no card consistent with the volunteer's answers (the volunteer cheated).

Solving this problem

Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has only 1 Small input. Once you have solved the Small input, you have finished solving this problem.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing an integer: the answer to the first question. The next 4 lines represent the first arrangement of the cards: each contains 4 integers, separated by a single space. The next line contains the answer to the second question, and the following four lines contain the second arrangement in the same format.

Output

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1).

If there is a single card the volunteer could have chosen, y should be the number on the card. If there are multiple cards the volunteer could have chosen, y should be "Bad magician!", without the quotes. If there are no cards consistent with the volunteer's answers, y should be "Volunteer cheated!", without the quotes. The text needs to be exactly right, so consider copying/pasting it from here.

Limits

1 ≤ T ≤ 100.
1 ≤ both answers ≤ 4.
Each number from 1 to 16 will appear exactly once in each arrangement.

Sample

Input	Output
3 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3 1 2 5 4 3 11 6 15 9 10 7 12 13 14 8 16 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16	Case #1: 7 Case #2: Bad magician! Case #3: Volunteer cheated!

Here is what I wrote (gives correct output): 

import java.util.*;

import java.io.*;

import java.util.regex.Matcher;

import java.util.regex.Pattern;

public class magic {

    public static void main(String[] args) throws Exception{

        BufferedReader br = new BufferedReader(new FileReader("d:\\A-small-attempt0.in"));

        BufferedWriter bw = new BufferedWriter(new FileWriter("d:\\result.txt"));

        

        int ncases = Integer.parseInt(br.readLine());

        

        int index = 1;

        while(index<=ncases){

            int nrow1 = Integer.parseInt(br.readLine());

            

            int[][] row1 = new int[4][4];

            int[][] row2 = new int[4][4];

            

            Pattern p = Pattern.compile("-?\\d+");

            Matcher m = null;

            for(int i= 0;i<4;++i){

                m =  p.matcher(br.readLine());

                for(int j = 0;j<4;++j){

                    if(m.find())

                    row1[i][j] = Integer.parseInt(m.group());

                }

            }

            

            int nrow2 = Integer.parseInt(br.readLine());

            for(int i= 0;i<4;++i){

                m =  p.matcher(br.readLine());

                for(int j = 0;j<4;++j){

                    if(m.find())

                    row2[i][j] = Integer.parseInt(m.group());

                }

            }

            

            Vector<Integer> vec1 = new Vector<Integer>();

            Vector<Integer> vec2 = new Vector<Integer>();

            

            for(int i = 0;i<4;++i){

                vec1.add(row1[nrow1-1][i]);

            }

            for(int i = 0;i<4;++i){

                vec2.add(row2[nrow2-1][i]);

            }

            

            Vector<Integer> number = new Vector<Integer>();

            for(int i = 0;i<vec1.size();++i){

                for(int j = 0;j<vec2.size();++j){

                    if(vec1.elementAt(i)==vec2.elementAt(j)){

                        number.add(vec1.elementAt(i));

                    }

                }

            }

            if(number.size()==0){

                bw.write("Case #"+index+++": Volunteer cheated!");

                //System.out.println("Case #"+index+++": Volunteer cheated!");

            }

            if(number.size()==1){

                bw.write("Case #"+index+++": "+number.elementAt(0));

                //System.out.println("Case #"+index+++": "+number.elementAt(0));

            }

            if(number.size()>1){

                bw.write("Case #"+index+++": Bad magician!");

                //System.out.println("Case #"+index+++": Bad magician!");

            }

            bw.newLine();

            bw.flush();

        }

    }

}