UVa11236 - Grocery store (數論 Math theorm、暴力搜尋 Brute force)

題目大意

雜貨店的收銀員不太懂加號跟乘號這兩個意思，為了要讓他更容易理解，因此在你買雜貨店的商品時，你想要讓你買的四項商品總和價格等同於你買的四項商品價格乘積，四項商品都是相同的商品。

總共不可以大於 20 元，雜貨店的商品價格範圍在 0.00 ~ 20.00 範圍內，小數點前兩位都是合理的價位。
輸出時，四個商品價格必須是遞增

重點觀念

• 了解小數點不夠精確，因此必須化為整數運算
• 對於暴力搜尋進行優化
  • 反推最後一項商品價錢
  • 暴力搜尋的範圍優化
  • 解決小數會越乘越小的問題

分析

好題，好題，沒想到 UVa 裡面也有類似於 Codeforces 的題目呢。

我們來進行一些分析，首先由於我們知道電腦對於小數運算並不精確，假如小數數字連續乘四，有非常高的機率會使浮點數運算有誤差，導致無法 AC，因此我們的第一件事情就是要用整數來解決此題。

擴分公式

根據題目的方程式，我們現在定義 \(p_1,p_2,p_3,p_4\)，是我們 4 個商品的價錢，因此公式要如下
\(p_1p_2p_3p_4 = p_1 + p_2 + p_3 p_4\)

接下來我們要進行擴分，這樣我們才可以用整數進行運算，我們定義括分 100 倍的價錢為 \(a_1 , a_2 , a_3 , a_4\)

• \(\frac{a_1}{100} \frac{a_2}{100} \frac{a_3}{100} \frac{a_4}{100} = \frac{a_1}{100}+ \frac{a_2}{100} + \frac{a_3}{100} \frac{a_4}{100}\)
• 稍微化簡下，成為 \(\frac{a_1 a_2 a_3 a_4}{10^8} = \frac{a_1+a_2+a_3+a_4}{100} \)
• 移項，\(\frac{a_1 a_2 a_3 a_4}{10^6} = a_1+a_2+a_3+a_4\)
• 分母移項 \((a_1+a_2+a_3+a_4) 10^6 = a_1 a_2 a_3 a_4 \)
• 透過此方程式，就可以用整數來寫出題目所需要的答案

優化迴圈

由於我們還知道一件事情是，總共不能大於 20 元，且商品價格要遞增，因此大家比較容易想到的是迴圈不斷的遞增，但其實我們也可以減少迴圈的上限，來更加優化，如下

for(int a1 = 1; a1 <= 2000; a1++){
    for(int a2 = a1; a2 <= 2000-a1; a2++ ){ 
        for(int a3 = a2; a3 <= 2000-a1-a2; a3++){
            for(int a4 = a3; a4 <= 2000-a1-a2-a3; a4++){

            }
        }
    }
}

其中可以注意到，a2,a3,a4 他們的迴圈上限都有被縮小，是因為題目除了要數值遞增，並且還不能超過 2000，那麼 a1 用掉的錢勢必也在 20 元以內，才可以透過這樣進行優化。

而遞增，減少下限就是大家比較熟悉的，不多做解釋。

設定檢查點

其中我們可以知道公式是 \((a_1+a_2+a_3+a_4) 10^6 = a_1 a_2 a_3 a_4 \)，但這裡有一個大問題，原先的題目數值是小數，如果是 \(0.1(0.2)\) 的情況下是越乘越小的，但整數的情況並不是，0因此才會有一個 \(10^6\) 的情況出現，所以反之，也就是說如果 \(a_1 a_2 a_3 a_4 <= 10^6\) 的情況下表示四個數值都是 \(> 1\)，乘積只會越來越小，必定不符合題目需求。

\(10^6\) 是因為我們先擴分 100 倍，才會有的限制器。

減少迴圈數量

先提一個概念，\(x+y=10\)，如果我們知道 x 的情況，那 y 是不是可以移項得出。
所以 \(a_1 + a_2 + a_3 + a_4 = A\)，如果前三項與 A 都知道那 \(a_4\) 也可以被得知。

因此我們來進行移項與定義

• 定義 \(a_1+a_2+a_3\) 為 sum
• 定義 \(a_1 a_2 a_3\) 為 product
• 定義 \(10^6\) 為 c
• 因此 \((a_1+a_2+a_3+a_4) 10^6 = a_1 a_2 a_3 a_4 = c(sum + p_4) = product (p_4)\)
• 左項乘開 \(c(sum + p_4) = product (p_4)\)
• 再來移項 \(c(sum) + c(p_4) = product (p_4) \)
• 移項 \(c(sum) = product(p_4) - c(p_4)\)
• 結合 \(c(sum) = p_4(product - c)\)
• 移項 \(p_4 = \frac{c(sum)}{(product - c)}\)

擴分後的限制

再來我們知道了這公式後，我們還有幾個題目的限制要注意

• \(c(sum) % (product - c) == 0\) 因為我們進行擴分，因此如果沒有剛好 mod 等同於 0 時，表示其實此數值在縮小 100 倍後則不會剛好符合題目要求。表示 \(a_4\) 可能需要小數後 x 位才能符合題目要求，其中 x 必須大於 2。
• \(p_3 < p_4\)，題目要求
• \(sum + p_4 \leq 2000\)，因為我們將 20 放大 100 倍
• \(product(p_4) \leq 2(10^9)\)，由於 \(\frac{a_1 a_2 a_3 a_4}{10^8}\)，縮小 100 倍後不可以超過 20 元。注意，這裡的縮小 100 倍是每個 \(a\) 都縮小 100 倍，全部則是縮小 \(10^8\)

參考連結

EQUATION SOLVING IS THE KEY TO UVA 11236 by Red-Green-Code
UVa 11236 - Grocery store by geniustanley

心得

這題很有趣RRR，完全不用輸入測資卻可以讓人有著這麼多的腦力激盪，其實很有趣R。

總之學到了很多，但我也是看著詳解一步一步慢慢地去學習，或許我的腦袋其實沒有很聰明，但我會透過學習來讓自己也能夠跟上一般人的腳步。

希望大家可以包容這樣的我，不夠聰明的我。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 2*1e9 // 四項商品乘積放大 100 倍的值
#define int long long //避免溢位
using namespace std;
int c = 1e6; //將他進行第溢

//add more fast than product
void solve(){
    for(int a1 = 1; a1 <= 2000; a1++){
        //if(pow(a1,4) >= MAXN) break; //注意，加法運算比乘法快。
        if(a1+a1+a1+a1 > 2000) break; //如果這邊就超過 2000，後面沒辦法遞增部符合題目要求
        for(int a2 = a1; a2 <= 2000-a1; a2++ ){ 
            //if(a1+pow(a2,3) >= MAXN) break;
            if(a1+a2+a2+a2 > 2000) break; //如果這邊就超過 2000，後面沒辦法遞增部符合題目要求
            for(int a3 = a2; a3 <= 2000-a1-a2; a3++){
                //if(a1+a2+pow(a3,2) >= MAXN) break;
                if(a1+a2+a3+a3 > 2000) break; //如果這邊就超過 2000，後面沒辦法遞增部符合題目要求

                int sum = a1 + a2 + a3;
                int product = a1 * a2 * a3;
                if(product <= c) continue;
                if((sum*c) % (product-c) != 0) continue; //mod != 0 

                //上方擴分後的限制有提到
                int a4 = (sum*c) / (product-c);
                if(a3 > a4) continue;
                if(sum + a4 > 2000) continue;
                if(product * a4 > MAXN) continue;
                cout << fixed << setprecision(2) << a1/100.0 << ' ' << \
                    fixed << setprecision(2) << a2/100.0 << ' ' << \
                    fixed << setprecision(2) << a3/100.0 << ' ' << \
                    fixed << setprecision(2) << a4/100.0 << '\n';
                //小數運算
            }
        }
    }
}

int32_t main()
{

    solve();
    return 0;
}