Problem-Solving/Codeforces
[Codeforces][Round #702][Div.3] A : Dense Array
has2
2021. 3. 1. 22:44
https://codeforces.com/contest/1490/problem/A
Problem - A - Codeforces
codeforces.com
[난이도] 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