24h購物| | PChome| 登入
2011-08-03 17:51:59| 人氣3,167| 回應1 | 上一篇 | 下一篇

a159. 11743 - Credit Check

推薦 0 收藏 0 轉貼0 訂閱站台

a159. 11743 - Credit Check

內容 :

這些日子以來,使用信用卡在網路上購買東西已經變的司空見慣。
但是因為信用卡卡號比較長,很容易在輸入他們的時候打錯。
為了快速的識別錯誤,如數字打錯,大多數的電子商務網站都會用一種校檢演算法來確認信用卡卡號

一種較為流行的校檢演算法叫做 "Luhn"演算法 (Luhn algorithm),它可以檢測任何一位元的錯誤及多位元錯誤:

1.從倒數第二個位元開始,將他們放到後面,並且加倍其他沒有移動的位元到另一個列表
2.把列表內的數字的位元加總(n),再把被移到後面的數字加總(m),在把兩個數加起來 (n+m)
3.如果這個數字的結尾是0,則信用卡卡號為合法的,反之則是不合法的。

這裡有個例子,以這組號碼為例 5181 2710 9900 0012:

1.把相對應的數字加倍後,放到另一個列表 (5 181 2719900012) :10,16,4,2,18,0,0,2。

2.把這些數的位元加起來得到 (1+0) + (1+6) + 4 + 2 + (1+8) + 0 + 0 + 2=25
  沒有對應到的位元合為1+1+7+0+9+0+0+2 = 20 , 所以最後的總和是 20 + 25 = 45。

3. 45不是以0結尾,故這組信用卡號並不合法。

對於這個問題,你需要寫一個根據 Luhn演算法的程式來確認輸入的信用卡號是否合法。
 
   
圖片來源:Uva題目 Q11743

輸入說明 :

輸入的第一行為N 代表接下來有幾組測試資料

之後的N行

每行包含一行信用卡號碼

每個信用卡號碼由16個 10進位位數字組成四組,並且以空白分隔

輸出說明 :

 輸出包含一行文字

如果號碼是合法的,請輸出"Valid"

如果不合法,請輸出"Invalid" 

範例輸入 :help

2
5181 2710 9900 0012
5181 2710 9900 0017

範例輸出 :

Invalid
Valid

提示 :

測資頗大,請小心駕駛 :D


Uva原題

 

 

 

出處 :

UVa ACM 11743 (管理:grd)



/**********************************************************************************/
/*  Problem: a159 "11743 - Credit Check" from UVa ACM 11743                       */
/*  Language: C                                                                   */
/*  Result: AC (288ms, 192KB) on ZeroJudge                                        */
/*  Author: morris1028 at 2011-08-01 23:39:34                                     */
/**********************************************************************************/


#include<stdio.h>
char s[20];
main() {
    int n, a, t1, t2;
    scanf("%d", &n), getchar();
    while(n--) {
        gets(s);
        for(a = 0; s[a]; a++)    s[a] = (s[a]-'0')*2;
        t1 = s[0]%10+s[0]/10 + s[2]%10+s[2]/10 + s[5]%10+s[5]/10
        + s[7]%10+s[7]/10 + s[10]%10+s[10]/10 + s[12]%10+s[12]/10
        + s[15]%10+s[15]/10 + s[17]%10+s[17]/10;
        t2 = (s[1] + s[3] + s[6] + s[8] + s[11] + s[13] + s[16] + s[18]) /2;
        if((t1+t2)%10)    puts("Invalid");
        else    puts("Valid");
    }
    return 0;
}

台長: Morris
人氣(3,167) | 回應(1)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:a158. 11827 - Maximum GCD
此分類上一篇:c095. False coin

GrD
我的天啊......

C 的 優化真的是太強大了...... 240ms飛過去~~~

pascal最快的是 1.1s而已
2011-08-04 20:08:31
版主回應
PASCAL 沒辦法優化, C++ 的優化更神, 在此不方便透露
2011-08-05 20:40:07
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文