[UVa] 10994 - Simple Addition

[UVa] 10994 - Simple Addition

   4月 15, 2018       PM

---

[UVa] 10994 - Simple Addition (題目網址 )

題目

時間限制: 3秒
輸入: int, int

輸入兩個整數 p, q 然後計算出 S(p, q) 的值

$$
\begin{align*}
F(n) = \left\{ \begin{array}{cc}
  n\%10 ,& \hspace{5mm} if\quad(n\%10)>0 \\
  0,& \hspace{5mm} if \quad n=0 \\
  F(n/10),& \hspace{5mm} Otherwise \\
  \end{array} \right.
\end{align*}
$$
$$
S(p,q) = \sum_{i=p}^{q} F(i)$$

解題思維

最直觀的想法為用迴圈從 F(s) 不斷的累加直到 F(q) ，不過這樣會超過題目要求的時間。

稍微想下後發現，F(n)的值都介於 0~9 之間
因此可以把F(n)的數列看成這樣:
(0、1、2  ... 8、9)、F(10)、(1 、2 ... 8、9)、F(20)  ... (1、2 ... F(n))

然後根據函示 F(n) 的定義如果 n 可以被 10 整除，則 F(n) = F(n/10)
再把上面的式子化簡成下面這樣:
(0、1、2  ... 8、9)、F(1)、(1 、2 ... 8、9)、F(2)  ... (1、2 ... F(n))

整理後這樣題目就好解多了!

程式碼解說

這題可以分成三個函式
*回傳的值有可能超過 int 能表示的上限因此用 long long int

1. f => 計算 F(n) 的值。
2. sum => 計算等差級數的總和。
3. f_sum => 計算 S(p, q) 的值，也就是算 F(p) 累加到 F(q) 的總和。

// C++
int f(int n);
long long int sum(int from, int to);
long long int f_sum(int p, int q);

先根據定義寫出一個 F(n) 的函式

// C++
int f(int n)
{
    if(n%10) return n%10;
    else if(!n) return 0;
    else return n/10;
}

再來寫一個計算等差級數總和的函式

// C++
long long int sum(int from, int to)
{
    int count = to - from + 1;

    return (from+to) * count / 2;
}

接下來寫一個函式計算 S(p, q)
先把結尾是 (1~9) 的數字做一個間隔來切割，如下:
0、(1、2 ... 9)、10、(11、12 ... 19)、20、(21、22 ... 29) ...

如果 p 跟 q 在同一個區間的話則直接累加

// C++
if((p/10) == (q/10))
{
    ans += sum(f(p), f(q));
}

若 p 、q 在不同區間的話，先把不能湊成一個完整區間的數字累加起來。
ex:
(8、9)、10、(11、12 ... 18 、 19)、20、(21、22、23)
=> 10、(11、12 ... 18 、 19)、20 為一個完整的區間
=> (8、9) 、 (21、22、23) 不是完整的區間

讓 F(p) 一直累加到 9，並更新 p 的位置到還沒運算的地方

// C++
if(p%10)
{
    ans += sum(f(p), 9);
    p += (10-p%10);
}

作法跟上面類似，從 1 累加到 F(q)，並更新 q 的位置到還沒運算的地方

// C++
if(q%10){
    ans += sum(1, f(q));
    q -= q%10;
}

在來用 p、q 來計算之間有幾個間隔，在乘上每個間隔中的總和

// C++
ans += ((q/10 - p/10) * sum(1, 9));

最後再加上 10 的倍數序列 的總和就可以得出答案了
*若 n 是10的倍數 根據 F(n) 定義也就等同於 F(n/10)

// C++
ans += f_sum(p/10, q/10);

完整程式碼(github)