結果

問題 No.92 逃走経路
ユーザー TatamoTatamo
提出日時 2016-06-21 18:37:22
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,440 bytes
コンパイル時間 621 ms
コンパイル使用メモリ 53,216 KB
実行使用メモリ 4,504 KB
最終ジャッジ日時 2023-08-01 22:50:25
合計ジャッジ時間 1,299 ms
ジャッジサーバーID
(参考情報)
judge14 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 -
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
}
0