欧拉计划个人题解(016-020)

algorithm
Project Euler, algorithm
文章目录
  1. 1. [016]Power digit sum
  2. 2. [017]Number letter counts
  3. 3. [018] Maximum path sum I
  4. 4. [019] Counting Sundays
  5. 5. [020]Factorial digit sum

[016]Power digit sum

题意

求$2^{1000}$的每数位之和。

思路

高精度乘法，并利用快速幂优化。

代码

C++\STL

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
class BigInt
{
public:
    BigInt(int num);
    BigInt(const BigInt&);
    BigInt(BigInt&& o) noexcept;
    BigInt& operator = (const BigInt&);
    static BigInt Zero();
    static BigInt One();

    bool operator == (const BigInt&) const;
    BigInt& operator ++(); //++i
    BigInt& operator --(); //--i
    BigInt operator +(const BigInt&);
    BigInt operator +=(const BigInt&);
    BigInt operator *(const BigInt&);
    BigInt operator *=(const BigInt&);

    inline size_t& size();
    inline size_t size() const;
    string toString() const;
    ~BigInt();

    friend ostream& operator << (ostream& out, const BigInt& o)
    {
        auto ptr = o.m_num + o.size();
        do{
            --ptr;
            out << *ptr;
        }while(ptr != o.m_num);
        return out;
    }
private:
    BigInt();
    int* m_num;
    size_t m_size;
    void format();
};
size_t& BigInt::size()
{
    return m_size;
}
size_t BigInt::size() const
{
    return m_size;
}
BigInt::BigInt()
{
}
BigInt::~BigInt()
{
    if(m_num != nullptr)
    delete[] m_num;
    m_size = 0;
}
BigInt::BigInt(int num)
{
    size_t cnt = 0;
    {
        int tmp = num;
        do{
            ++cnt;
            tmp /= 10;
        }while(tmp != 0);
    }
    size() = cnt;
    m_num = new int[size()];
    auto ptr = m_num;
    do{
        *ptr = num % 10;
        num /= 10;
        ++ptr;
    }while(num != 0);
}
BigInt::BigInt(const BigInt& o)
{
    size() = o.size();
    m_num = new int[size()];
    memcpy(m_num, o.m_num, size() * sizeof(int));
}
BigInt::BigInt(BigInt&& o) noexcept
{
    size() = o.size();
    m_num = o.m_num;
    //delete;
    o.size() = 0;
    o.m_num = nullptr;
}
BigInt& BigInt::operator = (const BigInt& o)
{
    size() = o.size();
    if(m_num != nullptr)
        delete [] m_num;
    m_num = new int[size()];
    memcpy(m_num, o.m_num, size() * sizeof(int));
    return *this;
}
BigInt BigInt::Zero()
{
    BigInt a(0);
    return a;
}
BigInt BigInt::One()
{
    BigInt a(1);
    return a;
}
bool BigInt::operator==(const BigInt& o) const
{
    if(size() != o.size())
        return false;
    for(size_t i = 0; i < size(); ++i)
        if(m_num[i] != o.m_num[i])
            return false;
    return true;
}
BigInt& BigInt::operator ++()
{
    ++m_num[0];
    format();
    return *this;
}
BigInt& BigInt::operator --()
{
    --m_num[0];
    format();
    return *this;
}
void BigInt::format()
{
    // Carry
    for(size_t i = 0; i < size() - 1; ++i)
        if(m_num[i] >= 10)
        {
            m_num[i+1] += m_num[i] / 10;
            m_num[i] %= 10;
        }
        else
            if(m_num[i] < 0)
            {
                int cnt = (m_num[i] / 10 + 1);
                m_num[i] += cnt * 10;
                m_num[i+1] -= cnt;
            }
    // Stretch out digital
    if(m_num[size() - 1] >= 10)
    {
        int* new_num = new int[size() + 1];
        memcpy(new_num, m_num, size() * sizeof(int));
        new_num[size()] = new_num[size() - 1] / 10;
        new_num[size() - 1] %= 10;
        ++size();
        if(m_num != nullptr)
            delete [] m_num;
        m_num = new_num;
    }
    // Draw back digital
    if(size() == 1)
        return;
    auto ptr = m_num + size();
    do{
        --ptr;
        if(*ptr != 0)
            break;
    }while(ptr != m_num);
    size_t new_size = static_cast<size_t>(ptr - m_num + 1);
    if(size() != new_size)
    {
        int* new_num = new int[new_size];
        memcpy(new_num, m_num, new_size * sizeof(int));
        if(m_num != nullptr)
            delete [] m_num;
        m_num = new_num;
        size() = new_size;
    }
}
BigInt BigInt::operator +(const BigInt& o)
{
    BigInt ans;
    size_t length = max(size(), o.size());
    ans.m_num = new int[length];
    ans.size() = length;
    for(size_t i = 0; i < min(size(), o.size()); ++i)
        ans.m_num[i] = m_num[i] + o.m_num[i];
    if(size() > o.size())
        for(size_t i = o.size(); i < size(); ++i)
            ans.m_num[i] = m_num[i];
    else
        for(size_t i = size(); i < o.size(); ++i)
            ans.m_num[i] = o.m_num[i];
    ans.format();
    return ans;
}
BigInt BigInt::operator+=(const BigInt& o)
{
    if(size() < o.size())
    {
        int* new_num = new int[o.size()];
        memcpy(new_num,m_num,size());
        for(size_t i = size(); i < o.size(); ++i)
            new_num[i] = 0;
        delete [] m_num;
        m_num = new_num;
    }
    for(size_t i = 0; i < o.size(); ++i)
        m_num[i] += o.m_num[i];
    format();
    return *this;
}
BigInt BigInt::operator *=(const BigInt& o)
{
    size_t new_size = size() + o.size() - 1;
    int* new_num = new int[new_size];
    memset(new_num, 0, new_size * sizeof(int));
    for(size_t i = 0; i < size(); ++i)
        for(size_t j = 0; j < o.size(); ++j)
            new_num[i + j] += m_num[i] * o.m_num[j];
    size() = new_size;
    delete [] m_num;
    m_num = new_num;
    format();
    return *this;
}
BigInt BigInt::operator *(const BigInt& o)
{
    BigInt ans;
    size() = size() + o.size() - 1;
    ans.m_num = new int[size()];
    memset(ans.m_num, 0, size() * sizeof(int));
    for(size_t i = 0; i < size(); ++i)
        for(size_t j = 0; j < o.size(); ++j)
            ans.m_num[i + j] += m_num[i] * o.m_num[j];
    ans.format();
    return ans;
}
string BigInt::toString() const
{
    char* str = new char[size() + 1];
    for(size_t i = 0; i < size(); ++i)
        str[size() - i - 1] = static_cast<char>(m_num[i] + '0');
    str[size()] = '\0';
    string ans = string(str);
    delete str;
    return ans;
}
BigInt mulpow(BigInt base, int index)
{
    BigInt ans = BigInt::One();
    while(index != 0)
    {
        if(index & 1)
            ans *= base;
        index >>= 1;
        base *= base;
    }
    return ans;
}
int main()
{
    BigInt ans = mulpow(BigInt(2), 1000);
    string str = ans.toString();
    int count = 0;
    for(auto iter = str.begin(); iter != str.end(); ++iter)
        count += (*iter) - '0';
    cout <<count << endl;
    return 0;
}

答案

1366

[017]Number letter counts

题意

统计1到1000的数字，英文写法的字符和(包括连字符)。

思路

根据规律统计。

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
个位数：
zero   4
one    3
two    3
three  5
four   4
five   4
six    3
seven  5
eight  5
nine   4
两位数：
ten        3
eleven     6
twelve     6
thirteen   8
fourteen   8
fifteen    7
sixteen    7
seventeen  9
eighteen   8
nineteen   8
twenty     6
twenty-one 9
...
thirty     6
forty      5
fifty      5
sixty      5
seventy    7
eighty     6
ninety     6
三位数：
one hundred         10
one hundred and one 16
...
四位数：
one thousand 11

C++\STL

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
int main()
{
    const int HUNDRED = 7;
    const int THOUSAND = 8;
    const int AND = 3;
    const int single_digit[9] = {3, 3, 5, 4, 4, 3, 5, 5, 4};
    const int double_digit_1[10] = {3, 6, 6, 8, 8, 7, 7, 9, 8, 8};
    const int double_digit_2[8] = {6, 6, 5, 5, 5, 7, 6, 6};
    // calc 1 - 9
    int single_count = 0;
    for(auto e : single_digit)
        single_count += e;
    
    // calc 10~19
    int double_count = 0;
    for(auto e : double_digit_1)
        double_count += e;
    
    // calc 20 ~ 99
    for(auto e : double_digit_2)
        double_count += e * 10 + single_count;

    // calc 100 ~ 999
    int three_count = 0;
    for(auto e : single_digit)
    {
        three_count += (e + HUNDRED) * 1; // 100 200 300 ...
        three_count += (e + HUNDRED + AND) * 9 + single_count; // 101 ... 201 ...
        three_count += (e + HUNDRED + AND) * 90 + double_count; // 110 ... 210 ...
    }

    // calc 1000
    int four_count = single_digit[0] + THOUSAND;

    cout << single_count + double_count + three_count + four_count << endl;
    return 0;
}

答案

21124

[018] Maximum path sum I

题意

给出一个空间结构类似杨辉三角的一些数字，有十五层，最上层有一个数字，最下层有十五个数字。找出从最上层到最下层一条连续的路径，使这条路径上的数字代数和最大。

思路

简单动态规划。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int MAXN = 100;
int maps[MAXN+1][MAXN+1];
int dp[MAXN+1][MAXN+1];
int max(int a,int b)
{
    return (a > b) ? a : b;
}
int main(void)
{
    for(int i = 1; i <= MAXN; ++i)
        for(int j = 1; j <= i; ++j)
            cin >> maps[i][j];
    for(int i = MAXN - 1; i >= 1; --i)
    {
        for(int j = 1; j <= i; ++j)
            dp[i][j] = max(dp[i+1][j] + maps[i+1][j], dp[i+1][j+1] + maps[i+1][j+1]);
    }
    cout << dp[1][1] + maps[1][1] << endl;
    return 0;
}

答案

1074

相似题目

Maximum path sum II

[019] Counting Sundays

题意

给出下列信息：

  • 1900.01.01 是星期一
  • 四月、六月、九月、十一月有30天
  • 二月平年有28天，闰年有29天
  • 剩余月份均为31天
  • 闰年定义为：任意年可以被4整除，特殊的，对于世纪年需要被400整除。否则就是平年。

问：20世纪（1901年1月1日到2000年12月31日）一共有多少个星期日落在了当月的第一天。

思路

模拟，对每一年每一月都实际进行检测，统计次数，输出。

C++\STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int isLeap(int year, int month)
{
    if(month != 1)
        return 0;
    if(year % 100 == 0)
        return (year % 400 == 0) ? 1 : 0;
    else
        return (year % 4 == 0) ? 1 : 0;
}
int main(void)
{
    const int dayPerMonth[12]={31,28,31,30,31,30,31,31,30,31,30,31};
    int nowDay = 0;
    int ans = 0;
    for(int year = 1901; year <= 2000; ++year)
        for(int month = 0; month < 12; ++month)
        {
            if(nowDay == 0)
                ++ans;
            nowDay = (nowDay + dayPerMonth[month] + isLeap(year, month)) % 7;
        }
    cout << ans << endl;
    return 0;
}

拓展

蔡勒公式
观察，公元元年1月5日是星期五，公元二年1月5日是星期六，公元三年1月5日是星期天，也就是说，平年过一年，星期中的天数只增加一，遇闰年则增加2。于是我们可以从公元元年1月1日是星期一这个事实出发，计算需推算的日子离元年1月1日相距多少天（W），再用天数W除以7的余数加上1就是星期几了。即公式如下

$$
W = \lfloor Y-1 \rfloor + \lfloor \frac{Y-1}{4} \rfloor + \lfloor \frac{Y-1}{400} \rfloor + D \\
W为天数，算出来的结果可正可负，对7取模得到星期几 \\
Y为目标年份，D为目标年份下的天数
$$
这样的公式比较麻烦，每个月的天数是不一致的，2月份还有平闰年之分，蔡勒提出了新的最好用的公式：

$$
W = \lfloor \frac{C}{4} \rfloor - 2 \times C + y + \lfloor \frac{y}{4} \rfloor + \lfloor 13 \times \frac{M+1}{5} \rfloor + d - 1 \\
C为目标年份前两位，y为年份后两位 \\
M为目标月份，d为日数，1月与2月要按上一年的13月和14月来算 \\
$$
蔡勒公式只适合于1582年10月15日之后的情形。罗马教皇格里高利十三世在1582年组织了一批天文学家，根据哥白尼日心说计算出来的数据，对儒略历作了修改。将1582年10月5日到14日之间的10天宣布撤销，继10月4日之后为10月15日。

答案

171

[020]Factorial digit sum

题意

$n!$意为$$1\times2\times3\times … \times n$，即n的阶乘。
现在有 $10! = 3628800$ ，然后 $3 + 6 + 2 + 8 + 8 + 0 + 0 = 27$ 。
现在求 $100!$ 的各数位之和。

思路

使用我之前的大数乘法模版，代码略。

答案

648