import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3254.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
int R, N;
String sven, friend[];
in.nextToken();
R = (int) in.nval;
in.nextToken();
sven = in.sval;
in.nextToken();
N = (int) in.nval;
friend = new String[N];
for (int i = 0; i < N; ++i) {
in.nextToken();
friend[i] = in.sval;
}
int scores = 0, maxScores = 0;
int[] r, p, s;
r = new int[R];
p = new int[R];
s = new int[R];
for (int i = 0; i < N; ++i) {
for (int j = 0; j < R; ++j) {
scores += getPoint(sven.charAt(j), friend[i].charAt(j));
switch (friend[i].charAt(j)) {
case 'S':
++s[j]; break;
case 'P':
++p[j]; break;
default:
++r[j]; break;
}
}
}
for (int j = 0; j < R; ++j)
maxScores += Math.max(s[j] + 2 * p[j], Math.max(
p[j] + 2 * r[j], r[j] + 2 * s[j]));
out.println(scores + "\n" + maxScores);
out.flush();
}
private static int getPoint(char ch, char ch2) {
switch (ch) {
case 'S':
switch (ch2) {
case 'R': return 0;
case 'P': return 2;
default: return 1;
}
case 'P':
switch (ch2) {
case 'R': return 2;
case 'P': return 1;
default: return 0;
}
default:
switch (ch2) {
case 'R': return 1;
case 'P': return 0;
default: return 2;
}
}
}
}
Thứ Năm, 6 tháng 1, 2011
3254. Rock-Paper-Scissors
3293. A Sequence of Numbers
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3293.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
long N, a, b, c, d, k, i, m = 200907, n, res;
in.nextToken();
N = (long) in.nval;
while (N-- > 0) {
in.nextToken();
a = (long) in.nval;
in.nextToken();
b = (long) in.nval;
in.nextToken();
c = (long) in.nval;
in.nextToken();
k = (long) in.nval;
if (c - b == b - a) {
res = ((a % m) + (((k - 1) % m) *
((b - a) % m) % m)) % m;
} else {
d = (b / a) % m;
n = k - 1;
res = a % m;
for (i = 0; (1l << i) <= n; ++i) {
if ((n & (1l << i)) != 0)
res = (res * d) % m;
d = (d * d) % m;
}
}
out.println(res);
}
out.flush();
}
}
Thứ Hai, 3 tháng 1, 2011
3472. Chopin
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3472.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(
new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int t = Integer.parseInt(in.readLine());
String[] s;
while (t-- > 0) {
s = in.readLine().split(" ");
if (valid(s))
out.println("yes");
else
out.println("no");
}
out.flush();
}
private static boolean valid(String[] s) {
int i = 0, j = 0;
while (i < s[0].length() && j < s[1].length())
if (s[0].charAt(i) == s[1].charAt(j)) {
++i; ++j;
} else
++i;
return (j == s[1].length());
}
}
3498. Differences
import java.io.*;
import java.math.BigInteger;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3498.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(
new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(System.out);
int ca, n;
String[] s;
ca = Integer.parseInt(in.readLine());
while (ca-- > 0) {
n = Integer.parseInt(in.readLine());
s = in.readLine().split(" ");
BigInteger min = new BigInteger(s[0]);
BigInteger max = new BigInteger(s[0]);
BigInteger j;
for (int i = 1; i < n; ++i) {
j = new BigInteger(s[i]);
if (j.compareTo(max) > 0)
max = j;
else if (j.compareTo(min) < 0)
min = j;
}
out.println(max.subtract(min));
}
out.flush();
}
}
3457. Cow Pinball
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3457.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
int r, a[][];
in.nextToken();
r = (int) in.nval;
a = new int[r][];
for (int i = 0; i < r; ++i) {
a[i] = new int[i + 1];
for (int j = 0; j <= i; ++j) {
in.nextToken();
a[i][j] = (int) in.nval;
}
}
for (int i = 1; i < r; ++i) {
a[i][0] += a[i - 1][0];
a[i][i] += a[i - 1][i - 1];
for (int j = 1; j < i; ++j)
a[i][j] += Math.max(a[i - 1][j - 1], a[i - 1][j]);
}
int res = -1;
for (int j = 0; j < r; ++j)
if (res < a[r - 1][j])
res = a[r - 1][j];
out.println(res);
out.flush();
}
}
3484. Stones
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3484.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
int t, n, i, sum, max;
in.nextToken();
t = (int) in.nval;
while (t-- > 0) {
in.nextToken();
n = (int) in.nval;
max = -1; sum = 0;
for (int j = 0; j < n; ++j) {
in.nextToken();
i = (int) in.nval;
sum += i;
if (max < i)
max = i;
}
out.println(sum - max);
}
out.flush();
}
}
3483. Common Divisor
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3483.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
int t, n, m, a, i, j, k, res;
in.nextToken();
t = (int) in.nval;
while (t-- > 0) {
in.nextToken();
n = (int) in.nval;
in.nextToken();
m = (int) in.nval;
a = gcd(n, m);
res = 1;
k = 0;
while (a % 2 == 0) {
++k;
a = a >> 1;
}
res *= (k + 1);
k = 0;
while (a % 3 == 0) {
++k;
a /= 3;
}
res *= (k + 1);
i = 5; j = 2;
while (a > 1 && i * i <= a)
if (a % i == 0) {
k = 0;
while (a % i == 0) {
++k;
a /= i;
}
res *= (k + 1);
} else {
i += j;
j = 6 - j;
}
if (a > 1)
res = res << 1;
out.println(res);
}
out.flush();
}
private static int gcd(int a, int b) {
int r;
while (b != 0) {
r = a % b; a = b; b = r;
}
return a;
}
}
Chủ Nhật, 2 tháng 1, 2011
3496. Summation
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3496.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
int n, x, y, a, b;
in.nextToken();
n = (int) in.nval;
while (n-- > 0) {
in.nextToken();
x = (int) in.nval;
in.nextToken();
y = (int) in.nval;
a = b = 0;
while (x > 0) {
a = (a << 3) + (a << 1) + x % 10;
x /= 10;
}
while (y > 0) {
b = (b << 3) + (b << 1) + y % 10;
y /= 10;
}
out.println((a + b) + "\n");
}
out.flush();
}
}
3456. Rank
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3456.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int n, a[];
in.nextToken();
n = (int) in.nval;
a = new int[n];
for (int i = 0; i < n; ++i) {
in.nextToken();
a[i] = (int) in.nval;
}
int res = 0;
for (int i = 1; i < n; ++i)
if (a[i] > a[0])
++res;
System.out.println(res + 1);
}
}
3445. Soda Surple
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp3445.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int e, f, c;
in.nextToken();
e = (int) in.nval;
in.nextToken();
f = (int) in.nval;
in.nextToken();
c = (int) in.nval;
int res = 0;
e += f;
do {
f = e / c;
res += f;
e %= c;
e += f;
} while (e >= c);
System.out.println(res);
}
}
2193. A Simple Game
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp2193.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int n, m;
do {
in.nextToken();
n = (int) in.nval;
if (n == 0)
break;
in.nextToken();
m = (int) in.nval;
if (n % (m + 1) == 0)
System.out.println("Think About It.");
else
System.out.println("Just Do It.");
} while (true);
}
}
2199. A+B Problem
import java.io.*;
import java.util.Arrays;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp2199.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int n, i, j, k, a[];
do {
in.nextToken();
n = (int) in.nval;
if (n == 0)
break;
a = new int[n];
for (i = 0; i < n; ++i) {
in.nextToken();
a[i] = (int) in.nval;
}
Arrays.sort(a);
boolean b = false;
for (i = n - 1; i > 1; --i)
for (j = i - 1; j > 0; --j) {
k = Arrays.binarySearch(a, a[i] - a[j]);
if (k >= 0 && (k != j || a[k] == a[k+1] ||
((k > 0 && a[k-1] == a[k])))) {
System.out.println(a[i]);
b = true;
i = j = 0;
}
}
if (!b)
System.out.println(-1);
} while (true);
}
}
2196. Nuanran's Idol II
import java.io.*;
import java.util.PriorityQueue;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp2196.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int n;
PriorityQueue<Integer> a = new PriorityQueue<Integer>();
do {
in.nextToken();
n = (int) in.nval;
if (n == 0)
break;
a.clear();
for (int i = 0; i < n; ++i) {
in.nextToken();
if (in.sval.charAt(0) == 'B') {
in.nextToken();
a.add((int) in.nval);
} else
System.out.println(a.remove());
}
} while (true);
}
}
2101. Bullseye
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp2101.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
double[] x = new double[6];
double[] y = new double[6];
double[] r = new double[6];
int[] res = new int[2];
while (in.nextToken() != StreamTokenizer.TT_EOF) {
x[0] = in.nval;
if (x[0] == -100)
break;
in.nextToken();
y[0] = in.nval;
for (int i = 1; i < 6; ++i) {
in.nextToken();
x[i] = in.nval;
in.nextToken();
y[i] = in.nval;
}
res[0] = res[1] = 0;
for (int i = 0; i < 6; ++i)
r[i] = Math.sqrt(x[i] * x[i] + y[i] * y[i]);
for (int i = 0; i < 6; ++i)
if (r[i] <= 3.0 || Math.abs(r[i] - 3.0) <= 0.000000001)
res[i/3] += 100;
else if (r[i] <= 6.0 || Math.abs(r[i] - 6.0) <= 0.000000001)
res[i/3] += 80;
else if (r[i] <= 9.0 || Math.abs(r[i] - 9.0) <= 0.000000001)
res[i/3] += 60;
else if (r[i] <= 12.0 || Math.abs(r[i] - 12.0) <= 0.000000001)
res[i/3] += 40;
else if (r[i] <= 15.0 || Math.abs(r[i] - 15.0) <= 0.000000001)
res[i/3] += 20;
System.out.print("SCORE: " + res[0] + " to " + res[1]);
if (res[0] == res[1])
System.out.println(", TIE.");
else if (res[0] > res[1])
System.out.println(", PLAYER 1 WINS.");
else
System.out.println(", PLAYER 2 WINS.");
}
}
}
1176. Recaman's Sequence
import java.io.*;
import java.util.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1176.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
boolean[] exist = new boolean[4000000];
int[] a = new int[500005];
int k, max = -1;
ArrayList<Integer> arr = new ArrayList<Integer>();
do {
in.nextToken();
k = (int) in.nval;
if (k == -1) break;
arr.add(k);
if (max < k) max = k;
} while (true);
a[0] = 0;
for (int m = 1; m <= max; ++m) {
if (a[m-1] > m && !exist[a[m-1] - m])
a[m] = a[m-1] - m;
else
a[m] = a[m-1] + m;
exist[a[m]] = true;
}
for (Integer m : arr)
System.out.println(a[m]);
}
}
1175. Calendar
import java.io.*;
import java.util.*;
import java.text.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1175.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
DateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd EEEE");
int n;
long m, k = 946684800000l;
Date date = new Date();
do {
in.nextToken();
n = (int) in.nval;
if (n == -1) break;
m = (long) n * 86400000 + k;
date.setTime(m);
System.out.println(dateFormat.format(date));
} while (true);
}
}
1161. 487-3279
import java.io.*;
import java.util.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1161.html
* @author hunglee
*/
private static String letter = "ABCDEFGHIJKLMNOPRSTUVWXY";
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
PrintWriter out = new PrintWriter(System.out);
int n;
int[] a = new int[10000000];
Integer i;
n = in.nextInt();
in.nextLine();
while (n-- > 0) {
i = convert(in.nextLine());
a[i]++;
}
n = 0;
for (i = 0; i < 10000000; i++)
if (a[i] > 1) {
n++;
out.print(String.format("%03d-%04d", i / 10000, i % 10000));
out.print(" ");
out.println(a[i]);
}
if (n == 0)
out.println("No duplicates.");
out.flush();
}
protected static int convert(String s) {
int res = 0;
for (int i = 0; i < s.length(); i++) {
if (Character.isDigit(s.charAt(i)))
res = 10 * res + (s.charAt(i) - '0');
else if (Character.isUpperCase(s.charAt(i)))
res = 10 * res + (2 + letter.indexOf(s.charAt(i)) / 3);
}
return res;
//return String.format("%03d-%04d", res / 10000, res % 10000);
}
}
1156. Niven Numbers
import java.io.*;
import java.util.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1156.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
int b;
String s;
do {
b = in.nextInt();
if (b == 0) break;
s = in.next();
int value = 0, sumd = 0;
for (int i = 0; i < s.length(); ++i) {
sumd += (s.charAt(i) - '0');
value = value * b + (s.charAt(i) - '0');
}
if (value % sumd == 0)
System.out.println("yes");
else
System.out.println("no");
} while (true);
}
}
1154. A Mathematical Curiosity
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1154.html
* @author hunglee
* @throws IOException
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int n, m, t = 0;
do {
in.nextToken();
n = (int) in.nval;
in.nextToken();
m = (int) in.nval;
if (n == 0 && m == 0) break;
int res = 0;
for (int a = 1; a < n - 1; ++a)
for (int b = a + 1; b < n; ++b)
if ((a * a + b * b + m) % (a * b) == 0) ++ res;
++t;
System.out.println("Case " + t + ": " + res);
} while (true);
}
}
1150. Sum of Factorials
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1150.html
* @author hunglee
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
int n, i;
int[] f = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};
do {
in.nextToken();
n = (int) in.nval;
if (n < 0) break;
if (n == 0) {
out.println("NO");
continue;
}
i = 9;
while (n > 0 && i >= 0) {
while (i >= 0 && f[i] > n) --i;
if (i >= 0)
n -= f[i];
--i;
}
if (n == 0)
out.println("YES");
else
out.println("NO");
} while (true);
out.flush();
}
}
1144. Tree Recovery
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1144.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
String preord, inord;
while (in.nextToken() != StreamTokenizer.TT_EOF) {
preord = in.sval;
in.nextToken();
inord = in.sval;
process(preord, inord);
System.out.println();
}
}
private static void process(String preord, String inord) {
if (preord.length() <= 1) {
System.out.print(preord);
return;
}
int i = inord.indexOf(preord.charAt(0));
process(preord.substring(1, i + 1), inord.substring(0, i));
process(preord.substring(i + 1), inord.substring(i + 1));
System.out.print(preord.charAt(0));
}
}
1138. Binomial Showdown
import java.io.*;
import java.math.BigInteger;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1138.html
* @author hunglee
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
PrintWriter out = new PrintWriter(System.out);
long n, k;
do {
in.nextToken();
n = (long) in.nval;
in.nextToken();
k = (long) in.nval;
if (n == 0 && k == 0) break;
long i;
BigInteger res = new BigInteger("1");
BigInteger res2 = new BigInteger("1");
if (k > n - k) k = n - k;
for (i = n - k + 1; i <= n; ++i)
res = res.multiply(BigInteger.valueOf(i));
for (i = 2; i <= k; ++i)
res2 = res2.multiply(BigInteger.valueOf(i));
out.println(res.divide(res2));
} while (true);
out.flush();
}
}
Thứ Bảy, 1 tháng 1, 2011
1136. Humble Numbers
import java.io.*;
import java.util.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1136.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int n, nhumbles = 0;
int[] humble = new int[5842];
final long MAX = 2000000000;
long res = 1;
for (int i = 0; ; ++i) {
if (res > MAX) break;
for (int j = 0; ; ++j) {
if (res > MAX) {
res /= (long) Math.pow(3, j);
break;
}
for (int h = 0; ; ++h) {
if (res > MAX) {
res /= (long) Math.pow(5, h);
break;
}
for (int k = 0; ; ++k) {
if (res > MAX) {
res /= (long) Math.pow(7, k);
break;
}
humble[nhumbles++] = (int) res;
res *= 7;
}
res *= 5;
}
res *= 3;
}
res = res << 1;
}
Arrays.sort(humble);
do {
in.nextToken();
n = (int) in.nval;
if (n == 0) break;
if (n % 10 == 1 && n%100 != 11)
System.out.println("The " + n + "st humble number is " +
humble[n - 1] + ".");
else if (n % 10 == 2 && n % 100 != 12)
System.out.println("The " + n + "nd humble number is " +
humble[n - 1] + ".");
else if (n % 10 == 3 && n % 100 != 13)
System.out.println("The " + n + "rd humble number is " +
humble[n - 1] + ".");
else
System.out.println("The " + n + "th humble number is " +
humble[n-1] + ".");
} while (true);
}
}
1134. Lotto
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1134.html
* @author hunglee
*/
static int k;
static int[] a, b = new int[7];
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int t = 0;
b[0] = -1;
do {
in.nextToken();
k = (int) in.nval;
if (k == 0) break;
a = new int[k];
for (int i = 0; i < k; ++i) {
in.nextToken();
a[i] = (int) in.nval;
}
if (t > 0) System.out.println();
else t = 1;
attempt(1);
} while (true);
}
private static void attempt(int i) {
if (i == 7) {
for (int j = 1; j <= 5; ++j)
System.out.print(a[b[j]] + " ");
System.out.println(a[b[6]]);
} else {
for (int j = b[i-1] + 1; j < k + i - 6; ++j) {
b[i] = j;
attempt(i + 1);
}
}
}
}
1132. Knight Moves
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1132.html
* @author hunglee
* @throws IOException
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
String xx, yy;
int iS, jS, iF, jF, i, j, ik, jk;
final int[] di = {-2, -1, 1, 2, 2, 1, -1, -2};
final int[] dj = {1, 2, 2, 1, -1, -2, -2, -1};
Queue<Integer> q;
while (in.nextToken() != StreamTokenizer.TT_EOF) {
xx = in.sval;
in.nextToken();
yy = in.sval;
iS = xx.charAt(1) - '0' + 1;
jS = xx.charAt(0) - 'a' + 2;
iF = yy.charAt(1) - '0' + 1;
jF = yy.charAt(0) - 'a' + 2;
if (iS == iF && jS == jF) {
System.out.print("To get from ");
System.out.print(xx + " to " + yy);
System.out.println(" takes 0 knight moves.");
continue;
}
int[][] board = new int[12][12]; //2 -> 9
for (i = 0; i <= 11; ++i)
board[i][0] = board[i][1] =
board[i][10] = board[i][11] = -1;
for (j = 0; j <= 11; ++j)
board[0][j] = board[1][j] =
board[10][j] = board[11][j] = -1;
q = new LinkedList<Integer>();
board[iS][jS] = 1;
q.add(iS); q.add(jS);
while (!q.isEmpty()) {
i = q.remove(); j = q.remove();
for (int k = 0; k < 8; ++k) {
ik = i + di[k];
jk = j + dj[k];
if (ik == iF && jk == jF) {
System.out.print("To get from ");
System.out.print(xx + " to " + yy);
System.out.print(" takes " + (board[i][j]));
System.out.println(" knight moves.");
k = 8;
q.clear();
break;
}
if (board[ik][jk] == 0) {
board[ik][jk] = board[i][j] + 1;
q.add(ik); q.add(jk);
}
}
}
}
}
}
1131. The Circumference Of The Circle
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1131.html
* @author hunglee
* @throws IOException
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
final double PI = 3.141592653589793;
double x1, x2, x3, y1, y2, y3;
double x, y, dx, dy, d, a1, b1, c1, a2, b2, c2, r, c;
while (in.nextToken() != StreamTokenizer.TT_EOF) {
x1 = in.nval;
in.nextToken(); y1 = in.nval;
in.nextToken(); x2 = in.nval;
in.nextToken(); y2 = in.nval;
in.nextToken(); x3 = in.nval;
in.nextToken(); y3 = in.nval;
a1 = 2.0 * (x2 - x1);
b1 = 2.0 * (y2 - y1);
c1 = x2 * x2 + y2 * y2 - x1 * x1 - y1 * y1;
a2 = 2.0 * (x3 - x1);
b2 = 2.0 * (y3 - y1);
c2 = x3 * x3 + y3 * y3 - x1 * x1 - y1 * y1;
dx = c1 * b2 - c2 * b1;
dy = a1 * c2 - a2 * c1;
d = a1 * b2 - a2 * b1;
x = dx / d;
y = dy / d;
r = Math.sqrt((x - x1) * (x - x1) + (y - y1) * (y - y1));
c = 2.0 * r * PI;
System.out.println(String.format("%.2f", c));
}
}
}
1117. Game Prediction
import java.io.*;
import java.util.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1117.html
* @author hunglee
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int m, n, t = 1;
do {
in.nextToken();
m = (int) in.nval;
in.nextToken();
n = (int) in.nval;
if (m == 0 && n == 0) break;
boolean[] exist = new boolean[m * n + 1];
int arr[] = new int[n];
for (int i = 0; i < n; ++i) {
in.nextToken();
arr[i] = (int) in.nval;
exist[arr[i]] = true;
}
int max = m * n;
int res = 0, j;
Arrays.sort(arr);
for (int i = n - 1; i >= 0; --i) {
j = arr[i] + 1;
while (j <= max && exist[j]) ++j;
if (j <= max)
exist[j] = true;
else
res++;
}
System.out.println("Case " + t++ + ": " + res);
} while (true);
}
}
1105. Word Index
import java.io.*;
import java.util.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1105.html
* @author hunglee
* @throws IOException
*/
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
String s;
int res = 0;
int i, j;
while (in.hasNext()) {
s = in.nextLine();
if (s == "") break;
res = 0;
for (i = 0; i < s.length() - 1; i++)
if (s.charAt(i) >= s.charAt(i+1)) {
System.out.println(0);
s = "";
break;
}
if (s == "") continue;
for (i = 1; i < s.length(); i++) {
res += (c(26, i));
}
res++;
int pre = 'a' - 1;
for (i = 0; i < s.length(); i++) {
for (j = pre + 1; j < s.charAt(i); j++)
res += c('z' - j, s.length() - i - 1);
pre = s.charAt(i);
}
System.out.println(res);
};
}
protected static int c(int n, int k) {
long res, res2;
res = res2 = 1;
int i;
for (i = n - k + 1; i <= n; i++)
res *= i;
for (i = 2; i <= k; i++)
res2 *= i;
return (int)(res / res2);
}
}
1100. Pi
import java.io.*;
public class Main {
/**
* http://acm.tju.edu.cn/toj/showp1100.html
* @author hunglee
* @throws IOException
*/
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(
new InputStreamReader(System.in)));
int n;
int res, total;
double pi;
String s;
do {
in.nextToken();
n = (int) in.nval;
if (n == 0) break;
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
in.nextToken();
a[i] = (int) in.nval;
}
res = 0;
total = (n * (n - 1)) / 2;
for (int i = 0; i < n - 1; ++i)
for (int j = i + 1; j < n; ++j)
if (gcd(a[i], a[j]) == 1) ++res;
pi = Math.sqrt((double)total * 6.0 / res);
if (res != 0)
s = String.format("%.6f", pi);
else
s = "No estimate for this data set.";
System.out.println(s);
} while (true);
}
private static int gcd(int a, int b) {
int r;
while (b != 0) {
r = a % b; a = b; b = r;
}
return a;
}
}
1090. City Hall
http://acm.tju.edu.cn/toj/showp1090.html
import java.io.*;
import java.util.Arrays;
public class Main {
/**
* @author hunglee
*/
static BufferedReader bin = new BufferedReader(
new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int m = 0, n = 0;
m = readInt();
n = readInt();
int a[][] = new int[m + 1][n];
String s;
for (int i = 0; i < m; ++i) {
do {
s = bin.readLine();
} while (s.length() != n);
for (int j = 0; j < n; ++j)
a[i][j] = s.charAt(j) - '0';
}
Arrays.fill(a[m], 1);
int h[] = new int[m + 1];
int l;
for (int j = 0; j < n; ++j) {
l = 0;
for (int i = 0; i <= m; ++i)
if (a[i][j] == 0)
++l;
else {
++h[l];
l = 0;
}
}
for (int i = 1; i <= m; ++i)
if (h[i] > 0)
System.out.println(i + " " + h[i]);
}
private static int readInt() throws IOException {
int res = 0, i;
do {
i = bin.read();
if (i < '0' || i > '9') break;
res = 10 * res + i - '0';
} while (true);
return res;
}
}
Đăng ký:
Bài đăng (Atom)