Y7M2 P2A 練習-3

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)

1.圈叉連線數問題(zj:a817)  ================ 
// zj: a817 O X 連線問題 a817. 1.圈叉連線數問題 -- 100學年度桃竹苗區資訊
// 寬高 最多 10x10
#include <iostream>
#include <sstream>
#include <cstring>
#include <set>
using namespace std;

int a[20][20];
//    E  S  NE NW SE SW  六種不同方向的位移量
int dx[]={ 1, 0, 1,-1, 1,-1};  // x軸(左右)
int dy[]={ 0, 1,-1,-1, 1, 1};  // y軸(上下)

set<int> out;
set<int>::iterator it;

void putout(int x1,int y1, int x2, int y2)
{
int t;
if(x1!=x2)
{
if(x1>x2)
{
t=x1; x1=x2; x2=t;
t=y1; y1=y2; y2=t;
}
}
else if(y1>y2)
{
t=y1; y1=y2; y2=t;
}
out.insert(x1*1000+y1*100+x2*10+y2);
}

int match(int x, int y, int d, int len)
{
if(len<3) return 0;   // 最少需3格
int r=y , c=x; 
int k=a[r][c];
r+=dy[d]; c+=dx[d];
for(int i=1; i<len; ++i)
{
if(a[r][c]!=k) return 0;  // OX不同
r+=dy[d]; c+=dx[d];
}
putout(x, y, c-dx[d] , r-dy[d]);
return 1;
}

int main( )
{
   int t , n , i , j , k;
   string line;
   while(cin >> n)
{
getline(cin,line);
  memset(a,0,sizeof(a));
for(i=0; i<n; ++i)
{
getline(cin,line);
istringstream ss(line);
while( ss>>j ) 
{
if(j==0) break;
a[i][j-1]=1;
}
}
int ans=0;
out.clear();
// 以下  ( 0 橫:由上至下)、( 1直:由左至右) 、( 2 北東:由左下往右上)
//     ( 3 北西:由右下往左上)、( 4 南東:由左上往右下) 、( 5 南西:由右上往左下)
//   共六種方向各判別 一次， 呼叫 match，若符合的傳回 1 , 就是增加一條線
//  zerojudge 不需印出，但原題應印出(不過沒規定順序，我的解有順序:以set存，最後再一起輸出
for(i=0;i<n;++i)
{
ans += match(0,  i, 0,n);  // 橫 E
ans += match(i,  0, 1,n);  // 直 S
}
for(i=2;i<n;++i)
{
ans += match(0,  i, 2,i+1);  // 北東 NE
ans += match(n-1,i, 3,i+1);  // 北西 NW
}
for(i=1;i<n-2;++i)
{
ans += match(0,  i, 4,n-i);  // 南東 SE
ans += match(n-1,i, 5,n-i);  // 南西 SW
}
cout << ans << endl;

// 應再輸出哪幾條線 set<int> out
/* (x1,y1)(x2,y2) ： x1從小至大 列出
 for( it=out.begin(); it!=out.end(); ++it )
 {
k=(*it);
cout <<"("<<k/1000+1<<","<<k%1000/100+1<<")("<<k%100/10+1<<","<<k%10+1<<")\n";
 }
*/
}
   return 0;
}
/*  ----範例輸入
4
1 4
3 4
4
1 2 3 4
5
1 2 3 4 5
3 4
4 5
1 2 5
0
6
3 5
4 5
5 6
5 6
4 5
3 4 5
-----------範例輸出
3
(1,3)(3,1)
(1,4)(4,4)
(4,1)(4,4)
5
(1,1)(5,1)
(1,2)(4,5)
(1,5)(5,5)
(2,1)(5,4)
(3,1)(5,3)
7
(1,1)(1,6)
(1,4)(4,1)
(2,1)(2,6)
(3,1)(6,4)
(3,6)(6,3)
(4,6)(6,4)
(5,1)(5,6)
*/

3.小四數學(zj:a825) ================ 
// zj: a825. 3.小四數學 -- 100學年度桃竹苗區資訊學科能力競賽
#include <iostream>
#include<algorithm>  // sort 需用
using namespace std;
int main( )
{
   int i,m ,num[10];
   while(cin>>m)
   {
     int n[2]={0};
     for(i=0; i<m; i++)
           cin >> num[i];
     sort(num, num+m);
     // 各位數num[...]排序，由大至小分給兩個數 n[0]、n[1]，
     // 第1個分給 n[0]，然後num[1...]分給 n[0],n[1]較小的
     int j, s=0;     
     for( j=m-1; j>=0; j--)
      {
        n[s]=n[s]*10 + num[j];
        s=(n[0]>n[1])?1:0;      //如果 n[0]>n[1]則下次分別 n[1]
      }
//     cout <<n[0] <<"*" <<n[1] <<"=";
     cout <<n[0]*n[1] <<endl;
   }
    return 0 ;
}
/* ----範例輸入
3
2 2 5
5
5 4 3 8 9
-------範例輸出
110      {註 5*22}
80182    {註 94*853}

*/