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

スポンサーサイト

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

Related Posts

Next and Prev

Comments + Add Comment

Leave a comment

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分程度で解きます。

Comments + Add Comment

Leave a comment

Urgench Time

Urgench Temp

Click for Urgench, Uzbekistan Forecast

Tweets

Counter (visitor)

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