Friday, September 9, 2011

Codeforces Beta Round #86 (Div1 & Div2)

Sep  8, 2011.
Accepted: .        WA: .        NotTried: .
Div 2:
114A.
114B.
Div 1:
113A.
113B.
113C.
113D.
113E.

Tutorial

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;
}
}
}
}

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++) {
}
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>();
map.put(a, tmp);
} else {
}
if (map.containsKey(b) == false) {
List<String> tmp = new ArrayList<String>();
map.put(b, tmp);
} else {
}
}
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)
} else
}
}
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());
}
}
}

Solution:

The usage of Pattern is really nice and convenient here.

Source Code:

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
System.in));
String[] str;
try {

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";
}

}