743B - Chloe and the sequence - CodeForces Solution


binary search bitmasks constructive algorithms implementation *1200

Please click on ads to support us..

Python Code:

import math

a, k = map(int, input().split())

if k % 2 != 0:
    print(1)
    exit()

if k & k-1 == 0:
    print(int(math.log2(k)) + 1)
    exit()

l = 2 ** math.floor(math.log2(k)) + 1
r = 2 ** math.ceil(math.log2(k)) - 1
center = (l + r) // 2

n = math.floor(math.log2(k))

while center != k:
    if center > k:
        r = center - 1
    else:
        l = center + 1
    
    center = (l + r) // 2
    n -= 1
    
print(n)

C++ Code:

#include<bits/stdc++.h>
using namespace std;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long int
#define ull unsigned long long int
#define nl "\n"
#define MOD 1e9+7
#define pb push_back
#define ppb pop_back
#define dbg(x) cerr<<#x<<"-"<<x<<nl;

/* solve function */
void solve(){
    ll n,k;
    cin>>n>>k;
    ll x = 2;
    int i=1;
    while(x<=pow(2,n)){
        if(k%x == x/2){
            cout<<i<<nl;
            return;
        }
        ++i;
        x *= 2;
    }
    cout<<-1<<nl;
}


/* main function */
int main(){
    clock_t start,end;
    start=clock();
    fast();
    ll t=1;
    ll i=1;
    /* cin>>t; */
    while(t--){
        /* cout<<"Case# "<<i<<": "; */
        solve();
        i++;
    }
    end=clock();
    double time=double(end-start)/double(CLOCKS_PER_SEC);
    cerr<<nl<<"Time: "<<time<<" sec"<<nl;
}


Comments

Submit
0 Comments
More Questions

1302. Deepest Leaves Sum
1209. Remove All Adjacent Duplicates in String II
994. Rotting Oranges
983. Minimum Cost For Tickets
973. K Closest Points to Origin
969. Pancake Sorting
967. Numbers With Same Consecutive Differences
957. Prison Cells After N Days
946. Validate Stack Sequences
921. Minimum Add to Make Parentheses Valid
881. Boats to Save People
497. Random Point in Non-overlapping Rectangles
528. Random Pick with Weight
470. Implement Rand10() Using Rand7()
866. Prime Palindrome
1516A - Tit for Tat
622. Design Circular Queue
814. Binary Tree Pruning
791. Custom Sort String
787. Cheapest Flights Within K Stops
779. K-th Symbol in Grammar
701. Insert into a Binary Search Tree
429. N-ary Tree Level Order Traversal
739. Daily Temperatures
647. Palindromic Substrings
583. Delete Operation for Two Strings
518. Coin Change 2
516. Longest Palindromic Subsequence
468. Validate IP Address
450. Delete Node in a BST