Codeforces Beta Round #86 (Div1 & Div2)

Sep  8, 2011.

Accepted: .        WA: .        NotTried: .

Div 2:
114A.
114B.
Div 1:
113A.
113B.
113C.
113D.
113E.

Tutorial

Problem 1: 114A

Solution:

The precision in java is a miracle. I don''t know why it could let a double number comparable with an integer. but it works.

Source Code:

import java.util.Scanner;

/**
 * 
 */

/**
 * @author antonio081014
 * @date Sep 8, 2011
 * @time 10:01:34 AM
 */
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        for (int i = 0;; i++) {
            double c = Math.pow(a, i);
            if (c > b) {
                System.out.println("NO");
                break;
            } else if (c == b) {
                System.out.println("YES");
                System.out.println(i - 1);
                break;
            }
        }
    }
}

Problem 2: 114B

Solution:

The usage of TreeSet with key String mapped to List is a nice idea, which implements the multi-valued mapping. It's like a hash table. 

Source Code:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * 
 */

/**
 * @author antonio081014
 * @date Sep 8, 2011
 * @time 10:26:13 AM
 */
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<String> list = new ArrayList<String>();
        TreeMap<String, List<String>> map = new TreeMap<String, List<String>>();
        for (int i = 0; i < n; i++) {
            list.add(sc.next());
        }
        for (int i = 0; i < m; i++) {
            String a = sc.next();
            String b = sc.next();
            if (map.containsKey(a) == false) {
                List<String> tmp = new ArrayList<String>();
                tmp.add(b);
                tmp.add(a);
                map.put(a, tmp);
            } else {
                map.get(a).add(b);
            }
            if (map.containsKey(b) == false) {
                List<String> tmp = new ArrayList<String>();
                tmp.add(a);
                tmp.add(b);
                map.put(b, tmp);
            } else {
                map.get(b).add(a);
            }
        }
        TreeSet<String> ret = new TreeSet<String>();
        for (int i = 1; i < (1 << n); i++) {
            boolean flag = true;
            TreeSet<String> tmp = new TreeSet<String>();
            for (int j = 0; j < n && flag; j++) {
                if ((i & (1 << j)) > 0) {
                    String stmp = list.get(j);
                    if (map.containsKey(stmp)) {
                        boolean flag1 = true;
                        for (int k = 0; k < map.get(stmp).size() && flag1; k++) {
                            if (tmp.contains(map.get(stmp).get(k)))
                                flag1 = false;
                        }
                        if (flag1)
                            tmp.add(stmp);
                    } else
                        tmp.add(stmp);
                }
            }
            if (flag && tmp.size() > ret.size()) {
                ret = tmp;
            }
        }

        System.out.println(ret.size());
        Iterator it = ret.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

Problem 3: 113A

Solution:

The usage of Pattern is really nice and convenient here.

Source Code:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.regex.Pattern;

/**
 * 
 */

/**
 * @author antonio081014
 * @date Sep 9, 2011
 * @time 10:07:24 AM
 */
public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        BufferedReader reader = new BufferedReader(new InputStreamReader(
                System.in));
        String[] str;
        try {
            str = reader.readLine().split(" ");

            System.out.println(check(Translate(str)) ? "YES" : "NO");
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    private static boolean check(String s) {
        if (s.compareTo("NO") == 0)
            return false;
        if (s.length() == 1 && "ABCDEF".contains(s))
            return true;
        if (s.contains("B")) {
            if (Pattern.matches("A*BC*", s))
                return true;
        } else if (s.contains("E")) {
            if (Pattern.matches("D*EF*", s))
                return true;
        }
        return false;
    }

    public static String repeat(String str, int times) {
        return new String(new char[times]).replace("\0", str);
    }

    private static String Translate(String[] args) {
        String ret = "";
        for (int i = 0; i < args.length; i++) {
            String temp = Map(args[i]);
            if (temp.length() == 2)
                return "NO";
            ret += temp;
        }
        return ret;
    }

    private static String Map(String s) {
        if (s.endsWith("lios"))
            return "A";
        else if (s.endsWith("etr"))
            return "B";
        else if (s.endsWith("initis"))
            return "C";
        else if (s.endsWith("liala"))
            return "D";
        else if (s.endsWith("etra"))
            return "E";
        else if (s.endsWith("inites"))
            return "F";
        else
            return "NO";
    }

}

Problem 4: 113B

Solution:

Source Code:

Problem 5: 113C

Solution:

Source Code:

Problem 6: 113D

Solution:

Source Code:

Problem 7: 113E

Solution:

Source Code: