UVa : 485 (Pascal’s Triangle of Death)


Title : Pascal’s Triangle of Death

Link : http://uva.onlinejudge.org/external/4/485.html

Tricky Lines :

  1. When any number in the triangle is exceeds or equals 1060, your program should finish printing the current row and exit.

Analysis :

  1. from third row,
    each number = num [row – 1] [col] + num [row – 1] [col – 1]
    except 1st and last 1
  2. Big Integer

Runtime : 1.232s

Solution :

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

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		BigInteger current [] = new BigInteger [10000];
		BigInteger next [] = new BigInteger [10000];
		BigInteger end = BigInteger.TEN;
		
		for ( int i = 2; i <= 60; i++ )
			end = end.multiply(BigInteger.TEN);
		
		current [0] = current [1] = BigInteger.ONE;
		
		System.out.println (1);
		System.out.println ("1" + " " + "1");
		int line = 1;
		boolean stop = true;
		
		for ( ; stop ; ) {
			next [0] = BigInteger.ONE;
			for ( int i = 1; i <= line; i++ ) {
				next [i] = current [i].add(current [i - 1]);
				if ( next [i].compareTo(end) >= 0 ) stop = false;
			}
			next [++line] = BigInteger.ONE;
			
			for ( int i = 0; i < line; i++ ) {
				System.out.print (next [i] + " ");
				current [i] = next [i];
			}
			System.out.println (1);
			current [line] = BigInteger.ONE;	
		}
	}

}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s