読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 991 : Safe Salutations

問題リンク:http://uva.onlinejudge.org/external/9/991.html

問題概要:
円周上にn*2の人が等間隔で立っている
人と人を結ぶときにその線分が交差しない様な結び方は何通り存在するか?
(1 <= n <= 10)

解法:
カタラン数を利用する
wikipediaのカタラン数のページより、
2n人が円になって手を交差させないで握手をする場合の数はカタラン数Cnである。
なそうなので、この問題はまんまこれ
入力nに対するカタラン数Cnを出力する
入力は複数くる事とデータセットの間には空行を入れることを忘れずに

コード:

#include<iostream>
#define MAX 1024
using namespace std;
int Table[MAX];
int CatalanNumber(int n)
{
  if(n == 0)return 1;
  if(Table[n] != 1)return Table[n];
  Table[n] = 0;
  for(int i=1;i<=n;i++)
    {
      Table[n] += CatalanNumber(i-1)*CatalanNumber(n-i);
    }
  return Table[n];
}

int main()
{
  for(int i=0;i<MAX;i++)Table[i] = 1;

  int n;
  bool first = true;
  while(cin >> n)
    {
      if(!first)cout << endl;
      first = false;
      cout << CatalanNumber(n) << endl;
    }

  return 0;
}||<

*1385156909*[UVa][BigInteger][Java] UVa 10814 : Simplifying Fractions
問題リンク:[http://uva.onlinejudge.org/external/108/10814.html:title]

問題概要:
 p / q を約分した形にせよ
(1 <= p,q <= 10^30)

解法:
java の BigInteger を使う
p , q をそれぞれ BigInteger にし、BigIntegerのgcdを使い最大公約数を求め
(p/gcd) "/" (q/gcd) を出力する 

コード:
>|java|
import java.io.*;
import java.util.*;
import java.math.*;

class Main
{
    public static void main(String args[])
    {
	Scanner in = new Scanner(System.in);
	int N = in.nextInt();

	while(N-- > 0)
	    {
		String p = in.next();
		String div = in.next();
		String q = in.next();
		BigInteger P = new BigInteger(p);
		BigInteger Q = new BigInteger(q);
		BigInteger gd = P.gcd(Q);
		p = P.divide(gd).toString();
		q = Q.divide(gd).toString();
		System.out.println(p + " / " + q);
	    }
    }
}