NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC高中組 » NPSC2001高中組初賽
 NPSC 2001 高初 B.錢幣王國

作者 主題: NPSC 2001 高初 B.錢幣王國  (閱讀 978 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC 2001 高初 B.錢幣王國
« 於: 五月 31, 2015, 06:05:01 pm »

因錢幣種類最多2000,即費氏數f(2000)很大,若以大數法好像不大好哦,我的想法如下:

某人的錢幣總價值可轉換為費氏表示式,各個位置的權值如下,每一位只能0或1,且不可能連續1
位置: 1  2  3  4  5  6  7 ...
權值: 1  1  2  3  5  8  13 ...
   若有連續{...,X,1,1,Y,...}可轉成{...,X,0,0,Y+1,...}
   若有>1且第3種錢幣之後{...,X,Y,2,Z,...}可轉成{...,X+1,Y,1,Z+1,...}
   但若是第1或第2種 {X,2,Y,...}=>{X,0,Y+1,...} 或 {2,X,Y,...}=>{0,X,Y+1,...}
假設讀入如下:
(1)讀入 2 1 3 1 5 1 0即 {0,1,1,0,1}但2、3連續所以→{0,0,0,1,1}又4、5連續→最後{0,0,0,0,0,1}
(2)讀入 3 5 0 即{0,0,5}→{2,0,1,2}→{2,1,1,0,1}→{2,0,0,1,1}→{2,0,0,0,0,1}→{0,0,1,0,0,1}
(3)讀1 145 0 即{145}→{1,0,72}→{37,0,0,36}→{37,18,0,0,18}→…{1,0,0,0,0,0,0,0,0,0,0,1}
每組兩個錢幣值轉為費氏表示法後,再由最高位往低位比,即可判斷大小。

我的程式如下
代碼: [選擇]
// npsc01-s1b.cpp  npsc 2001 高初 B 錢幣王國
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
using namespace std;
const int maxn = 2100; //錢幣種類 最多 2000,但數量最多 10000,若進位 應不會超過 20位
int  a[2][maxn] , mm[2];
void t2f(int i)
{
int j , p=mm[i] , d;
int mp = p;
while( p )
{
if(p>mp) mp=p;
if(p>2)
{
if(a[i][p]>=2)
{
d = a[i][p]/2;
a[i][p] %= 2;
a[i][p+1] += d;
a[i][p-2] += d;
p+=1;
}
else if( a[i][p]==1 && (a[i][p+1]==1 || a[i][p-1]==1)  ) // 有可能[p+1]=1 或 [p-1]=1;
{
if(a[i][p+1]==1) ++p;
a[i][p+1] += 1;
--a[i][p];
--a[i][p-1];
p+=1;
}
else --p;
}
else  // p=1,2

d = (a[i][1]<a[i][2] ? a[i][1] : a[i][2]);
if(d)
{  p=3;
a[i][p] += d; a[i][1] -= d; a[i][2] -= d;
} else if(a[i][p]>=2)
{
   d = a[i][p]/2;
   a[i][3] += d;
a[i][p]%=2;
p=3;  
}
else --p;
}
}
mm[i]=mp;   //傳回最高位

// 以下是測試用 多印出的
cout <<"第" << i+1 << "人 ";
for(j=mp; j>0; --j)
  if(a[i][j]) cout << j <<":" <<a[i][j] <<" ";
cout << endl;

}
int cmp()
{
if(mm[0]>mm[1]) return 1;
else if(mm[0]<mm[1]) return -1;
for(int i=mm[0]; i>0; --i)
{
if(a[0][i]>a[1][i]) return 1;
   else if(a[0][i]>a[1][i]) return -1;
}
return 0;
}
int main()
{
  int m;
while( cin >> m )
{
if( m == -1 ) break;
memset(a,0,sizeof(a));
  mm[0] = mm[1] = 0;
   while( cin >> a[0][m]  )
   {
if( m > mm[0] ) mm[0] = m;    
cin >> m;
    if(m==0) break;
}
   t2f(0 );  //將 讀入資料轉成 費氏表示式

   while( cin >> m )
{
if(m==0) break;
cin >> a[1][m];
if( m > mm[1] ) mm[1] = m;    
   }
   t2f(1);
   int r = cmp();
if ( r == 1 ) cout << "MORE" << endl;
else if ( r == -1 ) cout << "LESS" << endl;
else cout << "EVEN" << endl;
}

  return 0;
}
/*
2 1 3 1 5 1 0   
7 1 0
3 5 0   
3 1 6 1 0
1 145 0
12 1 0
10 8 7 6 5 3 9 1 0
9 1 7 6 5 2 3 1 6 2 8 2 10 7 0
-1
--------
第1人 6:1
第2人 7:1
LESS
第1人 6:1 3:1
第2人 6:1 3:1
EVEN
第1人 12:1 1:1
第2人 12:1
MORE
第1人 14:1 12:1 9:1 6:1 4:1 1:1
第2人 14:1 12:1 9:1 6:1 4:1 1:1
EVEN

*/
« 上次編輯: 五月 31, 2015, 07:02:34 pm 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC高中組 » NPSC2001高中組初賽
 NPSC 2001 高初 B.錢幣王國