UVa11743

題目

http://domen111.github.io/UVa-Easy-Viewer/?11743
定義一組合法的信用卡卡號可以透過以下步驟檢查

1. 將偶數位置上的數字乘2
2. 將剛剛所得到的數字中每一個位數數值加總
3. 將信用卡號中奇數位數的數字作加總
4. 將步驟2、3兩數相加
5. 判斷個位數是否為0，0為合法卡號，非零為非法卡號

給一組信用卡卡號，求是否為合法卡號

想法

依據題目給的步驟模擬過一遍即可

Code

//By Koios1143
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
int t,tmp,odd,even;
int add(int n){
	int ret=0;
	while(n){
		ret+=n%10;
		n/=10;
	}
	return ret;
}
int main(){
	IOS
	cin>>t;
	while(t--){
		odd=0,even=0;
		for(int i=0 ; i<4 ; i++){
			cin>>tmp;
			bool is_odd=true;
			while(tmp){
				if(is_odd)
					odd+=tmp%10;
				else
					even+=add((tmp%10)*2);
				tmp/=10;
				is_odd=!is_odd;
			}
		}
		if((odd+even)%10!=0)
			cout<<"Invalid\n";
		else
			cout<<"Valid\n";
	}
	return 0;
}

複雜度

將數字 $t$ 的每位數字相加複雜度為 $O(len(t))$
而題目中的數字長度固定為16，故複雜度約為 $O(1)$
其餘操作皆為 $O(1)$
總複雜度 $O(1)$