Y7M3 P2A 練習-5

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年4.王者之路(zj:a821)  ================ 
// a821. 4.王者之路 -- 101學年度桃竹苗區資訊學科能力競賽
#include <iostream>
#include <cstring>
#include <map>
using namespace std;
const int MaxN = 20; //最多 20 個
map<string , int> mp;  //姓名，編號 ：編號為 1 ~ n
int mpcnt;   // 已出現的隊伍數
bool los[MaxN+1]; 
string nam[MaxN+1];
int main(void)
{
int  n , r , i;
string a,b;
while( cin >> n >> r )
{
mpcnt = 0;   mp.clear();

for(i=1; i<=n; ++i) los[i] = 0;
for(i=0; i<r; ++i)
{
cin >> a >> b;
if( mp.find(a) == mp.end() ) mp[a] = ++mpcnt; //  mp.size(); //
int ai = mp[a]; nam[ai] = a;
if( mp.find(b) == mp.end() ) mp[b] = ++mpcnt; // mp.size(); //
int bi = mp[b]; nam[bi] = b;
los[bi] = 1;  //輸過一場就是 1
}
// 因為 王者 會贏其他所有的人，不會輸
for(i=1; i<=n; ++i) 
     if( los[i] == 0 ){   // 沒輸過的就是王者
           cout << nam[i] << endl;
            break;
     }
}
return 0;
}

/*  ----範例輸入
3 3
tpa azf
tpa abc
azf abc
5 11
tpa azf
azf abc
tpa abc
abc xyz
tpa abcde
xyz abc
azf abcde
azf xyz
abc azf
tpa xyz
azf abcde
5 12
mmm bbb
bbb ccc
mmm ccc
ddd mmm
mmm eee
ddd ccc
ddd bbb
bbb mmm
ddd eee
bbb eee
mmm bbb
bbb ccc
-----------範例輸出
tpa
tpa
ddd
*/

101年5.滾球遊戲(zj:a822) 解１ ================ 
// zj: a822 滾球遊戲  -- 101學年度桃竹苗區資訊學科能力競賽
#include <iostream>
#include<cstring>
using namespace std;
int gb[500][500]; // 遊戲盤 game board 
int bn[500][500]; // 各格球數 ball numbers 
int n , n2;       // n2 = n*n;
void game(int r, int c)
{
   memset (gb,0,sizeof(gb));
   int i,j, t=0;
   while( t<n2 )
   {
      gb[r][c]= ++t;
      if(t==n2) break;
      i=(r*n+c+t)%n2;  //下一格的序號，所有格子換算成 0~n^2-1
      r=i/n  ; c=i%n;  // 序號轉回 列、行 (r,c)
      while(gb[r][c])  // 若該格已填入過， 往後找到可用的空格
      {
         c++;         // 往右找，一列找完往下一列
         if(c>=n)
         {
            ++r; c=0;
            if(r>=n) r=0;   // 最後一列回到第１列
         }
      }    
   }
}
int mr[]={-1,1,0,0};
int mc[]={0,0,-1,1};
void putball(int r, int c)
{
   int m=gb[r][c];
   int nr,nc, nd;
   while( 1 ) // 滾至最低格才停 
   {
      nd = -1;  // 是否為最小（最低格)
      for(int d=0; d<4; ++d) // 上下左右
      {
         nr = r+mr[d];  nc = c+mc[d];
         if(nr<0 || nr>=n || nc<0 || nc>=n) continue;
         if( gb[nr][nc] < m ) 
         {
            m=gb[nr][nc];  nd=d;  // m 四周 5格中 最小數字
         }     
      }
      if( nd == -1 )  break; //已是最低格了
      r = r+mr[nd];  c= c+mc[nd];  //移至四周較小的　格子
   }
   ++ bn[r][c];  //球停在此格
}

int main( )
{

   int  r,c;   // n , n2 公用變數 
   cin >> n >> r >> c;
   n2 = n*n;
   game(r,c);  // 產生遊戲盤
// 每1格放1球，滾至某格，將 bn[nr][nc] + 1;
   memset ( bn,0,sizeof(bn) ); 
   for(r=0;r<n;++r)
      for(c=0;c<n;++c)
         putball(r,c);
// 計算有哪幾格有球，最多球的球數？
   int gc=0 , bc=0;
   for(r=0;r<n;++r)
      for(c=0;c<n;++c)
      {
         if(bn[r][c])
         {
            ++gc;   // 格子數+1
            if(bn[r][c] > bc) bc=bn[r][c];
         }
      } 
   cout << gc <<" " << bc << endl;
   return 0 ;
}

101年5.滾球遊戲(zj:a822) 解２ ================ 
// zj: a822 滾球遊戲  -- 101學年度桃竹苗區資訊學科能力競賽
#include <iostream>
#include <cstring>
using namespace std;
const int MaxN = 500;
int gb[MaxN][MaxN];  // 遊戲盤數值
int bc[MaxN][MaxN];  // 各格球數
int n , n2 ;
void setgb(int r, int c)
{
int t=1 , p;
while( t< n2 )
{
gb[r][c] = t;
p = ( r*n + c + t++ ) % n2;
r = p/n;  c=p%n;
while( gb[r][c] !=0 )
{
p = (p+1)%n2; //找 下一 空格; 
r = p/n;  c=p%n;
}
}
gb[r][c] = t;
}
int dr[] = {-1, 1, 0, 0};
int dc[] = { 0, 0,-1, 1};
void putball(int r, int c)
{
int m=gb[r][c];
int ur =r , uc=c;
for(int d=0; d<4; ++d)
{
int nr=r+dr[d] , nc=c+dc[d];
if( nr<0 || nr>=n || nc<0 || nc>=n ) continue;
if( gb[nr][nc] < m ) 
{
ur=nr;  uc=nc;  m=gb[nr][nc];
}
}
if( ur==r && uc==c )  bc[r][c]++; 
else putball(ur,uc);  // 四周有更低格
}
void print(int x[][MaxN] )
{
  int i,j;
for(i=0; i<n; ++i)
{ 
  for(j=0; j<n; ++j)
    cout << x[i][j] <<' ';
  cout << endl;
}

}
int main(void)
{
int r,c,p;

while( cin >> n >> r >> c ) // 讀至檔尾
{
memset(gb,0,sizeof(gb));
memset(bc,0,sizeof(bc));
n2 = n*n;
setgb(r,c);  // 產生遊戲盤
// print(gb);   // 測試列印用 //
for(r=0; r<n; ++r)
 for(c=0; c<n; ++c)
   putball(r,c) ;  // 在(r,c)放1球
// print(bc);   // 測試列印用 //
// 找出共幾格有球ans1，球最多的格子有幾球ans2
  int ans1=0 , ans2=0;
for(r=0; r<n; ++r)
 for(c=0; c<n; ++c)
   if(bc[r][c])
   {
     ans1++;  // 多一格有球
     if(bc[r][c]>ans2) ans2=bc[r][c];
   }
   cout << ans1 << ' ' << ans2 << endl;
}
return 0;
}

/* ----範例輸入
3 1 1
4 0 0
-------範例輸出
1 9
5 5

*/