Project Euler 112

左から右までどの桁もその左の桁を上回らない数を増加数と呼ぶ。例えば、134468。

同様に、どの桁もその右の桁を上回らない数を減少数と呼ぶ。例えば、66420。

増加数でも減少数でもない正の整数を「活発な」数と呼ぶことにする。例えば、155349。

100以下の数に活発な数が無いのは明らかだが、1000より下の数では半数を少し上回る数(525)が活発である。

実際、活発な数の割合が50%に達する最少の数は538である。

驚くべきことに、活発な数はますます一般的になり、21780では活発な数の割合は90%に達する。

活発な数が数の割合が99%ちょうどになる最小の数を求めよ。

やるだけ

#include <iostream>
#include <deque>
using namespace std;

deque<int> integerDigits(int x){
	deque<int> arr;
	while(x!=0){
		arr.push_front(x%10);
		x/=10;
	}
	return arr;
}

bool isBouncy(int n){
	if(n < 100) return false;
	deque<int> d = integerDigits(n);

	bool increase = false, decrease = false;

	int a,b;
	for(int i=0 ; i<d.size()-1 ; i++){
		a = d[i];
		b = d[i+1];

		if(a > b) decrease = true;
		if(a < b) increase = true;
	}

	if(increase && decrease) return true;
	return false;
}

int main(){
	int cnt1=0 , cnt2=0;
	
	for(int i=1 ; i<100000000 ; i++){
		if(isBouncy(i)) cnt1++;
		else cnt2++;

		if( (double)cnt1/(double)(cnt1+cnt2) >= 0.99){
			cout << i << endl;
			break;
		}
	}
}