Sorry, no corresponding articles.
--
--
--
no comments

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
11
29
2011
0 comments

ACMプログラミングコンテストの過去問を解く3

シリーズその3。


帰りの列車で、
退屈だったのもあり、
今年の問題を解いてみました。


今回の問題はコレ↓のA
http://neerc.ifmo.ru/regional/neerc-2011.pdf


ASCII Area

今年のA(一番簡単な)問題です。

要約

アスキーアートのように、記号で形を表現し、そのエリアの大きさを求めさせるもの。

考え方

アスキーアートの部分は1行ずつ読み込み、左から1つずつ処理させます。

仕切りの確認、エリアの内外の判定などを実行していきます。

エリア内外の判定フラグでエリア内となった部分の数を、仕切りの数は半分にして加算します。

プログラム

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class AsciiArea {

public static void main(String[] args) {

BufferedReader br = null;
PrintWriter pw = null;

try {
br = new BufferedReader(new FileReader("ascii.in"));
pw = new PrintWriter("ascii.out");

StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int h = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int ans = 0;

for (int i = 0; i < h; i++) {
String str = br.readLine();
boolean area = false;
int line = 0;

for (int j = 0; j < w; j++) {
if (str.charAt(j) == '/' || str.charAt(j) == '\\') {
area = !area;
line++;
} else {
if (area) {
ans++;
}
}
}

ans += line / 2;
}

//System.out.println(ans);
pw.println(ans);

br.close();
pw.close();
} catch(IOException e) {
e.printStackTrace();
} finally {
try {
if (br != null) {
br.close();
}

if (pw != null) {
pw.close();
}
} catch(IOException e) {
e.printStackTrace();
}
}

}

}
スポンサーサイト
09
26
2011
0 comments

ACMプログラミングコンテストの過去問を解く2

さてシリーズその2。


今回の問題はコチラ↓
http://acm.timus.ru/problem.aspx?space=1&num=1054


Hanoi Tower

NEERC 2000 Central Subregional

要約

有名なパズル「ハノイの塔」を使った問題です。

3本の杭をそれぞれ1、2、3と表記し、
1・・・移動元
2・・・移動先
3・・・一時的な置き場
と、します。

インプットの最初の数字は移動させるディスクの数N、その後に続くN個の数字は、
小さい順にそれぞれのディスクが置かれている杭を表します。

インプットのディスクの状態がハノイの塔の何手目であるかを
アウトプットするプログラムを作ります。

ただしインプットでない場合は、
「-1」を出力させる必要があります。

考え方

定石通り再帰的呼出しを使います。

一番大きなN番目のディスクに注目すると、
1(移動元にいる)・・・手が進んでいない
2(移動先にいる)・・・2^(n-1)手進んだ状態
3(一時的な置き場にいる)・・・正着でない
となります。

次に大きいN-1番目のディスクは、N番目のディスクの位置によって、
「移動元」、「移動先」、「一時的な置き場」の関係が変わります。

<N = 1の場合>
1・・・移動元
2・・・一時的な置き場
3・・・移動先

<N = 2の場合>
1・・・一時的な置き場
2・・・移動先
3・・・移動元
と、なります。

N-1番目のディスクについてもN番目のディスクと同様に
何手進んだ状態であるか判定することが可能で、
NとN-1の関係は、N-1とN-2についても変わらないので、
再帰処理で全てのディスクから手数の合計が求められます。

プログラム

import java.util.Scanner;

public class HanoiTower {

static int[] p;

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int i = 0;

p = new int[n];

for (int j = 0; j < n; j++) {
p[j] = sc.nextInt();
}

hanoi(n, i, 1, 2, 3);

}

static void hanoi(int n, int i, int from, int to, int temp) {

if(n == 0) {
System.out.println(i);
return;
}

if(p[n - 1] == from) {
hanoi(n - 1, i, from, temp, to);
} else if(p[n - 1] == to) {
i += Math.pow(2, n - 1);
hanoi(n - 1, i, temp, to, from);
} else {
System.out.println("-1");
}
}

}
08
24
2011
0 comments

ACMプログラミングコンテストの過去問を解く1

というわけでシリーズになるのかはさておき、
ウチの学生たちはこんなことやってますということで、
自分の解いた問題を公開してみようと思います。


今回の問題はコチラ↓
http://acm.timus.ru/problem.aspx?space=1&num=1114


Boxes

Bulgarian Online Contest September 2001

Description

N boxes are lined up in a sequence (1 ≤ N ≤ 20). You have A red balls and B blue balls (0 ≤ A ≤ 15, 0 ≤ B ≤ 15). The red balls (and the blue ones) are exactly the same. You can place the balls in the boxes. It is allowed to put in a box, balls of the two kinds, or only from one kind. You can also leave some of the boxes empty. It's not necessary to place all the balls in the boxes. Write a program, which finds the number of different ways to place the balls in the boxes in the described way.

Input

Input contains one line with three integers N, A and B separated by space.

Output

The result of your program must be an integer written on the only line of output.
Sample Input
2 1 1
Sample Output
9

要約

N個の箱、A個の赤いボール、B個の青いボールがあります。
それらは、1 ≤ N ≤ 20、0 ≤ A ≤ 15、0 ≤ B ≤ 15です。

N、A、Bに適当な数字を与えたとき、箱にボールを入れないことも可で、
全部で何通りのボールの納め方があるかを計算するプログラムを書きます。

箱には1番目の箱、2番目の箱・・・というように区別がありますが、
ボールには色の違い以外の区別はありません。

サンプルのインプットは箱2つ、赤いボール1つ、青いボール1つで、
1つの赤いボールが、「1番目の箱へ」、「2番目の箱へ」、「箱に入れない」
の3通り、青いボールについても同様なので、3×3で9通りとなります。

考え方

各色のボールが1つなら要約の方法で計算できますが、
2つ以上ある場合に同じ箱に入ると、組合せの数から減らす必要があります。

従って、
(N+1)の(A+B)乗では不正解です。

まず赤いボールについてだけの組み合わせを考えます。

箱の数(N)+1通りの選択を重複を許して赤いボールの数だけ行うと考えて、
重複組合せ(nHr)を利用します。

すると、
(N+1)HA=(N+A)CA
と赤いボールの組み合わせが求められました。

一方、
青いボールについても同様で、(N+B)CB
となります。

また、赤と青それぞれの組み合わせはお互いに影響を及ぼさないので、
トータルの組み合わせは、(N+A)CA×(N+B)CB
と求められます。

プログラム

import java.math.BigInteger;
import java.util.Scanner;

public class Boxes {

public static void main(String args[]) {

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();

System.out.println(function(n, a).multiply(function(n, b)));
}

private static BigInteger function(int n, int m) {

BigInteger v = new BigInteger("1");

for (int i = 1; i <= n; i++) {
v = v.multiply(BigInteger.valueOf((m + i))).divide(BigInteger.valueOf(i));
}

return v;

}
}
桁あふれを考慮して、BigIntegerを使っています。


慣れないタイプのプログラムやアルゴリズムに自分は2時間ぐらいかかりましたが、
4年生のエースの学生あたりだと20分程度で解きます。
Total 1 Pages:

Urgench Time

Urgench Temp

Click for Urgench, Uzbekistan Forecast

Tweets

Counter (visitor)

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。