Algorithm


Problem Name: beecrowd | 2718

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2718

Christmas Lights

 

By Francisco Elio Parente Arcos Filho, UEA BR Brazil

Timelimit: 1

Giovanna loves Christmas. The parties, the family, Christmas decorations and especially the famous blink Christmas lights. But this year little Gio was sad to realize that his set of lights is broken. Some lights still work, others do not. Giovanna obviously wants to fix her preferred object but does not have enough bulbs to replace all the burned bulbs so she decided to do the following: divide the Christmas lights into ordered groups of 50 bulbs and in each group only fix the largest number of consecutive burned bulbs.

Because of the many groups, the task became tedious and to try to remedy this, Giovanna, noting the similarity of groups with binary representation of numbers when she imagined burned lights bulbs like 1's and functional bulbs like 0's, decided to think of them effectively as numbers and wrote the representations decimals of these binaries then tried to figure out the amount of bulbs to be exchanged from these annotations.

Your task is, given Gio's notes, find out how many bulbs will be changed in each group.

 

Input

 

The first line of the entry contains an integer N (1 ≤ N ≤ 103) representing the number of groups Giovanna wrote down. The next N rows contain an integer X each representing the decimal equivalent of the number representing the group.

 

Output

 

The output consists of N lines each containing the size of the largest sequence of consecutive bulbs burned in each group, respecting the order of entry of the groups.

 

 

 

Input Sample Output Sample

3

11

7

23

2

3

3

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


#include <iostream>
#include <vector>
#include <string>
#include  < algorithm>
#include <bitset>

using namespace std;

#define ull unsigned long long

int main()
{
    ull int n, x, rem;
    cin >> n;
    for (ull int i = 0; i  <  n; ++i)
    {
        cin >> x;
        string s=bitset < 64>(x).to_string();
        s.push_back('0');
        vector < ull int> v;
        vector<ull int>::iterator it;
        ull int k=0;
        for (ull int j = 0; j  <  s.size()-1; ++j)
        {
            k++;
            if (s[j] == '1' && s[j+1] == '0')
                v.push_back(k);
            if (s[j] == '0' && s[j+1] == '1')
                k=0;
        }
        it=max_element(v.begin(), v.end());
        if (it==v.end())
            cout << 0 << endl;
        else
            cout << *it << endl;
    }

    return 0;
}

Copy The Code & Try With Live Editor

#2 Code Example with Javascript Programming

Code - Javascript Programming


const { readFileSync } = require("node:fs")
const [N, ...input] = readFileSync("/dev/stdin", "utf8").split("\n", 1 + 1e3)

const output = Array.from(
	{ length: Number.parseInt(N, 10) },
	(_, index) => {
		return BigInt(input[index])
			.toString(2)
			.split(/0+/g)
			.sort((a, b) => a.length - b.length)
			.pop()
			.length
	}
)

console.log(output.join("\n"))

Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
#2717 Beecrowd Online Judge Solution 2717 Elf Time Solution in C, C++, Java, Js and Python
Next
#2719 Beecrowd Online Judge Solution 2719 How Many Trips Will Noel Make? Solution in C, C++, Java, Js and Python