[PKU] P1306: Combinations
Description
Computing
the exact number of ways that N things can be taken M at a time can be
a great challenge when N and/or M become very large. Challenges are the
stuff of contests. Therefore, you are to make just such a computation
given the following:
GIVEN: 5 <= N <= 100; 5 <= M <= 100; M <= N
Compute the EXACT value of: C = N! / (N-M)!M!
You may assume that the final value of C will fit in a 32-bit
Pascal LongInt or a C long. For the record, the exact value of 100! is:
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,
468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,
697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000
the exact number of ways that N things can be taken M at a time can be
a great challenge when N and/or M become very large. Challenges are the
stuff of contests. Therefore, you are to make just such a computation
given the following:
GIVEN: 5 <= N <= 100; 5 <= M <= 100; M <= N
Compute the EXACT value of: C = N! / (N-M)!M!
You may assume that the final value of C will fit in a 32-bit
Pascal LongInt or a C long. For the record, the exact value of 100! is:
93,326,215,443,944,152,681,699,238,856,266,700,490,715,968,264,381,621,
468,592,963,895,217,599,993,229,915,608,941,463,976,156,518,286,253,
697,920,827,223,758,251,185,210,916,864,000,000,000,000,000,000,000,000
Input
The
input to this program will be one or more lines each containing zero or
more leading spaces, a value for N, one or more spaces, and a value for
M. The last line of the input file will contain a dummy N, M pair with
both values equal to zero. Your program should terminate when this line
is read.
input to this program will be one or more lines each containing zero or
more leading spaces, a value for N, one or more spaces, and a value for
M. The last line of the input file will contain a dummy N, M pair with
both values equal to zero. Your program should terminate when this line
is read.
Output
The output from this program should be in the form:
N things taken M at a time is C exactly.
N things taken M at a time is C exactly.
Sample Input
|
1 |
100 6<br>20 5<br>18 6<br>0 0 |
Sample Output
|
1 |
100 things taken 6 at a time is 1192052400 exactly.<br>20 things taken 5 at a time is 15504 exactly.<br>18 things taken 6 at a time is 18564 exactly. |
Source
Solution:
[#M_ more.. | less.. ||
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
import java.math.BigInteger; import java.util.*; public class P1306 { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); while(true){ String temp = sc.nextLine(); StringTokenizer st = new StringTokenizer(temp, " "); String sn = st.nextToken(); String sm = st.nextToken(); int n =Integer.parseInt(sn); int m = Integer.parseInt(sm); if(n==0){ break; } BigInteger bn = new BigInteger(sn); BigInteger bm = new BigInteger(sm); BigInteger answer; answer = (factorial(bn).divide(((factorial(bn.subtract(bm)).multiply(factorial(bm)))))); System.out.println(bn+" things taken "+bm+" at a time is "+answer+" exactly."); } } public static BigInteger factorial( BigInteger n ) { if( n.compareTo(new BigInteger("1"))<=0 ) // base case return new BigInteger("1"); else return n.multiply(factorial( n.subtract(new BigInteger("1")))); } } |
![[PKU] P3062: Celebrity jeopardy](https://www.bpak.org/blog/wp-content/themes/hueman/assets/front/img/thumb-medium-empty.png)