1200: A DP problem ★★☆☆☆ 題組：Problem Set Archive with Online Judge

Presentation on theme: "1200: A DP problem ★★☆☆☆ 題組：Problem Set Archive with Online Judge"— Presentation transcript:

1 1200: A DP problem ★★☆☆☆ 題組：Problem Set Archive with Online Judge
解題者：李協彥 解題日期：2017年5月23日 題意：測資為 𝑡 個一元一次方程式，運算符號只有+或−，𝑥的係數與常數項皆為整數[0~1000]，這題要求出每個方程式的解，以整數下界的形式印出，若方程式無解印出”IMPOSSIBLE，若無限多解需印出”IDENTITY”。

2 透過字串處理之後，整理出等號兩邊的方程式， 即可算出𝑥。 2𝑥-4+5𝑥+300=98𝑥
題意範例：2 2x-4+5x+300=98x  3 x+2=2+x  IDENTITY 解法： 透過字串處理之後，整理出等號兩邊的方程式， 即可算出𝑥。 2𝑥-4+5𝑥+300=98𝑥  a𝑥 + b = c𝑥 + d  𝑥 = 𝑑−𝑏 𝑎−𝑐 字串處理： 逐個字元去讀取，遇到運算子(+ - = x)就總結這一項的數值 解題範例： 38+5x-20-3x+x+0x+9=20x

3 38+5x-20-3x+x+0x+9=20x Positive + Value length ax + b = cx + d a b c d

4 38+5x-20-3x+x+0x+9=20x Positive + Value 3 length 1 ax + b = cx + d a b

5 38+5x-20-3x+x+0x+9=20x Positive + Value 38 length 2 ax + b = cx + d a

6 38+5x-20-3x+x+0x+9=20x Positive + Value 38 length 2 ax + b = cx + d a

7 38+5x-20-3x+x+0x+9=20x Positive + Value 38 length 2 ax + b = cx + d a
38

8 38+5x-20-3x+x+0x+9=20x Positive + Value length ax + b = cx + d a b c d
length ax + b = cx + d a b c d 38

9 38+5x-20-3x+x+0x+9=20x Positive + Value 5 length 1 ax + b = cx + d a b
38

10 38+5x-20-3x+x+0x+9=20x Positive + Value 5 length 1 ax + b = cx + d a b
38

11 38+5x-20-3x+x+0x+9=20x Positive + Value 5 length 1 ax + b = cx + d a b

12 38+5x-20-3x+x+0x+9=20x Positive - Value length ax + b = cx + d a b c d
length ax + b = cx + d a b c d 5 38

13 38+5x-20-3x+x+0x+9=20x Positive - Value 20 length 2 ax + b = cx + d a
18 ax + b = cx + d a b c d 5 38

14 38+5x-20-3x+x+0x+9=20x Positive + Value length ax + b = cx + d a b c d
length Special case  value=1 ax + b = cx + d a b c d 3 18 ax + b = cx + d a b c d 2 18

15 38+5x-20-3x+x+0x+9=20x Positive + Value length 1 ax + b = cx + d a b c
length 1 ax + b = cx + d a b c d 3 18

16 38+5x-20-3x+x+0x+9=20x Positive + Value 9 length 1 ax + b = cx + d a b
18

17 38+5x-20-3x+x+0x+9=20x Positive + Value 9 length 1 ax + b = cx + d a b
27

18 ax + b = cx + d a b c d 3 27 20 𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 =1.58823529
𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 = =1

19 ax + b = cx + d a b c d 3 27 20 𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 =1.58823529
𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 = =1 a == c and b == d  IDENTITY a == c and b != d  IMPOSSIBLE

20 討論： 要印出數值的整數下界，可直接呼叫函式。 #include <math.h> // double floor(double x); double x = 1.234; cout << floor(x) << endl; printf(“%d\n”,floor(x)); 此解法的時間複雜度為 𝑂 𝑛 =𝑙𝑖𝑛𝑒𝑎𝑟 𝑡𝑖𝑚𝑒.