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