[Codeforces][Round #702][Div.3] A : Dense Array

https://codeforces.com/contest/1490/problem/A

Problem - A - Codeforces

 

[난이도] Div.3
[유형] Greedy

[풀이]
a[i]와 a[i+1]가 dense가 아니라면 둘중 작은 수에서 두배의 수를 더해가면서 배열에 추가해주면 된다.

 

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int tc,n,a[50];
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        int ans = 0;
        for(int i=1;i<n;i++){
            int p=a[i-1],q=a[i];
            if(p>q) swap(p,q);
            if(2*p>=q) continue;
            int cur=p;
 
            for(int cur=2*p;cur<q;cur*=2){
                ans++;
            }  
        }
        printf("%d\n",ans);
    }
}

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round702-Div.3/A.cpp