1490A - Dense Array - CodeForces Solution

greedy math *800

Please click on ads to support us..

Python Code: 

for _ in range(int(input())):
    n=int(input())
    a=[int(x) for x in input().split()]
    cnt=0
    flag=0
    for i in range(n-1):
        if(((max(a[i],a[i+1])/min(a[i],a[i+1])))>2):
            flag+=1
            maxi=max(a[i],a[i+1])
            mini=min(a[i],a[i+1])
            while(maxi>mini):
                cnt+=1
                mini*=2
    print(cnt-flag)

C++ Code: 

#include <iostream>
int main(){
    int t,n,p,c,a;
    std::cin>>t;
    
    while(t--){
        std::cin>>n>>p;
        a=0;
        while(--n){
            std::cin>>c;
            if(c-p) a+=31-__builtin_clz((p+c-1)/(p>c?c:p)-1);
            p=c;
            
        }
            std::cout<<a<<'\n';
        
    }}


Comments

Submit
0 Comments
More Questions

1665C - Tree Infection
1665D - GCD Guess
29A - Spit Problem
1097B - Petr and a Combination Lock
92A - Chips
1665B - Array Cloning Technique
1665A - GCD vs LCM
118D - Caesar's Legions
1598A - Computer Game
1605A - AM Deviation
1461A - String Generation
1585B - Array Eversion
1661C - Water the Trees
1459A - Red-Blue Shuffle
1661B - Getting Zero
1661A - Array Balancing
1649B - Game of Ball Passing
572A - Arrays
1455A - Strange Functions
1566B - MIN-MEX Cut
678C - Joty and Chocolate
1352E - Special Elements
1520E - Arranging The Sheep
1157E - Minimum Array
1661D - Progressions Covering
262A - Roma and Lucky Numbers
1634B - Fortune Telling
1358A - Park Lighting
253C - Text Editor
365B - The Fibonacci Segment