Phoenix has decided to become a scientist.
He is currently investing the growth of bacteria, initially on day one.
There is one bacterium of mass one.
Some number of bacteria will split possibly zero, or when a bacterium of mass M splits, it becomes
two bacteria of mass M divided by two each archaea.
If it is possible for the total mass of all the bacteria to be exactly and if it is possible, he is
interesting the way to obtain that mass using the minimum.
Oh, that's cool.
That is pretty cool.
So you are just given the integer N and you want to see if there is some.
The minimum number of nights.
All right.
The minimum number of nights needed.
Such that the total mass of the buck theory are.
Of all the bacteria to be exactly, and you could be tricked into thinking about each separate bacteria
mess.
And this is not good, right?
Because if you take each separate bacteria and think about eats moss, you could have numbers like two
point twenty five, which is quite confusing.
But we should always think about the total sum of the masses of the bacterias.
That's definitely a better way of solving this.
You start with one bacteria of mass one.
If during the day you split these bacteria, the total mass is still one.
But the thing is.
That now you have two separate bacterias and they are both increased by one.
Then you can split even those or.
All right.
I think I'm onto something here.
If you got tricked and think about the separate mass of each bacteria.
You're not going to solve the problem because those masses could be like fractions, right?
Which is not good.
But if you think about the total mass, let's say, like this on day one.
We have one bacteria of mass one.
So the total mass is one.
And if I choose to split this bacteria.
I'm going to have to bacterias.
Oh.
Zero point five and zero point five.
And on the first night, each of these are increased by one.
So one point five and one point four.
What happened here?
Well, I don't care about these separate numbers, but I care about their son.
So on day one, they basically had one total son.
On day two.
Yeah.
That's gonna be kind of day to day.
I'm going to have.
Some of free.
And if I choose to split them even more so each of the bacteria is splitted.
Again, I'm going to have something like, oh point several, five point seven, five point seven,
five point seven five.
And each of these is increased by one.
Right, and the total sum.
What's it going to be?
I think it's going to be seven here.
It's gonna be seven.
All right.
What do you notice here?
We don't care about these values.
They are ugly, pure about the tattoos.
And basically, let's think about the maximum sum, the maximum total mass that you could achieve on
day one is what?
On day two is free.
Which is one plus two.
And this is, of course, because you transformed this into two bacteria and increased each of the each
of them by one.
So you've basically increased this one by two.
Then you've taken all this to bacterias.
Split them.
Now you have four bacterias and you increased each of them by one.
So you basically have here.
That's right.
One plus two plus four and so on and so forth.
You could even split this into eight separate bacteria.
And when you increase each of those eight by one.
Right.
So I don't know if it's eight ones here, but yeah, I think it is, of course, on let's say I think
night.
The day free or.
No.
No day free on day four.
You're gonna have one plus two.
Plus four.
The fourth observation, which is pretty simple, is that when you look at the total mass on day X,
let's say on day X.
Total moss is going to be one plus two plus four plus dot, dot, dot.
Plus I think toward power X minus.
Which is, of course, to what, power X everything minus one.
So on day X, the sum of the bacterias is less or equal than to what power X minus.
If at some point you have a bacterial.
So you have exactly Kay bacterias.
Or bacteria was the plural.
I don't know, you're basically.
Bill big.
Some of them.
And split them, so when you split some bacteria.
Instead of that book, the area, which was one, of course, you are going to have to.
Bacteria.
So basically, when you have cable Tyria, after one day when you split them, you can get any number
of bacteria from K, K plus one K plus two Dhada that all the way to two the.
Because if you choose to split only one bacteria, then you're gonna have K plus one bacteria.
If you choose to split man, you're gonna have still keep if you choose to split all the bacteria,
you have to cross cable arterials.
So basically.
You had Kay Book Teria.
Now you have.
Some number from here, K.K plus one, K plus 2.0, other that two crossed cable Teria.
And that sum was increased by which number you have chosen from here.
So what you can do basically is that suppose that you are always going to split all of these bacterias
so you start to one bacteria.
Got the bacteria's.
Poor bacteria, eight bacteria that add up, as we've seen.
This is one plus two plus four plus dot, dot, dot plus two.
Add some power, right.
Let's call it power D..
Which is the number of nights or days that you need.
You are basically starting from this some.
And this lady is the smallest number for which this sum is greater or equal than at.
First of all, because this is them.
So for D nights.
The maximum total sum total mosse that you can have is this number.
So this number, of course, has to be greater or equal then.
And if it's less than M.
Is D is not valid.
So first of all, you are going to find the smallest D such that this sum is greater or equal than N
when you have found this D.
You know that that is going to be your answer.
But the problem is.
That some would be actually greater than a.
So if we note this by S..
We could have a difference of and minus s.
So you have found your desire d the minimum one which has this property.
And you have.
To boast that each night you split all the bacterias and you are left with a difference of and minus
s.
And you now have to get rid of this difference.
How will you get rid of this difference where basically you are taking a look at each of these numbers,
one to four, toward power, Dean?
And remember that you could have chosen a less number.
You could literally have chosen as a less number, but what you're gonna do is that you are going to
start from the end.
Or let's take some example.
One, two, four, eight, 16 and 42.
Was this some.
I think it should be 60 free, right?
This is 60 free and let's say our end was something like 45 or something.
All right.
You have your deed, which is for for this example.
No.
Five, five for this example.
And this sum like this is the smallest D such that this sum is greater or equal than N.
But still.
If they were equal, everything would have been all right.
But this sum is greater than than.
Oh yeah, sorry about that.
This is s minus and I realize we're not anyways.
So but this sum is greater than N.
So you will have a difference of S minus M, which is 28.
So from this configuration where you have split each and every bacteria, each and every night, you'll
have to get rid of 28 units of mass.
Well, how would you do that?
First of all, you'll take a look at the greatest number, which is 42.
And remember that when we had K bacteria on some night, we could have chosen to have each number between
K and to cross the key.
Though here we had 16 on the previous night, and we have chosen to upgrade them to 42.
Well.
Let's not do that and keep this number to still be 16.
So one plus two plus four plus eight plus 16.
And then this night, we won't split any bacteria.
And it's still plus 16 in this way from this 28 difference.
We have got rid of 16.
So we still have to deal with 12 different with 12 mass units that are extra.
Right.
Well, basically, we'll do the same thing here.
But what are we gonna do here?
We are taking this 16.
We take a look from the previous night.
You were a.
On the previous night, you were eight.
That means that I could have chosen every number from eight to 60.
So I can choose this to be on a.
So I've basically got rid of eight units of moss, and now I still have four units to subtract.
Then I take a look at this eight the previous night was four.
So I could have chosen instead of this eight to have this four.
And now I got rid of this fort.
And because this is zero to me.
My sum is no, actually equal to N and it's ticket.
I have one.
It's right here again.
Plus two, plus four.
US.
This is not an eight anymore.
It's a four.
This is not a 16 anymore.
It's an eight.
Plus, this is not the first two, it's a six.
One plus two free.
Seven.
Eleven.
Nineteen thirty four, which is a.
Well, let's rewind this problem.
Because I think it's a pretty nice one.
It's not very hard, but it's a pretty nice one for constructive algorithms and stuff like that.
So first of all, the problem asked me.
To print minus one.
If I can obtain any units of mass.
So I'm thinking about.
When it's impossible to obtain any units of what?
Let's take the maximum scenario, right, like this scenario when I have the biggest possible sum or
Messe units or something like that and build up on that.
So I was thinking, like, if I had these nights right, let's call it number the.
Is the problem quality it actually if I have denied basically.
The maximum loss that I could of pain is one plus two plus four, plus dot, dot, dot plus two.
What power?
The minus one or some.
So I'm going to find the smallest D.
Such that this sum is greater or equal than an.
And in order to do that, to obtain this maximum some.
I've tried the scenario in which each bacteria was split during the day.
When I found this D, I know this is my answer.
But if the sum is greater than an.
This should mean that not on each day I'm going to take each and every bacteria in splitted.
I'm going to have to get rid of some units of mass.
And how do I do that?
Well, just as I told you, you're just taking this array.
Let's say you start off with this array.
We have some oray looking like the.
And you start from the greatest number.
You see what is your difference that you want to get rid of?
Which is initially.
S minus N, of course.
And you just take a look.
It could have got rid of two, it powered D minus two on these.
Step on this element.
All right.
Let's check the difference if the difference is greater or equal than this.
You're gonna get rid of this.
If it's less or equal than that, you're gonna get rid of the different units and then you're done,
basically.
And that's it.
Or.