2017年6月15日 星期四
2017年5月29日 星期一
2017年5月22日 星期一
b547 巧克力口味
/*
b547-巧克力口味
*/
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
const int MaxR = 10;
set <string> rel[MaxR]; // 最多 10 種 關係
map <int , int> c2n;
string rs(8,'?');
string c6(6,' ');
int getn(int i)
{
int j=c2n[ c6[i] ];
j += c2n[ c6[i+1] ];
return j;
}
// 以遞迴 將某一關係的所有編號建立 存入 rel[si]中
string ss[]={"PBY","SCT"};
void setr(int si, int p, int q)
{
int i,j;
if(q==6) // 已 6個字元了
{
bool mk[10];
string one="";
memset(mk,0,sizeof(mk));
for(i=0; i<6; i+=2)
{
j= getn(i);
if( mk[j] ) return; // 出現過，不合
mk[j] = true;
one += char('0'+j);
}
rel[si].insert(one); // 可以的關係編號 加入 rel[si] 中
//// cout << si <<':' << one << endl; /////
}
else // 完成第 q 個字元，遞迴下一字元 q+1
{
if( rs[p+q]=='?' ) // 目前這個位置為 ? 偶則以 PBY各代1次、 奇則以 SCT各代1次
for(i=0; i<3; ++i)
{
c6[q] = ss[q%2][i]; setr(si, p, q+1);
}
else
{
c6[q] = rs[p+q]; setr(si, p, q+1);
}
}
}
string x,y,z; // 將nine切成3部份
int r; //共 r 個關係
bool ok() // 任一個關係 最少要有 某一列 3個巧克力 符合它
{
for(int si=0; si<r; ++si)
{
if( !( rel[si].find(x)!=rel[si].end() || rel[si].find(y)!=rel[si].end() || rel[si].find(z)!=rel[si].end() ) ) return false;
}
return true;
}
int main(void)
{
int i,j,k,t ,n;
char c;
c2n.clear();
c2n['P']=0; c2n['B']=3; c2n['Y']=6;
c2n['S']=1; c2n['C']=2; c2n['T']=3;
cin >> r;
for(i=0; i<r; ++i)
{
cin >> t;
for(j=0; j<t*2; ++j)
{
cin >> rs[j+2];/// >> rs[j+3];
}
/// cout << i <<':' << rs << endl; ////
if(t==3) setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
else // t=2 , 前?? 及後 ?? 各一次
{
setr(i,0,0); // 第i個關係，從第0字元、已轉了0個
rs[6] = rs[7] ='?';
setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
}
}
string nine="123456789";
// cout << nine << endl; 1~9 九位數，全排列 共 9! = 362880
int cnt=0;
do
{
x=nine.substr(0,3); y=nine.substr(3,3); z=nine.substr(6,3);
// cout << x <<',' << y <<',' << z <<'\n';
if( ok() ) ++cnt;
} while( next_permutation(nine.begin(),nine.end() ) );
cout << cnt << endl;
// system("pause");
return 0;
}
/*
3
3 B S Y S P C
3 P T B C Y T
3 P S B T Y C
3
3 B S Y ? ? C
2 B C Y T
3 P S ? ? Y C
==========
6
24
*/
b547-巧克力口味
*/
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstring>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
const int MaxR = 10;
set <string> rel[MaxR]; // 最多 10 種 關係
map <int , int> c2n;
string rs(8,'?');
string c6(6,' ');
int getn(int i)
{
int j=c2n[ c6[i] ];
j += c2n[ c6[i+1] ];
return j;
}
// 以遞迴 將某一關係的所有編號建立 存入 rel[si]中
string ss[]={"PBY","SCT"};
void setr(int si, int p, int q)
{
int i,j;
if(q==6) // 已 6個字元了
{
bool mk[10];
string one="";
memset(mk,0,sizeof(mk));
for(i=0; i<6; i+=2)
{
j= getn(i);
if( mk[j] ) return; // 出現過，不合
mk[j] = true;
one += char('0'+j);
}
rel[si].insert(one); // 可以的關係編號 加入 rel[si] 中
//// cout << si <<':' << one << endl; /////
}
else // 完成第 q 個字元，遞迴下一字元 q+1
{
if( rs[p+q]=='?' ) // 目前這個位置為 ? 偶則以 PBY各代1次、 奇則以 SCT各代1次
for(i=0; i<3; ++i)
{
c6[q] = ss[q%2][i]; setr(si, p, q+1);
}
else
{
c6[q] = rs[p+q]; setr(si, p, q+1);
}
}
}
string x,y,z; // 將nine切成3部份
int r; //共 r 個關係
bool ok() // 任一個關係 最少要有 某一列 3個巧克力 符合它
{
for(int si=0; si<r; ++si)
{
if( !( rel[si].find(x)!=rel[si].end() || rel[si].find(y)!=rel[si].end() || rel[si].find(z)!=rel[si].end() ) ) return false;
}
return true;
}
int main(void)
{
int i,j,k,t ,n;
char c;
c2n.clear();
c2n['P']=0; c2n['B']=3; c2n['Y']=6;
c2n['S']=1; c2n['C']=2; c2n['T']=3;
cin >> r;
for(i=0; i<r; ++i)
{
cin >> t;
for(j=0; j<t*2; ++j)
{
cin >> rs[j+2];/// >> rs[j+3];
}
/// cout << i <<':' << rs << endl; ////
if(t==3) setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
else // t=2 , 前?? 及後 ?? 各一次
{
setr(i,0,0); // 第i個關係，從第0字元、已轉了0個
rs[6] = rs[7] ='?';
setr(i,2,0); // 第i個關係，從第2字元、已轉了0個
}
}
string nine="123456789";
// cout << nine << endl; 1~9 九位數，全排列 共 9! = 362880
int cnt=0;
do
{
x=nine.substr(0,3); y=nine.substr(3,3); z=nine.substr(6,3);
// cout << x <<',' << y <<',' << z <<'\n';
if( ok() ) ++cnt;
} while( next_permutation(nine.begin(),nine.end() ) );
cout << cnt << endl;
// system("pause");
return 0;
}
/*
3
3 B S Y S P C
3 P T B C Y T
3 P S B T Y C
3
3 B S Y ? ? C
2 B C Y T
3 P S ? ? Y C
==========
6
24
*/
2017年5月20日 星期六
b549 數位相片檔名
/*
b549 nr102-5 北二區102年-5 數位相片檔名
*/
#include <iostream>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
map<int,int> used; // 已使用的 <時間 , 檔名>
map<int,int>::iterator mit;
map<int,int>::reverse_iterator rit;
bool can(int fn) // 傳入的檔名是否可用(符合雙遞增)
{
if(used.size()<2) return true; // 只有0或1個時，一定可以
int cnt=1; // 使用的 序列數，最多2個
mit=used.begin();
int fn1=mit->second, fn2=9999 ,fn3; //第1個使用 一個序列
// 若有兩個序列，維持 fn1<fn2
for(++mit; mit!=used.end() ; ++mit) // 從 第2個起與前一個比
{
fn3=mit->second; // 第2個起的檔案編號
if( fn3<fn1 )
{
if (cnt==2 ) return false; //已兩個再加1個 x
++cnt; fn2=fn1; fn1=fn3; //保持 fn1<fn2
}
else // fn3>fn1 可加入 fn1或fn2
{
if(fn3>fn2) fn2=fn3; //加至較大 的序列處，保留較小的序序編號
else fn1=fn3; // fn3<fn2無法加至 fn2，也保證 fn1=fn3<fn2
}
}
if( cnt==2 && fn<fn1 ) return false; //已兩個再加1個 x
else return true;
}
int main( )
{
int n , t ;
int fn[1000];
char c;
for( n=0; n<1000; ++n) fn[n] = n;
set <int>::iterator sit;
bool first=true;
while( cin >> n )
{
set <int> nuse(fn,fn+1000); //待用的檔號
used.clear();
while( n-- )
{
cin >> c >> t;
if( c == 'A' )
{
for( sit = nuse.begin(); sit != nuse.end(); ++sit )
{
int fn = *sit; //檢查檔名編號 fn 是否可用
if ( !can( fn ) ) continue; // 不能用，下一個
used[ t ] = fn; // t 時，加可用檔名 fn
nuse.erase( *sit );
break;
}
}
else
{
nuse.insert( used[t] ); // 未用的檔名，加一個
used.erase( t ); // 已用的 map <t,fn> 刪一個
}
}
// 印出，若不是第一組，則印出 --
if(first) first=false; else cout << "--\n";
rit = used.rbegin(); rit++; //先至倒數第2個
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
rit--;
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
}
return 0 ;
}
/* 輸入範例
10 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6 D 3 A 7 D 0 A 8
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 D 0 A 8 A 9
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9
15 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10
17 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11
19 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11 D 11 A 12
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 D 0 A 5
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 A 6
10 A 0 A 1 A 2 A 3 A 4 D 2 A 5 A 6 D 3 A 7
輸出範例-----------------
PIC004
PIC001
--
PIC002
PIC003
--
PIC006
PIC007
--
PIC006
PIC001
--
PIC001
PIC002
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC004
PIC005
--
PIC005
PIC003
*/
b549 nr102-5 北二區102年-5 數位相片檔名
*/
#include <iostream>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
map<int,int> used; // 已使用的 <時間 , 檔名>
map<int,int>::iterator mit;
map<int,int>::reverse_iterator rit;
bool can(int fn) // 傳入的檔名是否可用(符合雙遞增)
{
if(used.size()<2) return true; // 只有0或1個時，一定可以
int cnt=1; // 使用的 序列數，最多2個
mit=used.begin();
int fn1=mit->second, fn2=9999 ,fn3; //第1個使用 一個序列
// 若有兩個序列，維持 fn1<fn2
for(++mit; mit!=used.end() ; ++mit) // 從 第2個起與前一個比
{
fn3=mit->second; // 第2個起的檔案編號
if( fn3<fn1 )
{
if (cnt==2 ) return false; //已兩個再加1個 x
++cnt; fn2=fn1; fn1=fn3; //保持 fn1<fn2
}
else // fn3>fn1 可加入 fn1或fn2
{
if(fn3>fn2) fn2=fn3; //加至較大 的序列處，保留較小的序序編號
else fn1=fn3; // fn3<fn2無法加至 fn2，也保證 fn1=fn3<fn2
}
}
if( cnt==2 && fn<fn1 ) return false; //已兩個再加1個 x
else return true;
}
int main( )
{
int n , t ;
int fn[1000];
char c;
for( n=0; n<1000; ++n) fn[n] = n;
set <int>::iterator sit;
bool first=true;
while( cin >> n )
{
set <int> nuse(fn,fn+1000); //待用的檔號
used.clear();
while( n-- )
{
cin >> c >> t;
if( c == 'A' )
{
for( sit = nuse.begin(); sit != nuse.end(); ++sit )
{
int fn = *sit; //檢查檔名編號 fn 是否可用
if ( !can( fn ) ) continue; // 不能用，下一個
used[ t ] = fn; // t 時，加可用檔名 fn
nuse.erase( *sit );
break;
}
}
else
{
nuse.insert( used[t] ); // 未用的檔名，加一個
used.erase( t ); // 已用的 map <t,fn> 刪一個
}
}
// 印出，若不是第一組，則印出 --
if(first) first=false; else cout << "--\n";
rit = used.rbegin(); rit++; //先至倒數第2個
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
rit--;
cout << "PIC" << setfill ('0') << setw (3) << (rit->second) << endl;
}
return 0 ;
}
/* 輸入範例
10 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 4 A 6 D 3 A 7 D 0 A 8
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 D 0 A 8 A 9
14 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9
15 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10
17 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11
19 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 D 5 A 6 A 7 A 8 D 4 A 9 A 10 D 6 A 11 D 11 A 12
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 D 0 A 5
9 A 0 A 1 A 2 A 3 D 2 A 4 D 1 A 5 A 6
10 A 0 A 1 A 2 A 3 A 4 D 2 A 5 A 6 D 3 A 7
輸出範例-----------------
PIC004
PIC001
--
PIC002
PIC003
--
PIC006
PIC007
--
PIC006
PIC001
--
PIC001
PIC002
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC002
PIC004
--
PIC004
PIC005
--
PIC005
PIC003
*/
2017年3月23日 星期四
Y7M3 P2A 練習-7 俄羅斯方塊
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) ✔(上次已傳)
100年5.俄羅斯方塊問題(zj:a827) ================
// a827. 5.俄羅斯方塊問題 -- 100學年度桃竹苗區資訊學科能力競賽
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
const int BitN = 8; // 牆寬 8 格
const int BoxN = 11; // 11 種 (含旋轉)的方塊
int box[BoxN][2]={{3,3}, {0,15}, {1,1}, {3,1}, {3,6}, {3,2}, {6,3}, {2,7}, {7,2}, {3,2}, {3,1} }; // 每種2列
int bw[BoxN] = { 2, 4, 1, 2, 3, 2, 3, 3, 3, 2, 2}; // 11種 方塊的 寬度
int ty[BoxN] = {1, 2,2, 3,3, 4,4, 5,5,5,5 }; //屬於哪一種類型
int w[2]; // 牆 2列
set<int> out;
set<int>::iterator it;
int chk(int bi )
{
int i,b0,b1, sco, tot=0;
for(i=BitN-bw[bi]; i>=0; --i)
{
b1 = box[bi][1]<<i ; // 小方塊的下方列 由左至右的值
if( b1&w[0] ) continue; // bit and 值非 0 即無法放入第1層
// 進入第1層，接著檢查是否可進入第2層
b0 = box[bi][0]<<i ; // 小方塊的上方列 由左至右的值
if( (b0&w[0]) == 0 && (b1&w[1]) == 0 ) // 2層皆進入 , 因運算序(bit and)需括住
{
sco = ( ((b0|w[0])==255) + ((b1|w[1])==255) ) * 8; // 因運算序(bit or)需括住
} else { // 只能進一層，算第1層的分數
sco = ( (b1|w[0]) == 255 ) * 8;
}
if( sco>tot ) tot=sco;
}
return tot;
}
int main(void)
{
int i,j;
string s;
// 讀入兩列 牆
for(i=0; i<2; ++i) // 2列
{
cin >> s;
w[i] = 0;
for(j=0; j<BitN; ++j)
w[i] = w[i]*2 + (s[j]=='*');
}
int mx=0 , sco;
for( i=0; i<BoxN; ++i) // 以 11種 方塊各求 可得的分數，最高的 放入 out
{
sco = chk(i);
if( sco==0 || sco<mx ) continue;
if( sco>mx ) out.clear();
mx=sco;
out.insert( ty[i] ); // 若分數 >= mx 加入 out , 數字同 set只有1個
}
if( mx == 0 ) cout << "0\n0\n"; // 印2列 0
else { //最少一個
it = out.begin();
cout << (*it) ;
for(++it; it!=out.end(); ++it)
cout << ' ' << (*it) ;
cout << endl << mx << endl;
}
return 0;
}
/* ----範例輸入
例一 ：
000*0000
****0***
例二 ：
***0****
***0****
-----------範例輸出
例一 ：
2 4 5
8
例二 ：
2
16
*/
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) ✔(上次已傳)
100年5.俄羅斯方塊問題(zj:a827) ================
// a827. 5.俄羅斯方塊問題 -- 100學年度桃竹苗區資訊學科能力競賽
#include <iostream>
#include <cstring>
#include <set>
using namespace std;
const int BitN = 8; // 牆寬 8 格
const int BoxN = 11; // 11 種 (含旋轉)的方塊
int box[BoxN][2]={{3,3}, {0,15}, {1,1}, {3,1}, {3,6}, {3,2}, {6,3}, {2,7}, {7,2}, {3,2}, {3,1} }; // 每種2列
int bw[BoxN] = { 2, 4, 1, 2, 3, 2, 3, 3, 3, 2, 2}; // 11種 方塊的 寬度
int ty[BoxN] = {1, 2,2, 3,3, 4,4, 5,5,5,5 }; //屬於哪一種類型
int w[2]; // 牆 2列
set<int> out;
set<int>::iterator it;
int chk(int bi )
{
int i,b0,b1, sco, tot=0;
for(i=BitN-bw[bi]; i>=0; --i)
{
b1 = box[bi][1]<<i ; // 小方塊的下方列 由左至右的值
if( b1&w[0] ) continue; // bit and 值非 0 即無法放入第1層
// 進入第1層，接著檢查是否可進入第2層
b0 = box[bi][0]<<i ; // 小方塊的上方列 由左至右的值
if( (b0&w[0]) == 0 && (b1&w[1]) == 0 ) // 2層皆進入 , 因運算序(bit and)需括住
{
sco = ( ((b0|w[0])==255) + ((b1|w[1])==255) ) * 8; // 因運算序(bit or)需括住
} else { // 只能進一層，算第1層的分數
sco = ( (b1|w[0]) == 255 ) * 8;
}
if( sco>tot ) tot=sco;
}
return tot;
}
int main(void)
{
int i,j;
string s;
// 讀入兩列 牆
for(i=0; i<2; ++i) // 2列
{
cin >> s;
w[i] = 0;
for(j=0; j<BitN; ++j)
w[i] = w[i]*2 + (s[j]=='*');
}
int mx=0 , sco;
for( i=0; i<BoxN; ++i) // 以 11種 方塊各求 可得的分數，最高的 放入 out
{
sco = chk(i);
if( sco==0 || sco<mx ) continue;
if( sco>mx ) out.clear();
mx=sco;
out.insert( ty[i] ); // 若分數 >= mx 加入 out , 數字同 set只有1個
}
if( mx == 0 ) cout << "0\n0\n"; // 印2列 0
else { //最少一個
it = out.begin();
cout << (*it) ;
for(++it; it!=out.end(); ++it)
cout << ' ' << (*it) ;
cout << endl << mx << endl;
}
return 0;
}
/* ----範例輸入
例一 ：
000*0000
****0***
例二 ：
***0****
***0****
-----------範例輸出
例一 ：
2 4 5
8
例二 ：
2
16
*/
2017年3月20日 星期一
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
*/
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
*/
發表文章
