UVa12502 - Three Families(數論 Math theorm )

題目大意

A,B,C 這 3 個家庭共同管理一個花園，其中有一周 C 家庭出去玩，讓 A 與 B 共同去整理花園，當 C 回來時給予一筆錢來感謝 A 與 B 一起整理花園，題目詢問 A 應該要拿到多少錢比較好？

x 為 A 家庭整理花園的時數
y 為 B 家庭整理花園的時數
z 為 C 家庭給予的錢

貼心提示

• 假如 x 為 5、y 為 4、z 為 90，那公式並不是 \(90/(5+4)*5 = 50 \)，需要仔細想想，題目不會告訴你
• 如果用到小數點時請小心使用，建議盡量避免

分析

這題是大坑…，題目寫得很委婉希望你不要用小數..，但其實就是在暗示你說基本上你用有 95% 的機率不會過，另外 5% 是運氣www，然後我就是那 95 % 的人，真難過，嗚嗚嗚。

如果用題目推薦的方法，也就是不使用小數來計算時那我們就需要透過公式，公式推導如下：

• \(\frac{x+y}{3} = one\)，one 為三個家庭都應該要花的時數
• \(x^{\prime} = x - one\)， \(x^{\prime} \) A 家庭多做的時數，如果是負數表示為少做
• \(y^{\prime} = y - one \)，\(x ^ {\prime}\) B 家庭多做的時數，如果是負數表示為少做
• \(z_a = z * \frac{x^{\prime} }{^{\prime}+y^{\prime} } \)，\(z_a\) 為 A 家庭應該獲得的錢
• 將 \(z_a \) 開始進行推導
  \(z_a = z * \frac{x^{\prime} }{x^{\prime}+y^{\prime}} \\ = z * \frac{x - one }{(x -one ) + (y - one)} \\ = z * \frac{(x - \frac{x+y}{3})} { (x - \frac{x+y}{3}) + (y - \frac{x+y}{3}) } \\ = z * \frac{ \frac{2x-y}{3}}{\frac{2x-y}{3} + \frac{2y-x}{3}} \\ = z * \frac{2x-y}{2x-y+2y-x} \\ = z * \frac{(2x-y)}{x+y} \)
• 根據我們得出的結論就可以得到此公式 \(z * \frac{(2x-y)}{x+y}\)，再透過此公式進行計算即可且此計算還可以避免掉小數問題，符合題目需求，讚。(只使用一次除法會產生小數點，是最簡避免方法)

觀念重點

• 思考出這題要帶給你的邏輯觀念
• 公式推導
• 讓你知道在程式中多使用小數點是非常不好的事，盡量避免小數除法
• 如果 A 沒有幫忙工作，反而還少工作此時 A 則不應該拿到薪水，如果計算出來為負也要改為 0
  壞家庭 A
• 享受題目的惡意

參考來源

• UVa：12502－Three Families

心得

這題好機車..，主要任務是將小數點誤差降至最低但是卻又不跟你說明白，有點暗示暗示的概念小討厭阿，查看了 google 上其他大神的詳解後發現他們的解法才是真的強阿，透過不斷推導、不斷優化來找出答案，讓我不禁覺得自己是個笨蛋了…。

不過透過他們的推導也讓我自己對這種類型的題目有了更深的體悟，也讓我思考的觀點有多了一個，學習到了新事物的感覺真的不錯呀，整個腦袋感覺都被提升了一個檔次。

只是題目沒有明示我真的猜不出來…，我不夠熟還需要懂淺規則RRRRR。

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
float t , hr , x , y , z ;
int cost ;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt","r" , stdin) ;
    freopen("out.txt", "w" , stdout);
#endif // LOCAL
    cin >> t ;
    while(t--){
        cin >> x >> y >> z ;
        cost = z * (2 * x - y) / (x + y ) ;
        if(cost < 0 ) cost = 0 ;
        cout << cost << '\n' ;
    }

    return 0;
}

##　思考流程
透過紙筆與黑板而思考而成的片段，放在網路上供我紀念XD

錯誤的思考方向

我在寫程式的時後我一開始有透過我的思考方式來寫出這份題目，但發現有個很重要的問題XD，那就是誤差太大了…。

在透過題目的樣本測資時並沒有錯誤，但在 udebyg 上的測資發現有兩筆答案都少一個數字，我很納悶於是用手重新算了一遍則發現是小數點誤差導致發生其問題。

我一開始寫的程式邏輯如下

• 先算出每個家庭應該要工作的時數，公式是 \((x+y) / 3\)，因為題目有說明所有家庭的打掃速度都是相同
• 由於 C 家庭付出薪水而沒有工作(資本主義的荼毒)，因此我們可以假設成 C 付出的錢等於一個家庭的工作量
• C 付出的薪水除以一個家庭應該要工作的時數，等於 1 小時的薪資
• A 家庭減去一個家庭應該要工作的時數，剩下的時數就是幫 C 工作的時數，再將我們計算好 1 hr 的薪水去乘 A 多工作的時數
• 輸出 A 應該要拿到的薪水

會錯誤的原因 - 誤差

• 第一個誤差
  其實這個邏輯沒有錯，錯就錯在小數點誤差…，一開始必須要算出一個人的工作時數，此時需要除以 3，如果這時候會有小數時就會有誤差
• 第二個誤差
  再來是 C 付出的錢要除以一個家庭應該要工作的時數，如果這時候也除不盡也會有誤差
• 第三個誤差
  再來是 A 家庭要拿到多工作的薪水，如果前面是小數點且有誤差的狀態則會讓誤差被放大，但如果前面兩個誤差都不會發生那就沒有問題XD。

有上面三個誤差，就導致在某些測資上會產生 >= 1 的誤差，因此錯誤，才要透過大神們的推導來寫，只會有一個機會誤差。

舉例 x = 3 , y = 2 , z = 90

錯誤思考

那每個家庭平均的工作量應該要是 (3+2) / 3 = 1.66
由於 C 付出 90 元，因此 90 / 1.66 = 54.21，也就是 1hr 為 54.21 元
3 - 1.66 = 1.34 ，1.34 為 x 多做的部分，因此給他時薪也就是 54.21 * 1.34 = 72.614

正確方向

透過推導公式可以得出 \(90 * \frac{2 * 3 - 2 }{3 + 2 } = 90 * \frac{4}{5} = 72 \)，與錯誤思考相差 0.614 元，因此正確方向比較好，遇到小數點誤差機率降低

錯誤程式碼

放在這裡來紀念寫錯程式碼的我來讓我進步吧XD

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
using namespace std;
float t , hr , x , y , z ;
int cost ;

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt","r" , stdin) ;
    freopen("out.txt", "w" , stdout);
#endif // LOCAL
    cin >> t ;
    while(t--){
        cin >> x >> y >> z ;
        cost = z * (2 * x - y) / (x + y ) ;
        if(cost < 0 ) cost = 0 ;
        cout << cost << '\n' ;
    }

    return 0;
}