#include <stdio.h> #define E 11 #define D (void) long long int pot[E] = {1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10}; int log10(long long int x) { int r = 0; while (x) { x /= 10; r++; } return r; } int main() { int N, pe = 0, e; long long int x, res = 0, pr = 0, px = 0, tx, tpx, rx, rpx, pl = 0; /* x * 10^e + pl * 10^k + pr */ scanf("%d", &N); while (N--) { int a, b, cr, cl; scanf("%lld", &x); e = 0; if (pe >= E || pr + px * pot[pe] >= x) { a = log10(px); b = log10(x); e = pe - b + a; D("(a, b, e) = (%d, %d, %d)\n", a, b, e); if (a > b) { tpx = px / pot[a - b]; rpx = px % pot[a - b]; tx = x; rx = 0; } else if (a < b) { tpx = px; rpx = 0; tx = x / pot[b - a]; rx = x % pot[b - a]; } else { tpx = px; tx = x; rx = rpx = 0; } if (tpx > tx) { D("tpx > tx (%lld > %lld)\n", tpx, tx); e++; pr = 0; pl = 0; } else if (tpx == tx) { D("tpx == tx (%lld)\n", tpx); pr++; cr = log10(pr); cl = log10(pl); if (cr > e - cl) { D("cr, e, cl = %d, %d, %d\n", cr, e, cl); pl++; pr = 0; if (cr > e || log10(pl) > e) { pl = 0; e++; } } else if (a < b) { pl = 0; } else if (a > b) { pl = rpx; } } else { D("adding only zeros\n"); pr = pl = 0; } if (e - b < E) { pr += pl * pot[e - b]; pl = 0; } res += e; D("%lld (%lld, %lld, %lld)\n", pot[e] * x + pl * pot[e - b] + pr, x, pr, pl); } else { D("%lld [unchanged]\n", x); } px = x; pe = e; } printf("%lld\n", res); return 0; }
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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include <stdio.h> #define E 11 #define D (void) long long int pot[E] = {1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10}; int log10(long long int x) { int r = 0; while (x) { x /= 10; r++; } return r; } int main() { int N, pe = 0, e; long long int x, res = 0, pr = 0, px = 0, tx, tpx, rx, rpx, pl = 0; /* x * 10^e + pl * 10^k + pr */ scanf("%d", &N); while (N--) { int a, b, cr, cl; scanf("%lld", &x); e = 0; if (pe >= E || pr + px * pot[pe] >= x) { a = log10(px); b = log10(x); e = pe - b + a; D("(a, b, e) = (%d, %d, %d)\n", a, b, e); if (a > b) { tpx = px / pot[a - b]; rpx = px % pot[a - b]; tx = x; rx = 0; } else if (a < b) { tpx = px; rpx = 0; tx = x / pot[b - a]; rx = x % pot[b - a]; } else { tpx = px; tx = x; rx = rpx = 0; } if (tpx > tx) { D("tpx > tx (%lld > %lld)\n", tpx, tx); e++; pr = 0; pl = 0; } else if (tpx == tx) { D("tpx == tx (%lld)\n", tpx); pr++; cr = log10(pr); cl = log10(pl); if (cr > e - cl) { D("cr, e, cl = %d, %d, %d\n", cr, e, cl); pl++; pr = 0; if (cr > e || log10(pl) > e) { pl = 0; e++; } } else if (a < b) { pl = 0; } else if (a > b) { pl = rpx; } } else { D("adding only zeros\n"); pr = pl = 0; } if (e - b < E) { pr += pl * pot[e - b]; pl = 0; } res += e; D("%lld (%lld, %lld, %lld)\n", pot[e] * x + pl * pot[e - b] + pr, x, pr, pl); } else { D("%lld [unchanged]\n", x); } px = x; pe = e; } printf("%lld\n", res); return 0; } |