[UVa]10219 - Find the ways !

Find the ways !

The Problem

An American, a Frenchman and an Englishwoman had been to Dhaka, the capital of Bangladesh. They went sight-seeing in a taxi. The three tourists were talking about the sites in the city. The American was very proud of tall buildings in New York. He boasted to his friends, "Do you know that the Empire State Building was built in three months?"

"Really?" replied the Frenchman. "The Eiffel Tower in Paris was built in only one month! (However, The truth is, the construction of the Tower began in January 1887. Forty Engineers and designers under Eiffel's direction worked for two years. The tower was completed in March 1889.)

"How interesting!" said the Englishwoman. "Buckingham Palace in London was built in only two weeks!!"

At that moment the taxi passed a big slum ( However, in Bangladesh we call it "Bostii"). "What was that? When it was built ?" The Englishwomen asked the driver who was a Bangladeshi.

"I don't know!" , answered the driver. "It wasn't there yesterday!"

However in Bangladesh, illegal establishment of slums is a big time problem. Government is trying to destroy these slums and remove the peoples living there to a far place, formally in a planned village outside the city. But they can't find any ways, how to destroy all these slums!

Now, can you imagine yourself as a slum destroyer? In how many ways you can destroy k

slums out of n slums ! Suppose there are 10 slums and you are given the permission of destroying 5 slums, surly you can do it in 252 ways, which is only a 3 digit number, Your task is to find out the digits in ways you can destroy the slums !

The Input

The input file will contain one or more test cases.
Each test case consists of one line containing two integers n (n>=1) and k (1<=<k=<n).

The Output

For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 2^31-1.

Sample Input

20 5
100 10
200 15

Sample Output

5
14
23

------------------------------------------------------------------------------------------------------------



解法說明：這題簡單的說題目要求的就是給定兩正整數 n, k ，然後要你求出C(n,k)是多少位數，其實並不用真正求出C(n,k)是多少，只要利用對數的運算規則，真數相乘對數相加，就可以簡單的算出答案。

#include <cstdio> #include <cmath> int main() { int n, k, i; double sum; while( scanf( "%d %d", &n, &k ) == 2 ) { sum = 0; k = ( n/2 > k ? k : n-k ); i = 0; while( i < k ) sum += log10(n--) - log10(++i); printf( "%d\n", (int)sum + 1 ); } return 0; }

程式碼連結：http://codepad.org/LHAtF5c