[ZJ e156] 良心題: 求和

原題： e156. 良心題: 求和 - 高中生程式解題系統 (zerojudge.tw)

如何不用乘法、除法、<<、>>、~、^，也不用for、while、if、else、switch、case及三元運算子，算出1+2+3+...+n ?

解題方向：

我覺得這一題滿有趣的，分享一些解法，不同寫法用到的語法細節都有點不一樣

解法如下

解 1 : 利用 new 會呼叫建構式來實現類似 for 迴圈的結構

用 new A[N] ，來呼叫 N 次 A 的建構式，再利用變數控制加總即可。

#include <bits/stdc++.h>
using namespace std;

class A {
public:
    A() {
        sum+=cnt++;
    }
    inline static int cnt = 1;
    inline static int sum = 0;
};


int main() {
    int N;
    scanf("%d", &N);
    delete [] new A[N];
    printf("%d\n", A::sum);
}

解 2 : 利用 && 會短路 (shortcut) 的特性來實現 if

#include <bits/stdc++.h>
using namespace std;

int sum(int x) {
    x && (x+=sum(x-1));
    return x;
}

int main() {
    int N;
    scanf("%d", &N);
    printf("%d\n", sum(N));
}

解 3 : 其實用 STL ，加上 algorithm 的函數就兜得出來了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int N;
    scanf("%d", &N);

    vector<int> v(N);
    iota(v.begin(), v.end(), 1);
    printf("%d\n", accumulate(v.begin(), v.end(), 0));
}

[ZJ b936] b936: Kevin 愛橘子

 原題： b936. Kevin 愛橘子 - 高中生程式解題系統 (zerojudge.tw)

解題方向：觀察

題目要求把 $n$ 不斷剖半 ( 遇到奇數就分成 $x,x+1$ )，問至少能分成幾塊，使每一塊大小至少為 $m$ 。

假設 $n \geq m$：

很顯然的，如果 $n=m\times 2^{k}$ ，答案為 $2^{k}$ 。

因此，我們要來討論 $n=m\times 2^{k}+r$，的情形，當中 $1\leq r < m\times 2^{k}$ 

根據觀察可以發現，每當 $r$ 增加 $2^{k}$ ，所有最後切下的部位就會增加 $1$：

比如說 

$n=25,m=6$ 時，會得到切除的結果是 $\{7,6,6,6\}, r=1$

$n=26,m=6$ 時，會得到切除的結果是 $\{7,7,6,6\}, r=2$

$n=27,m=6$ 時，會得到切除的結果是 $\{7,7,7,6\}, r=3$

$n=28,m=6$ 時，會得到切除的結果是 $\{7,7,7,7\}, r=4$

$n=29,m=6$ 時，會得到切除的結果是 $\{8,7,7,7\}, r=5$

因此，我們可以發現，當 $r\leq (m-1)\times 2^k$ 時，不影響答案，但是當 $r$ 大於 $ (m-1)\times 2^k$ 時，就會讓增加的項可以被近一步分割 !

比如說 

$n=43,m=6$ 時，會得到切除的結果是 $\{11,11,11,10\}, r=19$

$n=44,m=6$ 時，會得到切除的結果是 $\{11,11,11,11\}, r=20$

$n=45,m=6$ 時，會得到切除的結果是 $\{6,6,11,11,11\}, r=21$

原本是 $12$的項能被近一步分解為 $6,6$，因此分割數加了。

故我們可以得到下公式

$n = m\times 2^{k}+r$

$f(n)=\begin{cases}2^k&0\leq r\leq (m-1)\times 2^k\\2^k+t&(m-1)\times 2^k+t=r& t>0\end{cases}$

故得證。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ll n, m;
    while (~scanf("%lld%lld", &n, &m)) {
        if (n<m) {
            puts("0");
            continue;
        }

        long long P = 0;
        for(int i=0;n>=m*(1LL<<i);i++) {
            P = i;
        }
        long long R = n - m*(1LL<<P);

        long long ans = 1LL<<P;
        if (R > (m-1) * (1LL<<P))
            ans += R - (m-1) * (1LL<<P);

        printf("%lld\n", ans);

    }
    return 0;
}

[ZJ a134][UVA 00948] Fibonaccimal Base

原題： a134. 00948 - Fibonaccimal Base - 高中生程式解題系統 (zerojudge.tw)

解題方向：觀察、進位制

根據觀察，如果我們把一個數字去盡可能大的費式數，就能構造題目要求沒有連續 $1$ 的答案。

證明：

設 $x$ 足夠大，能被兩個相鄰的費式數夾擠，也就是 $F_{n+1}>x \geq F_{n}$。

如果要有不相鄰的 $1$ ，那麼 $x-F_{n}$ 就要小於 $F_{n-1}$。

根據定義

$F_{n+1}=F_{n}+F_{n-1} > x$

移項

$F_{n-1} > x - F_{n}$

故得證。

#include<bits/stdc++.h>
using namespace std;

int main() {
    long long f[40] = {1, 2, 0};
    for(int i=2;i<40;++i)
        f[i] = f[i-1] + f[i-2];
    reverse(f, f+40);

    int N, x;
    cin >> N;
    while (N--) {
        cin >> x;
        cout << x << " = ";

        bool leadZero = true;
        for(long long v:f) {
            if (x >= v) {
                leadZero = false;
                cout << 1;
                x-=v;
            } else {
                if (!leadZero) cout << 0;
            }
        }

        cout << " (fib)\n";
    }
    return 0;
}