include fstream include string include algorithm include cassert inclu

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <fstream>
#include <string>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <stdio.h>
using namespace std;
string no_trailing_zeros( string x ) // отрезание нулей в конце строки,
кроме первого
{
int pos = x.find_last_not_of("0");
if (pos == -1)
return "0";
return x.substr( 0, pos+1 );
}
int digit( string x, int xlen, int ind ) { return ind < xlen ? (x[ind] -
'0') : 0; } // дополнение нулями
string rev( string x ) { reverse( x.begin(), x.end() ); return x; } //
переворачиваем строку назад
string mul( const string& a, const string& b ) // умножаем a*b где a b
-- перевернутые строки
{
int la = a.length(), lb = b.length(); // запомним чтобы в цикле не
вычислять
string c; // result
int carry =0;
for (int k=0; k < la + lb -1; k++)
{
for (int i=k; i>=0; i--)
carry += digit(a, la, i)* digit(b, lb, k-i);
c += char( carry%10 + '0' );
carry /= 10;
}
while (carry)
{
c+= '0'+(carry%10);
carry/=10;
}
return c;
}
#if _DEBUG
#define INPUT_TXT "/temp/input.txt"
#define OUTPUT_TXT "/temp/output.txt"
#else // server?
#define INPUT_TXT "INPUT.TXT"
#define OUTPUT_TXT "OUTPUT.TXT"
#endif
bool test()
{
for (int t=0; t<100000; t++)
{
int a = rand() % 0x7000; int b = rand() % 0x7000;; int c = a* b;
char aa[256]={}; char bb [256]={}; char cc [256]={};
sprintf(aa, "%d", a); sprintf(bb, "%d", b); sprintf(cc, "%d", c);
string ab = rev( mul ( rev(aa), rev(bb) ) );
if ( ab != string( cc ) )
{
cout << a << '*' << b << '=' << c << endl;
cout << "longmul" << ab << '!=' << cc << endl;
return false; // test not passed
}
}
return true;
}
int main( int argc, char* argv[] )
{
////test(); // поймала за руку на варианте 1243 0
string a,b;
ifstream( INPUT_TXT ) >> a >> b;
string res = no_trailing_zeros( mul ( rev(a), rev(b) ) );
ofstream( OUTPUT_TXT ) << rev( no_trailing_zeros( mul ( rev(a),
rev(b) ) ) );
//ofstream( OUTPUT_TXT ) << rev( mul ( rev(a), rev(b) ) );
return 0;
}