#99349 (C++11) No.92 逃走経路

• 問題: No.92 逃走経路
• ユーザー: Tatamo
• 提出日時: 2016-06-21 18:37:22
• 言語: C++11 (gcc 11.4.0)
• 結果: WA
• 実行時間: -
• コード長: 1,440 bytes
• コンパイル時間: 542 ms
• コンパイル使用メモリ: 56,728 KB
• 実行使用メモリ: 6,824 KB
• 最終ジャッジ日時: 2024-10-11 18:30:26
• 合計ジャッジ時間: 1,202 ms
• ジャッジサーバーID （参考情報）: judge3 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-

ソースコード

#include<iostream>

using namespace std;

typedef long long ll;

// long longなのでlog10だと怖い気がした(未検証)
int getdigit(ll n){
	int result = 1;
	while(n>9){
		n /= 10;
		result += 1;
	}
	return result;
}

// get number of acceptable digits
int getad(int num){
	if(num >= 0 && num <= 3){
		return num+1;
	}
	else if(num <= 8){
		// num==4: 0,1,2,3
		// num==5: 0,1,2,3,5
		// etc...
		return num;
	}
	else if(num == 9){
		return 8; // 0,1,2,3,5,6,7,8
	}
	else {
		cerr << "invalid number" << endl;
		return -1;
	}
}

ll getTopDigit(ll n, int d){
	for(int i=0; i<d-1; i++){
		n/=10;
	}
	return n;
}

ll delTopDigit(ll n, int d){
	ll tmp = getTopDigit(n, d);
	for(int i=0; i<d-1; i++){
		tmp *= 10;
	}
	return n-tmp;
}

ll banned(ll n){
	ll result = 0;
	int d = getdigit(n);
	ll nn = n;
	int X = getad(9); // 0,1,2,3,5,6,7,8 -> 8
	while(d>0){
		if(d>1){
			ll top = getTopDigit(nn, d);
			if(top != 0){
			
				ll tmp = getad(top-1);
				for(int i=0; i<d-1; i++){
					tmp *= X;
				}
				result += tmp;
			}
			if(top == 4 || top == 9) break;
			nn = delTopDigit(nn, d);
			d--;
		}
		else{
			result += getad(nn);
			d--;
		} 
	}
	result -= 1; // 0が含まれてしまっているため(後で打ち消しあうので、なくても問題ではない)
	result = n-result;
	return result;
}

// AC
int main(){
	ll a,b;
	cin >> a >> b;
	ll b_a = banned(a-1);
	ll b_b = banned(b);
	cout << b_b - b_a << endl;

	return 0;
}