School Regional Team Contest Saratov 2011

Date: Oct 18, 2011.

Content:
Problem A.
Problem B.
Problem C.
Problem D.
Problem E.
Problem F.
Problem G.
Problem H.
Problem I.
Problem J.

Tutorial

Problem A:

Solution:

Ad-hoc.

Source Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;

/**
 * @author antonio081014
 * @date
 */
public class A {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            FileInputStream fis = new FileInputStream("input.txt");
            FileWriter fstream = new FileWriter("output.txt");
            BufferedWriter out = new BufferedWriter(fstream);
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String str = br.readLine();
            int num = Integer.parseInt(br.readLine());
            if ((str.compareTo("front") == 0 && num == 1)
                    || (str.compareTo("back") == 0 && num == 2))
                out.write("L");
            else
                out.write("R");
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Problem B:

Solution:

Ad-hoc.

Source Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;

/**
 * @author antonio081014
 * 
 */
public class B {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            FileInputStream fis = new FileInputStream("input.txt");
            FileWriter fstream = new FileWriter("output.txt");
            BufferedWriter out = new BufferedWriter(fstream);
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String strLine = br.readLine();
            int n = Integer.parseInt(strLine.split(" ")[0]);
            int k = Integer.parseInt(strLine.split(" ")[1]);
            String[] nums = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                int index = (i + k - 1) % n;
                if (Integer.parseInt(nums[index]) != 0) {
                    out.write(Integer.toString(index + 1));
                    break;
                }
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Problem C:

Solution:

Using Priority Queue to implement this is pretty straight forward. Keep popping the best solution for Winnie. PS: take care of the if...else... statement.

Source Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

/**
 * @author antonio081014, Oct 18, 2011, 12:02:19 AM
 */
public class C {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            FileInputStream fis = new FileInputStream("input.txt");
            FileWriter fstream = new FileWriter("output.txt");
            BufferedWriter out = new BufferedWriter(fstream);
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            PriorityQueue<Jar> queue = new PriorityQueue<Jar>();
            String strLine = br.readLine();
            int n = Integer.parseInt(strLine.split(" ")[0]);
            int k = Integer.parseInt(strLine.split(" ")[1]);
            String[] nums = br.readLine().split(" ");
            for (String str : nums) {
                queue.add(new Jar(Integer.parseInt(str)));
            }
            int total = 0;
            while (queue.isEmpty() == false) {
                Jar tmp = queue.poll();
                if (tmp.amount >= k) {
                    tmp.amount -= k;
                    tmp.times++;
                    if (tmp.times < 3)
                        queue.add(tmp);
                    else
                        total += tmp.amount;
                } else {
                    total += tmp.amount;
                }
            }
            out.write(Integer.toString(total));
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

class Jar implements Comparable<Jar> {
    int amount;
    int times;

    public Jar(int a) {
        this.amount = a;
        this.times = 0;
    }

    @Override
    public int compareTo(Jar o) {
        // TODO Auto-generated method stub
        if (this.amount > o.amount)
            return -1;
        else if (this.amount < o.amount)
            return 1;
        return 0;
    }
}

Problem D:

Solution:

From the statement of the problem, one of the most important statement is "The lines should be parallel to one side of the field and to each other." Thus, the problem can be considered in two options, one is cutting the board horizontally, the other one is cutting the board vertically. For each option, any two separation could make three pieces partition, so using two for loops to iterate every possible cutting solution, then check if the result is compatible with the required one. If yes, add one, do nothing otherwise.
PS: the solution should always have three pieces in the partition, so no piece of the solution could be empty.

Source Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * @author antonio081014
 * @date Oct 18, 2011, 12:38:48 AM
 */
public class D {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            FileInputStream fis = new FileInputStream("input.txt");
            FileWriter fstream = new FileWriter("output.txt");
            BufferedWriter out = new BufferedWriter(fstream);
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String strLine = br.readLine();
            int n = Integer.parseInt(strLine.split(" ")[0]);
            int m = Integer.parseInt(strLine.split(" ")[1]);
            int[][] arrays = new int[n][m];
            int[][] sum = new int[n][m];
            for (int i = 0; i < n; i++) {
                String[] tmp = br.readLine().split(" ");
                for (int j = 0; j < m; j++) {
                    arrays[i][j] = Integer.parseInt(tmp[j]);
                    sum[i][j] = arrays[i][j];
                    if (j > 0)
                        sum[i][j] += sum[i][j - 1];
                    if (i > 0)
                        sum[i][j] += sum[i - 1][j];
                    if (i > 0 && j > 0)
                        sum[i][j] -= sum[i - 1][j - 1];
                }
            }
            // for (int i = 0; i < n; i++) {
            // for (int j = 0; j < m; j++)
            // System.out.print(sum[i][j] + ", ");
            // System.out.println();
            // }
            strLine = br.readLine();
            int A = Integer.parseInt(strLine.split(" ")[0]);
            int B = Integer.parseInt(strLine.split(" ")[1]);
            int C = Integer.parseInt(strLine.split(" ")[2]);
            int count = 0;
            for (int i = 0; i + 2 < m; i++) {
                for (int j = i + 1; j + 1 < m; j++) {
                    int a1 = sum[n - 1][i];
                    int a2 = sum[n - 1][j] - a1;
                    int a3 = sum[n - 1][m - 1] - a1 - a2;
                    if (check(a1, a2, a3, A, B, C)) {
                        count++;
                    }
                }
            }
            for (int i = 0; i + 2 < n; i++) {
                for (int j = i + 1; j + 1 < n; j++) {
                    int a1 = sum[i][m - 1];
                    int a2 = sum[j][m - 1] - a1;
                    int a3 = sum[n - 1][m - 1] - a1 - a2;
                    if (check(a1, a2, a3, A, B, C)) {
                        count++;
                    }
                }
            }
            out.write(Integer.toString(count));
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static boolean check(int a1, int b1, int c1, int a2, int b2, int c2) {
        int[] num1 = { a1, b1, c1 };
        int[] num2 = { a2, b2, c2 };
        Arrays.sort(num1);
        Arrays.sort(num2);
        for (int i = 0; i < num1.length; i++)
            if (num1[i] != num2[i])
                return false;
        return true;
    }

}

Problem E:

Solution:

The solution is my random guess based on the case n = 1 ... 4. The more theoretical explanation will published later.

Source Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;

/**
 * @author antonio081014
 * @date Oct 18, 2011, 1:21:48 AM
 */
public class E {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            FileInputStream fis = new FileInputStream("input.txt");
            FileWriter fstream = new FileWriter("output.txt");
            BufferedWriter out = new BufferedWriter(fstream);
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            int T = Integer.parseInt(br.readLine());
            for (int i = 0; i < T; i++) {
                int n = Integer.parseInt(br.readLine());
                if (n % 2 == 1)
                    out.write(Integer.toString(0) + "\n");
                else
                    out.write(Integer.toString(1) + "\n");
            }
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}

Problem F:

Solution:

From the statement of the problem, the problem is actually to add the height of each tree(or spider) which is described in each line. So the problem turns to be calculate the height of each tree. To calculate the height of each tree, one needs to know the longest distance from any pair of nodes in that tree. So I iterate each node in the tree, and find the longest distance by using recursive function. PS: the rec function actually returns the number of nodes of the longest distance, while the length is the number of nodes - 1.

Source Code:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileWriter;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.StringTokenizer;

/**
 * @author antonio081014
 * @date Oct 18, 2011, 12:53:55 PM
 */
public class F {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        try {
            FileInputStream fis = new FileInputStream("input.txt");
            FileWriter fstream = new FileWriter("output.txt");
            BufferedWriter out = new BufferedWriter(fstream);
            DataInputStream in = new DataInputStream(fis);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            int T = Integer.parseInt(br.readLine());
            int count = 0;
            for (int i = 0; i < T; i++) {
                StringTokenizer stk = new StringTokenizer(br.readLine(), " ");
                int n = Integer.parseInt(stk.nextToken());
                List<Node> node = new ArrayList<Node>();
                for (int j = 0; j < n; j++) {
                    node.add(new Node(j));
                }
                for (int j = 0; j < n - 1; j++) {
                    int a = Integer.parseInt(stk.nextToken()) - 1;
                    int b = Integer.parseInt(stk.nextToken()) - 1;
                    node.get(a).next.add(node.get(b));
                    node.get(b).next.add(node.get(a));
                }
                // for (int j = 0; j < node.size(); j++) {
                // System.out.print("Node " + j + ":");
                // for (int k = 0; k < node.get(j).next.size(); k++) {
                // System.out.print(node.get(j).next.get(k).data + ", ");
                // }
                // System.out.println();
                // }
                int ret = 0;
                for (int j = 0; j < node.size(); j++) {
                    int tmp = rec(node.get(j), new HashSet<Integer>());
                    ret = Math.max(tmp, ret);
                }
                // System.out.println(ret - 1);
                count += ret - 1;
            }
            out.write(Integer.toString(count));
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public static int rec(Node node, HashSet<Integer> set) {
        int ret = 0;
        set.add(node.data);
        for (int i = 0; i < node.next.size(); i++) {
            if (set.contains(node.next.get(i).data))
                continue;
            int tmp = rec(node.next.get(i), set);
            if (tmp > ret)
                ret = tmp;
        }
        return ret + 1;
    }
}

class Node {
    int data;
    List<Node> next;

    public Node(int value) {
        this.data = value;
        next = new ArrayList<Node>();
    }
}

Problem G:

Solution:

Source Code:

Problem H:

Solution:

Source Code:

Problem I:

Solution:

Source Code:

Problem J:

Solution:

Source Code: