Y7M3 P2A 練習-6 小三資優數學

100北二區資訊複賽

1.圈叉連線數問題(zj:a817)      ✔(上次已傳)

2.藏寶問題(zj:a824)                ✔(上次已傳)

3.小四數學(zj:a825)                ✔(上次已傳)

4.天氣預測問題(zj:a826)          ✔(上次已傳)

5.俄羅斯方塊問題(zj:a827)

101北二區資訊複賽

1.解碼問題(zj:a818)                  ✔(上次已傳)

2.小三資優數學(zj:a819)            ✔

3.小精靈吃數字(zj:a820)            ✔(上次已傳)

4.王者之路(zj:a821)                   ✔(上次已傳)

5.滾球遊戲(zj:a822)                   ✔(上次已傳)

101年2.小三資優數學(zj:a819)  ================ 
// a819. 2.小三資優數學 -- 101學年度桃竹苗區資訊學科能力競賽
/*
a819 小三數學，三個數字三列，第1列：n{2~10}代表位數，第2列：k{n位的數字}，第3列：可算出的結果 m
     n位數k的每位數之間可加運算符號使結果等於 m ，最多可加兩個符號{符號為 + , - , * , / 四種}兩個符號可相同 
     ===*** 題目中未說明，但若 先÷再*，暫時規定需能整除才加除號；例如  12/8*6不可以，不接受右列結果 {1.5*6=9、1*6=6}
*/

#include <iostream>
using namespace std;
typedef long long LL;
const LL INF = 1e18;
int n,m ; //, cnt;
string s;
LL a,b,c;

LL cal(LL x, LL y , char op)  // 算出 x (op) y ： op是+-*/
{
switch(op)
{
case '+': //+
 return x+y; break;
case '-': //-
 return x-y; break;
case '*': //*
 return x*y; break;
case '/': // ÷  y<>0且x÷y需整除，否則傳回 INF(不成立)
 if(y && x%y==0) return x/y; else return INF;
 break;
}
}
char ops[]={'-','+','*','/'};
void cut2(int p) // 將讀入的 數字串 s，切成左右兩部份:加1個符號在 索引 p之前
{                // 即 s[0~p-1] 一段轉成數值 a、 s[p~n-1] 一段 轉成數值 b
int i;
for(a=0, i=0; i<p; ++i) a=a*10+s[i]-'0';
for(b=0, i=p; i<n; ++i) b=b*10+s[i]-'0';
for(int op=0; op<4; ++op)
{
LL r = cal(a,b,ops[op]);
// cout << a <<ops[op] <<b <<'=' << r << endl;  //
if(r!=m) continue;
cout << a << ops[op] <<b << endl;
// ++cnt;
}
}

void cut3(int p, int q) // 將讀入的 數字串 s，切成三部份:加2個符號 {索引 p之前,索引 q之前}
{            // 即 s[0~p-1] 一段轉成數值 a、 s[p~q-1] 一段 轉成數值 b  s[q~n-1] 一段 轉成數值 c
int i,op1,op2;
for(a=0, i=0; i<p; ++i) a=a*10+s[i]-'0';
for(b=0, i=p; i<q; ++i) b=b*10+s[i]-'0';
for(c=0, i=q; i<n; ++i) c=c*10+s[i]-'0';
// cout << a <<','<<b<<','<<c<<endl;    //
//// === *** 運算式的優先序，先乘除後加減，應可建一個表以簡化程式碼，但我懶得再改了
for( op2=0; op2<4; ++op2)  // r2 = b { + -  * / } c 先 ， 再 a{+-}r2 除了  - + 或 - -
{
LL r2 = cal(b,c,ops[op2]);
// cout << a <<ops[op] <<b <<'=' << r << endl;  //
if(r2 == INF) continue;
for( op1=0;op1<2; ++op1)
{
if(op1==0 && op2<2) continue;
LL r1 = cal(a,r2,ops[op1]);
//   cout << a << ops[op1] <<b << ops[op2] <<c <<'=' << r1 << endl;  //
if(r1 !=m ) continue;
  cout << a << ops[op1] <<b << ops[op2] <<c << endl;
//   ++cnt;
}
}
LL r = cal( cal(a,b,'-') , c , '+' );  // a-b+c
// cout << a << '-' <<b << '+' <<c  <<'=' << r << endl;  //
if (r==m) {  cout << a << '-' <<b << '+' <<c << endl;  } //  ++cnt; } 
r = cal( cal(a,b,'-') , c , '-' );  // a-b-c
// cout << a << '-' <<b << '-' <<c  <<'=' << r << endl;  //
if (r==m) { cout << a << '-' <<b << '-' <<c << endl;  } //  ++cnt; } 

for( op1=2; op1<4; ++op1)  // r1 = a{ * / } b 先 , 再 r1{+-*/} c ，除了 a/b*c
{
LL r1 = cal(a,b,ops[op1]);
// cout << a <<ops[op] <<b <<'=' << r << endl;  //
if(r1 == INF) continue;
for( op2=0;op2<4; ++op2) // 除了 a/b*c 先算 a*c/b
{
if(op1==3 && op2==2) continue;
LL r2 = cal(r1,c,ops[op2]);
//   cout << a << ops[op1] <<b << ops[op2] <<c <<'=' << r2 << endl;  //
if(r2 !=m ) continue;
cout << a << ops[op1] <<b << ops[op2] <<c << endl;
// ++cnt;
}
}
r = cal( cal(a,c,'*') , b , '/' );  // a/b*c => a*c/b ，例 9/6*4 = 6
// cout << a << '/' <<b << '*' <<c <<'=' << r<< endl;     //
if (r!=m) return;
cout << a << '/' <<b << '*' <<c << endl;
// ++cnt;
}

int main(void)
{
int i,j;
cin >> n >> s >> m;
// {
LL k=0;
for(i=0; i<n; ++i) k=k*10+s[i]-'0';
if(k==m) { 
 cout << s << endl;
 return 0;
}
  // cnt =0;
for(i=1; i<n; ++i)  //切成 2 部份，切點位置 p:1~n-1
cut2(i);
for(i=1;i<n-1;++i)
 for(j=i+1; j<n; ++j)  //切成 3 部份，切點位置 p:1~n-2 , q:p+1~n-1
   cut3(i,j);
// if(cnt==0) cout << s<<','<<m<<endl;
// }

return 0;
}
/*

*/

/*  ----範例輸入
例一 ： 12/3 = 4
3
123
4
例二 ： 2+3*4 = 14
3
234
14
例三 ： 240/15 = 16
5
24015
16
例四 : 8-6+2
3
862
4
例五 9/6*4 <<此例應不成立
3
964
6
例六  1357-924*680
10 
1357924680 
-626963
-----------範例輸出
12/3
2+3*4
240/15
8-6+2
9/6*4
1357-924*680

*/