zj:97-北縣賽-D227, D231~D233

第1題d227. 97北縣賽-1-正弦三角函數

// 本題 ZJ上輸入的角度 -900 ~ 900 不需轉成較小的同界角，但可當練習

#include <iostream>

#include<iomanip>

#include<cmath>

using namespace std;

int main( )

{

   int a , s;

   double pi180 = 3.1415926 / 180;

   double f , p , x , pdf ;

   double limit = 0.01;

   while( cin >> a )

   {

//   a 縮約 ==> a=(a+1080) % 360 ; a>180=>sin為負 ,  sin(a) = sin(90-abs(a-90)%90)

//   a=(a+1080) % 360 ; 

//   bool sgn=(a>180);

//   a=90-abs(a-90)%90;     

//    本題 d227 不需縮約 a 值 

      x = a * pi180 ;

      f = 1.0;     // k!

      p = x;     // x^k;

      s = 1;     // * 1 或 * -1

      double sin = 0.0;

      int k;

      for(k = 1 ;  ; k += 2 )

      {

         pdf =  p / f;    // x^k / k!         

         sin += ( s * pdf );

 //  cout << k << ":" <<p <<"/" << f << "=" << pdf <<"sin="<<sin<<endl; 

         if ( abs(pdf) <= 0.01 ) break;

         p = p * x * x ;

         f = f * ( k+1) * (k+2) ;

         s = -s;

      }

      cout << "N = " << k << endl;

//      cout << (sgn?"-":"");   有縮約  a 值 才需 加印  負號 

      cout << fixed << setprecision(6) << sin << endl;

   }

    return 0 ; 

}

第2題d231. 97北縣賽-2-基因序列密碼問題

// 參考 gj d003 "99年台中區複賽第三題"    LCS  

#include <iostream>  

using namespace std;  

int main( )  

{  

   int i,j, m,n,t;  

   string x,y,z;  

   while ( cin >> x >> y )  

   {  

      m = x.size();  

      n = y.size();  

      int b[m+1][n+1] , c[m+1][n+1];  

      for(i=0; i<=m; ++i ) c[i][0]=0;  

      for(j=0; j<=n; ++j ) c[0][j]=0;  

   // 開始由 c[1][1]開始設定，至c[m][n]即為 LCS 長度  

   // 由b[m][n]往回找若 b[i][j]==0 印出 { 0左上、1上、2左 }   

      for(i=1; i<=m; ++i )  

      {   

         for(j=1; j<=n; ++j )  

         {  

            if(x[i-1]==y[j-1])   // 字串從 0 開始   

              { c[i][j]=c[i-1][j-1]+1 ;  b[i][j]=0; }   // 左上   

            else if(c[i-1][j]<c[i][j-1]) 

              { c[i][j]=c[i][j-1] ;  b[i][j]=2; }       // 左  

            else   { c[i][j]=c[i-1][j] ;  b[i][j]=1; }  // 上  

         }              

      }  

   // 印出 LCS  

    //  cout << x << " " << y << " = ";   

      if( c[m][n]==0 ) { cout << "E" << endl; continue; }  

      i=m; j=n;  z="";  

      while ( i && j )  

      {  

         if( b[i][j]==1) --i;  

         else if( b[i][j]==2) --j;  

         else if( b[i][j]==0 )  

         {  

            --i; --j;  

            z = x[i] + z;  

         }  

      }  

      cout << z <<endl;  

   }  

   return 0 ;   

}

第3題d232. 97北縣賽-3-資料統計問題

/*

d232  97-北縣賽-3-資料統計問題 

*/

#include <iostream>

#include <cstring>

#include <algorithm>

#include <map>

using namespace std;

struct ntyp

{

   string nam;   // 姓名

   int psum;         // 購書總額

   int age;          // 年齡 

}  cus[101];

bool cmp(ntyp a, ntyp b)

{

   if( a.psum == b.psum )

      return (a.nam<b.nam);

   else return (a.psum>b.psum);

}

int main( )

{

   int t , i , j , cnt , ci ;

   string nam;

   char sex , typ;

   int age, pay;

   int tsum[5];  // A~E 五類的 總銷售金額

   int sta[10][10];  // 金額10級、年齡10級

   map <string , int> mp;

   while( cin >>t )   // 筆數 t 

   {

      memset ( tsum , 0 , sizeof(tsum) );

      memset ( sta , 0 , sizeof(sta) );

      mp.clear();

      for(cnt=0 , i=0 ; i<t ; ++i)

      {

         cin >> nam >> sex >> typ >> age >> pay;

         tsum[typ-65] += pay;    // 某類書 + 購買金額 

         if( mp.count(nam) ) // 已出現過，取 ci

         { 

            ci = mp[nam];

            cus[ci].psum += pay;

         }

         else  // mp 內沒有，新 ci=c++; 

         {

            mp[nam] = cnt;  ci = cnt++ ;

            cus[ci].nam = nam;

            cus[ci].age = age;

            cus[ci].psum = pay;

         }

      }

      sort(cus, cus+cnt , cmp);   // 自訂比較函式 cmp

// 依金額、年齡 分類統計

      for( i=0; i<cnt ; ++i )

      {

         sta[ (cus[i].psum-1)/1000 ][ (cus[i].age-1)/10 ] += 1;         

      } 

      int mx=tsum[0] , mi=0;

      for(i=1; i<5; ++i)

         if(tsum[i]>mx) { mx=tsum[i] ; mi=i ; } 

      cout << char( mi+65 ) << endl;

      for( i=0; i<10; ++i )

      {

         cout << sta[i][0] ;

         for( j=1; j<10; ++j)

            cout <<" "<< sta[i][j];

         cout << endl;

      }

      for ( i=0 ; i<cnt && i<5 ; ++i )

         cout << cus[i].nam << " " << cus[i].psum <<endl;

      // 與第5名 金額同的都要印

      for (  ; i<cnt && cus[i].psum==cus[i-1].psum ; ++i )

         cout << cus[i].nam << " " << cus[i].psum <<endl;

   }

   return 0 ; 

}

第4題d233. 97北縣賽-4-金幣問題

// 作法:DFS  搜尋的終止條件很重要

#include <iostream>

#include <cstring>

using namespace std;

int mp[256][256];

int mt [256];

int fg [256];

int mx = 0 , n ;

void DFS(int now,int time)

{  

   int i,find=0;

   if( time > mx )  mx = time;

     if( now > n || ( (n-now+1)/2 + time + 2 ) <= mx ) return;

   for(i=0 ; i < mt[now] ; ++i)

      if( fg[ mp[now][i] ] == 1 )

         {find=1;break;}

   if(find==0)

   {

      fg[now]=1;

      DFS(now+1,time+1);

      fg[now]=0;

   } 

   DFS(now+1,time);

}

main()

{

   int  x , y;

   cin >> n;

   int  wy[n];

   memset ( mp , 0 , sizeof(mp) );

   memset ( mt , 0 , sizeof(mt) );

   memset ( fg , 0 , sizeof(fg) );

   while( cin >> x , x)  // x==0 結束 

   {

       cin >> y;

       mp[x][ mt[x] ]=y;

       ++ mt[x] ;

       mp[y][ mt[y] ] = x;

       ++ mt[y] ;

   } 

   mx=0;

   DFS(1,0);    

   cout << mx << endl;

   return 0;

}

zj:94-北縣賽-D249~D252

第1題d249: 94北縣賽-1-心意相通的指數(Match)

以下程式碼在 ZJ 沒有 AC ，只有60分

討論區有人說測資與題意不符

http://zerojudge.tw/ShowThread?postid=2568&reply=2567#2568

測資解的順序不是像題目所說的任意解皆可。

當LCS的dp[a-1][b] == dp[a][b-1]時要取dp[a][b-1]，

這樣解的順序才會跟測資一樣，

另有morris的 AC 請查 下列網址

http://mypaper.pchome.com.tw/zerojudge/post/1322395974

我覺得我以下的小珠部份旋轉方向改一下、取dp[a][b-1]部份改一下應可以過，但還沒仔細試

下週再補

#include <iostream>

#include <sstream>

#include <iomanip>

#include<cstring>

using namespace std;

string LCS( string x , string y )

{

   string z;

    int i,j, m,n,t;  

      m = x.size();  

      n = y.size();  

      int b[m+1][n+1] , c[m+1][n+1];  

      for(i=0; i<=m; ++i ) c[i][0]=0;  

      for(j=0; j<=n; ++j ) c[0][j]=0;  

   // 開始由 c[1][1]開始設定，至c[m][n]即為 LCS 長度  

   // 由b[m][n]往回找若 b[i][j]==0 印出 { 0左上、1上、2左 }   

      for(i=1; i<=m; ++i )  

      {   

         for(j=1; j<=n; ++j )  

         {  

            if(x[i-1]==y[j-1])   // 字串從 0 開始   

              { c[i][j]=c[i-1][j-1]+1 ;  b[i][j]=0; }   // 左上   

            else if(c[i-1][j]<c[i][j-1]) 

              { c[i][j]=c[i][j-1] ;  b[i][j]=2; }       // 左  

            else   { c[i][j]=c[i-1][j] ;  b[i][j]=1; }  // 上  

         }              

      }  

   // 產生 LCS 字串 z  

 //     cout << x << " " << y << " = ";

      i=m; j=n;  z="";  

      if( c[m][n]==0 )  return z; //{ cout << 0 << endl; continue; }  

      while ( i && j )  

      {  

         if( b[i][j]==1) --i;  

         else if( b[i][j]==2) --j;  

         else if( b[i][j]==0 )  

         {  

            --i; --j;  

            z = x[i] + z;  

         }  

      }  

      return z;

}

int main( )

{

   string a , a2 , b , c , d , e;

   int an ,  abn , m , i;

   cin >> a >> b;   // 讀兩字串 ，求 LCS

   an = a.size();   // 串成環的長度 

   a2 = a + a.substr(0,an-1); 

   abn = an + b.size();

   for ( m=0 , i=0; i<an; ++i)

   {

      c = a2.substr( i , an ); // a2 循環 取 a 長度  

      d = LCS( c , b );   // 找出 c , b 的 lcs 字串傳回 d;

      if( d.size() > m )  

      {

         m = d.size();

         e = d;

      }

   }

   if ( m==0 ) cout << "no" << endl;

   else

   {   cout << e << endl;

       cout << fixed << setprecision(2) <<  2.0*m / abn << endl;

   }

   return 0 ; 

}

第2題d250: 94北縣賽-2-數獨問題 (Sudoku)

#include <iostream>

using namespace std;

int main( )

{

    string s;

    bool m[10];

    int i;    

   while(cin>>s) {

      bool m[10]={false};

      for(i=0;i<9;i++)  if(s[i]) m[s[i]-'0']=true; 

      for(i=1;i<=9;i++)  if( !m[i] ) cout<<i<<endl; 

   }

    return 0 ; 

}

第3題d251: 94北縣賽-3-羅馬數字 (Roman)

#include <iostream>

using namespace std;

// ----------------------------------------

string rtb="IVXLCDM";

int  ntb[]={1,5,10,50,100,500,1000};

int rton(string s)  // 羅馬字串轉數字 

{

 int i,j,n=s.size();

  int v1,v2,sum=0;

  for (i=0;i<n;i++) {

     j=i+1;

     v1= ntb[rtb.find(s[i])];

     sum+=v1;

     if(j>=n) return sum;

     else {

        v2= ntb[rtb.find(s[j])];

        if(v1<v2) { sum+=(v2-v1-v1); i++; }

     }

   }

   return sum;

}

// -------------------------------------------

string r,ms[]={"IV","IX","XL","XC","CD","CM"};

int    m[]={4,9,40,90,400,900};

string ntor(int n)  // 數字轉羅馬字串 

{

int ti;

  //千

  r="";

  while(n>=1000) {r+='M'; n-=1000; }

  for(ti=5;ti>=0;ti--) {

     if(n>=m[ti]) { r+=ms[ti]; n-=m[ti]; }

     while(n>=ntb[ti]) { r+=rtb[ti]; n-=ntb[ti]; }

  }

  return r;

}

// -------------------------------------------

int b2t(int m)

{

   return (m+450)%1440;  //部落總分鐘數+7小時30分的總分鐘數 

}

// ----------------------------------------------------

int main( )

{

   

   string rh , rm ;  //羅馬數字 時rh 、 分rm

   int bhm , thm ;  // 轉成數字的部落總分鐘bhm , 台灣的總分鐘 thm

   cin >> rh >> rm ;

   thm = b2t( rton( rh ) * 60 + rton( rm ) );

   cout << ntor( thm/60 ) << endl;

   cout << ntor( thm%60 ) << endl;

   return 0 ;

}

第4題d252: 94北縣賽-4-字串處理問題 (String)

/*

輸入： 

hellol, I am a frog.

$-----xxxxipieirisioin0u++xs

hellol, I am a frog.

0uuuxxxxssss----++++uuuussssxxxxuuuuipipipipipipip

範例輸出 ：

Hello, I am a person.

HEL I AFROGppppppp.

*/

#include <iostream>

#include <cctype>

using namespace std;

int main( )

{

   string data , cmd ; //資料、指令

   getline( cin , data );

   getline( cin ,cmd );

   int dn = data.size();

   int cn = cmd.size();

   if( data[dn-1] == 13 ) { --dn; data.erase(dn); }  //若最後1字為換行，刪

   string dd=data;

   if( cmd[cn-1] == 13 ) { --cn; cmd.erase(cn); }  //若最後1字為換行，刪

   int p=0;  // 游標在第1個字{索引值0}

   char c , t;

   for(int i=0; i<cn; ++i)

   {

      c=cmd[i];

      switch( c )

      {

         case '0' : p=0; break;  // 行首 

         case '$' : p=data.size(); break;  // 行尾 

         case 'x' : if( (p < data.size()) && (data.size()>0) ) data.erase(p,1) ; break;  // 刪1字元 

         case 's' : if( p < data.size()-1 )          // p , p+1 兩字元交換

                  { t=data[p];  data[p]=data[p+1] ; data[p+1]=t; }  break; 

         case 'i' : if(i+1<cn)                  // 游標前插入1字元 

                  { ++i ; data.insert(p,1,cmd[i]); ++p; }  break; 

         case 'u' : if( (p < data.size()) ){ data[p]=toupper(data[p]); ++p; } break; // 轉大寫

         case '+' :  ++p; break; // 右移if( p < data.size() )

         case '-' :  --p; break; // 左移if( p > 0 )

       }

   }

   cout << data << endl;

   return 0 ;

}