随笔 - 6, 文章 - 0, 评论 - 3, 引用 - 0
数据加载中……

SRM_420_div2_1000pt

Problem Statement

    

You will be given two positive ints A and B.

Let C be the product of all integers between A and B, inclusive.

The number C has a unique representation of the form C = D * 10^E, where D and E are non-negative integers and the last digit of D is non-zero.

Write a method that will return the value of C formatted as a String of the form "D * 10^E" (quotes for clarity only). Substitute the actual values of D and E into the output. If D has more than 10 digits, only output the first five and the last five digits of D, and separate them by three periods.

 

Definition

    

Class:

PrettyPrintingProduct

Method:

prettyPrint

Parameters:

int, int

Returns:

String

Method signature:

String prettyPrint(int A, int B)

(be sure your method is public)

     

Notes

-The purpose of the last constraint is to disallow inputs where precision problems could arise. 

Constraints

-A will be between 1 and 1,000,000, inclusive.-B will be between A and 1,000,000, inclusive.-If C has more than 10 digits, then the sixth most significant digit of C will be neither 0 nor 9. 

Examples

0)    

1

10

 

Returns: "36288 * 10^2"

1 * 2 * ... * 10 = 3628800 = 36288 * 10^2

 

1)    

7

7

 

Returns: "7 * 10^0"

The product of all numbers between 7 and 7, inclusive, is obviously 7.

 

2)    

211

214

 

Returns: "2038974024 * 10^0"

For this input D has 10 digits.

 

3)    

411

414

 

Returns: "28952...24024 * 10^0"

For this input D has 11 digits. Note that we output three dots even if just one digit is missing in the output.

 

4)    

412

415

 

Returns: "2923450236 * 10^1"

The actual value of C is larger than in the previous example. However, C ends in a zero and therefore D only has 10 digits.

 

5)    

47

4700

 

Returns: "14806...28928 * 10^1163"

 

 

6)    

1

19

 

Returns: "12164...08832 * 10^3"

Note that the last five digits of D can start with a zero.

 

7)    

13

25

 

Returns: "32382...26624 * 10^4"


 1 
 2 #include <cmath>
 3 #include <ctime>
 4 #include <iostream>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8 
 9 typedef long long i64;
10 
11 class PrettyPrintingProduct {
12 public:
13    string prettyPrint( int A, int B );
14 };
15 bool check(int A,int B,i64& D,i64& E){
16     D=1;E=0;
17     for(int i=A;i<=B;i++){
18         D*=i;
19         while(D%10LL==0LL) {
20             D/=10LL;
21             E++;
22         }
23         if(D>10000000000LL) return false;
24     }
25     return true;
26 }
27 
28 string PrettyPrintingProduct::prettyPrint(int A,int B){
29     i64 D,tens;
30     char str[256];
31 
32     if(check(A,B,D,tens)){
33         cout<<D<<" "<<tens<<endl;
34         sprintf(str,"%lld * 10^%lld",D,tens);
35         return str;
36     }
37 
38     i64 a=1,b=1;
39     tens=0;
40     for(int i=A;i<=B;i++){
41         a*=i;
42         b*=i;
43         while(b%10LL==0LL) b/=10LL,tens++;
44         b%=1000000000000LL;
45         while(a>=1000000000000LL) a/=10LL;
46     }
47     while(a>=100000LL) a/=10LL;
48     b%=100000LL;
49     cout<<a<<" "<<b<<" "<<tens<<endl;
50     sprintf(str, "%lld%05lld * 10^%lld", a, b, tens);
51     return str;
52 }
53 


posted on 2008-10-08 16:41 水牛♂Toto 阅读(193) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理