POJ 2719 Faulty Odometer
問題
http://poj.org/problem?id=2719
解法
4を抜かして数える
は
4->5
5->6
6->7
7->8
8->9
と置き換えた9進数で数えることと同じと考える。
つまり、与えられた数の各位に4より大きい数があれば、その位の数から1を引き、できあがった数を9進数とみて10進数に変換すればよい。
#include <cstdio> #include <algorithm> using namespace std; int main(){ int N; while(scanf("%d", &N) && N){ int i; char a[100]; sprintf(a, "%d", N); for(i=0; a[i]!=0; i++){ a[i]-='0'; if(a[i] > 4) a[i]--; } int ans = 0; int nine = 1; for(i--; i>=0; i--){ ans += a[i] * nine; nine *= 9; } printf("%d: %d\n", N, ans); } return 0; }
AOJで、PCKかなんかの過去問で似たような問題を解いたことがあるような気がする