UVa/uva-10268.cpp at master · debugster/UVa · GitHub

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
104
105
106
107
108
#include <bits/stdc++.h>

using namespace std;

/* typedef starts */

typedef long long ll;
typedef unsigned long long ull;

/* typedef ends */

/* macro starts */

#define PI acos(-1.0)
#define MAX 1000005

/* macro ends */

/* function starts */

/// calculates n-th (0-based) Gray Code
template<typename dataType>
dataType nthGrayCode(dataType n)
{
    return (n ^ (n >> 1));
}

/// extracts numbers from a string and pushes into vector
template<typename dataType>
void extractNumberFromString(string str, vector<dataType> &v)
{
    stringstream ss;

    /* Storing the whole string into string stream */
    ss << str;

    /* Running loop till the end of the stream */
    string temp;
    dataType found;
    v.clear();
    while (!ss.eof()) {

        /* extracting word by word from stream */
        ss >> temp;

        /* Checking the given word is integer or not */
        if (stringstream(temp) >> found) {
            //cout << found << " " << sizeof(found) << "\n";
            v.push_back(found);
        }

        /* To save from space at the end of string */
        temp = "";
    }
}

/* function ends */

vector<ll>allC;
ll P[MAX];

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    ll c, x, i, j, n;
    string strC;

    while (scanf("%lld", &x) != EOF) {
        getchar();
        getline(cin, strC);

        //cout << strC << "\n";

        extractNumberFromString(strC, allC);

        /*
        for (i = 0; i < allC.size(); i++) {
            printf("%d ", allC[i]);
        }
        printf("\n");
        */

        /// Applying Horner's Rule
        n = allC.size() - 1;
        reverse(allC.begin(), allC.end());

        if (!x) {
            if (n == 0) {
                printf("0\n");
            }
            else {
                printf("%lld\n", allC[1]);
            }
            continue;
        }

        P[n] = allC[n] * n;
        allC[0] = 0;
        for (i = n - 1, j = 1; i >= 0; i--, j++) {
            P[i] = (P[i + 1] * x) + (allC[i] * n) - (allC[i] * j);
        }
        printf("%lld\n", P[0] / x);
    }

    return 0;
}