import java.util.*;
import java.lang.*;
 
/**
 * To answer the question "How many combinations of coins add up to $1.00". US
 * currency is assumed. Reptition is assumed. Does not calculate permutations
 * where position is important.
 **/
class Main
{
 
    public static void main (String[] args) throws java.lang.Exception
	{
        Main main = new Main();
        main.run();
	}
 
    private void run(){
        // initialize array so that c[0] = 1 and c[i] = 0 for all i > 0
		int[] c = new int[101];
		c[0] = 1;
		for(int i = 1; i < 101; i++){
			c[i] = 0;
		}
 
		// For k=1,5,10,25,50 (in any order) do:
		int[] k = new int[5];
 
		k[0] = 1;
		k[1] = 5;
		k[2] = 10;
		k[3] = 25;
		k[4] = 50;
 
		for (int m = 0; m < 5; m++){
			int max = (100 - k[m]);
			//for i=0,1,…,100-k (in this order) do:
			for(int i = 0; i <= max; i++){
				//add c[i] to c[i+k]
				c[i+k[m]] += c[i];
			}
		}
 
        System.out.println("There are " + c[100] + " possible combinations.");
    }
 
}

aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CgovKioKICogVG8gYW5zd2VyIHRoZSBxdWVzdGlvbiAiSG93IG1hbnkgY29tYmluYXRpb25zIG9mIGNvaW5zIGFkZCB1cCB0byAkMS4wMCIuIFVTCiAqIGN1cnJlbmN5IGlzIGFzc3VtZWQuIFJlcHRpdGlvbiBpcyBhc3N1bWVkLiBEb2VzIG5vdCBjYWxjdWxhdGUgcGVybXV0YXRpb25zCiAqIHdoZXJlIHBvc2l0aW9uIGlzIGltcG9ydGFudC4KICoqLwpjbGFzcyBNYWluCnsKICAgIAogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4gKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBqYXZhLmxhbmcuRXhjZXB0aW9uCgl7CiAgICAgICAgTWFpbiBtYWluID0gbmV3IE1haW4oKTsKICAgICAgICBtYWluLnJ1bigpOwoJfQogICAgCiAgICBwcml2YXRlIHZvaWQgcnVuKCl7CiAgICAgICAgLy8gaW5pdGlhbGl6ZSBhcnJheSBzbyB0aGF0IGNbMF0gPSAxIGFuZCBjW2ldID0gMCBmb3IgYWxsIGkgPiAwCgkJaW50W10gYyA9IG5ldyBpbnRbMTAxXTsKCQljWzBdID0gMTsKCQlmb3IoaW50IGkgPSAxOyBpIDwgMTAxOyBpKyspewoJCQljW2ldID0gMDsKCQl9CgkJCgkJLy8gRm9yIGs9MSw1LDEwLDI1LDUwIChpbiBhbnkgb3JkZXIpIGRvOgoJCWludFtdIGsgPSBuZXcgaW50WzVdOwoJCQoJCWtbMF0gPSAxOwoJCWtbMV0gPSA1OwoJCWtbMl0gPSAxMDsKCQlrWzNdID0gMjU7CgkJa1s0XSA9IDUwOwoJCQoJCWZvciAoaW50IG0gPSAwOyBtIDwgNTsgbSsrKXsKCQkJaW50IG1heCA9ICgxMDAgLSBrW21dKTsKCQkJLy9mb3IgaT0wLDEs4oCmLDEwMC1rIChpbiB0aGlzIG9yZGVyKSBkbzoKCQkJZm9yKGludCBpID0gMDsgaSA8PSBtYXg7IGkrKyl7CgkJCQkvL2FkZCBjW2ldIHRvIGNbaStrXQoJCQkJY1tpK2tbbV1dICs9IGNbaV07CgkJCX0KCQl9CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiVGhlcmUgYXJlICIgKyBjWzEwMF0gKyAiIHBvc3NpYmxlIGNvbWJpbmF0aW9ucy4iKTsKICAgIH0KICAgIAp9