NPSC補完計劃

登入註冊帳號.

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

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2001國中組決賽
 題目A 33倍數+1 (C++)

作者 主題: 題目A 33倍數+1 (C++)  (閱讀 793 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
題目A 33倍數+1 (C++)
« 於: 四月 14, 2015, 01:54:53 pm »

代碼: [選擇]
// npsc01-j2a (2001 國決 題目 A  33N+1)
// 每列一串數字,最長 250 位數, 0 結束 ,若33的倍數+1 則印  T 否則印 F
//  33的倍為為 3的倍數且11的倍數, 3:所有位數被3整除、 11:奇偶位數和的差被11整除
//  大數 -1 也是可以算出奇、偶位的數字和
#include <iostream>
using namespace std;
int main()
{
  string s;
  while( cin >> s)  // 假設測資中 s 無前導0及前後空白,否則應另處理
  {
    if(s[0]=='0') break;
    int sum[2]={0,0};  // 奇位及偶位的和
    int sw=0;  // 0奇、1偶
    int sn = s.size();
    int i,z;
    for(i=sn-1; i>=0; --i, sw=1-sw)  sum[sw] += ( s[i]-'0' );  // 算奇偶位的和
  //  cout << sum[0] <<"," << sum[1] << " || ";
    // 大數減法 -1 ,除非末端為 0 否則直接-1(奇位-1)
    // 末端(1個0:奇位+9偶位-1)、(2個0:奇位+9-1偶位+9)、(3個0:奇位+9*2偶位+9-1)、(4個0:奇位+9*2-1偶位+9*2)…
    for(z=0, i=sn-1; i>=0; --i)
       if(s[i]!='0') break; else ++z;
    if(z>0) {  // 末端有0時
      sum[0] += ( (z+1)/2*9 );  sum[1] += ( z/2*9 ); //z個0: (奇位+(z+1)/2個9、偶位+z/2個9)再扣掉借位的
      sum[ z%2 ] -= 1;  // 末端0的個數: 奇個0偶位-1、偶個0奇位-1
    } else sum[0]--;  // 未端非0 直接奇位 -1 
    // 奇數位的和 sum[0] , 位數的和 sum[1]
//       cout << sum[0] <<"," << sum[1] << endl;
    // 若(odd+even)%3 ==0 且 abs(odd-even)%11==0) 且被33整除
    if( (sum[0]+sum[1])%3==0 && abs(sum[0]-sum[1])%11==0 )
       cout << "T" << endl;
   else cout << "F" << endl;
  }
  return 0;
}
/*
{12345678987654321*33 = 407407406592592593   ,
18446744073709551616*33 = 608742554432415203328 }
  範例輸入
33
34
3433
34343430
34343431
407407406592592592
407407406592592593
407407406592592594
608742554432415203328
608742554432415203327
608742554432415203329
132000
45600
0
  範例輸出
F
T
T
F
T
F
F
T
F
F
T
F
F
*/
« 上次編輯: 四月 14, 2015, 09:32:05 pm 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2001國中組決賽
 題目A 33倍數+1 (C++)