UVa : 10198 (Counting)


Title : Counting

Link : http://uva.onlinejudge.org/external/101/10198.html

Tricky Lines :

  1. 4 is another way to write 1.

Analysis :

  1. Classic dp
  2. dp [n] =
    how many ways we can made (n – 1) +
    how many ways we can made (n – 2) +
    how many ways we can made (n – 3) +
    how many ways we can made (n – 1)

    dp [n] = dp [n – 1] + dp [n – 2] + dp [n – 3] + dp [n – 1]

  3. Use Big Integer

Runtime : 0.676s

Critical input : 
1000
1
4
5
6
7
8

Critical output :
7804866167757385351726298167749579946964405850225254539132682472794981869745040537197592219996231328486687877730240352396489040560067523395940725030942516170568234738182127635234624655775531244438437118253542255365923486221253172456203933189283985689116139597563337647696143005496252287734941893682019406515104829885420261968884040123236083676226862353415881286645117793584639279853095668990201156175586714
2
33
84
214
545
1388

Solution :

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

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner input = new Scanner (System.in);
		BigInteger dp [] = new BigInteger [1000 + 10];
		
		Arrays.fill(dp, BigInteger.ZERO);
		
		dp [0] = BigInteger.valueOf(1);
		dp [1] = BigInteger.valueOf(2);
		dp [2] = BigInteger.valueOf(5);
		dp [3] = BigInteger.valueOf(13);
		
	    for ( int i = 4; i <= 1000; i++ ) {
	        dp [i] = dp [i].add(dp [i - 1]);
	        dp [i] = dp [i].add(dp [i - 2]);
	        dp [i] = dp [i].add(dp [i - 3]);
	        dp [i] = dp [i].add(dp [i - 1]);
	    }
	    
	    int n;
	    
	    while ( input.hasNextInt() ) {
	    	n = input.nextInt();
	    	System.out.println (dp [n]);
	    }
	}
}
Advertisements

One thought on “UVa : 10198 (Counting)

  1. Because here is a list of multiplayer games is that the leave was asked for more. ggfgbddbffad

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