Processing math: 100%

Friday, 1 November 2019

[Math][Codeforces] 1247C P Binary

P Binary:

My solution:
I was giving a virtual contest for this. The question before this one took 1 hour (ughh), and thus I couldn't solve this in time. So I solved this later.

So you're given a number n, which we need to check how many p-binary numbers are needed to make this n number. 

What are you gonna do?

So basically let's say we have n which we describe using m p-binary numbers. That will look like:
n = (2^{x_1}+p)+(2^{x_2}+p)+...+(2^{x_m}+p)
That can be made to look like:
n = (\sum_{i=1}^{m} 2^{x_i})+m*p
That is equal to:
n - m*p = (\sum_{i=1}^{m} 2^{x_i})

We do not know the value of m here. So,we can create an array with:
n-i*p where i goes from {1,...,100}, because you don't need more than that.

Now, check the number of set bits for each number in the array, starting from the left. Once you reach a point, where \text{number of set bits} <= i, you stop. As you can create i such elements in the expansion given above, from a lesser number of bits. Just remember that you can create 2 elements from one set bit if the number is not 1. 

For example if you have a 2 (10), you can have two 1s (01). Similarly, you can see that you can the same for 4,8, et cetera. But you can't divide 1. So remember to check that n-i*p>=i, which means that the number can create i elements. 

The logic here is that a number j can, at max, be divided into j elements.

It's a good question. 

Here's the code:
#include<iostream>
using namespace std ;
#define f(i,s,n) for(int i=s;i<n;i++)
typedef long long ll ;
int bits(ll n)
{
int count = 0 ;
while(n) n=n&(n-1),count++ ;
return count ;
}
int main()
{
ll n ;
ll p ;
cin>>n>>p ;
ll arr[30] ;
arr[0] = p ;
f(i,1,30) arr[i] = arr[i-1]+p ;
f(i,0,30) arr[i] = n-arr[i] ;
int minn = 33 ;
f(i,0,30)
{
int b = bits(arr[i]) ;
if(arr[i]>=i+1 && b!=0 && bits(arr[i])<=i+1)
{
cout<<i+1<<endl ;
return 0;
}
}
cout<<"-1"<<endl ;
//cout<<minn<<endl ;
}
view raw PBinary hosted with ❤ by GitHub

812B - Sagheer, the Hausmeister

 812B - Sagheer, the Hausmeister Problem statement Link : https://codeforces.com/problemset/problem/812/B Gist There are n floors and ther...