1200: A DP problem ★★☆☆☆ 題組：Problem Set Archive with Online Judge 解題者：李協彥 解題日期：2017年5月23日 題意：測資為 𝑡 個一元一次方程式，運算符號只有+或−，𝑥的係數與常數項皆為整數[0~1000]，這題要求出每個方程式的解，以整數下界的形式印出，若方程式無解印出”IMPOSSIBLE，若無限多解需印出”IDENTITY”。
透過字串處理之後，整理出等號兩邊的方程式， 即可算出𝑥。 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
38+5x-20-3x+x+0x+9=20x Positive + Value length ax + b = cx + d a b c d
38+5x-20-3x+x+0x+9=20x Positive + Value 3 length 1 ax + b = cx + d a b
38+5x-20-3x+x+0x+9=20x Positive + Value 38 length 2 ax + b = cx + d a
38+5x-20-3x+x+0x+9=20x Positive + Value 38 length 2 ax + b = cx + d a
38+5x-20-3x+x+0x+9=20x Positive + Value 38 length 2 ax + b = cx + d a 38
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
38+5x-20-3x+x+0x+9=20x Positive + Value 5 length 1 ax + b = cx + d a b 38
38+5x-20-3x+x+0x+9=20x Positive + Value 5 length 1 ax + b = cx + d a b 38
38+5x-20-3x+x+0x+9=20x Positive + Value 5 length 1 ax + b = cx + d a b
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
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
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
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
38+5x-20-3x+x+0x+9=20x Positive + Value 9 length 1 ax + b = cx + d a b 18
38+5x-20-3x+x+0x+9=20x Positive + Value 9 length 1 ax + b = cx + d a b 27
ax + b = cx + d a b c d 3 27 20 𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 =1.58823529 𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 =1.58823529 1.58823529 =1
ax + b = cx + d a b c d 3 27 20 𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 =1.58823529 𝑥= 𝑑−𝑏 𝑎−𝑐 = 0−27 3−20 =1.58823529 1.58823529 =1 a == c and b == d IDENTITY a == c and b != d IMPOSSIBLE
討論： 要印出數值的整數下界，可直接呼叫函式。 #include <math.h> // double floor(double x); double x = 1.234; cout << floor(x) << endl; printf(“%d\n”,floor(x)); 此解法的時間複雜度為 𝑂 𝑛 =𝑙𝑖𝑛𝑒𝑎𝑟 𝑡𝑖𝑚𝑒.