

In some cities, the sewage system does not work properly and every time it rains, water accumulates on the streets and in between buildings, blocking traffic and causing distress.
You have an N number of buildings and an array with the height of every building.
You want to find out what is the maximum volume of water that would hypothetically accumulate after heavy rain, in between 2 buildings.
Input: N > 0 on the first line, array of N integer elements on the second line.
Output: integer positive X units of water.
Example: The following sequence of heights will generate the structure below:
Sequence: 1 2 1 5 2 4 1 0 1 2 6 4 5 2 3 4 1 2
The biggest block of water would contain 20 units of water.
<pre>using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace heavy_rain{
class Program{
static void Main(string[] args){
System.IO.StreamReader sr;
int n = 0, i = 0, result = int.MaxValue;
int[] buildingHeights = null;
try {
sr = new System.IO.StreamReader(args[0]);
String[] lines = new String[2];
String line = null;
while ((line = sr.ReadLine()) != null) {
lines[i++] = line;
}
n = int.Parse(lines[0]);
buildingHeights = new int[n];
String[] heights = lines[1].Split(' ');
for(int j = 0; j < heights.Length; j++) {
buildingHeights[j] = int.Parse(heights[j]);
}
Console.WriteLine(result);
}
catch (Exception e) {
System.Diagnostics.Trace.WriteLine(e.Message);
}
}
}
}





I don't think you'll find anyone here to do your homework for you. You'll have to do it yourself. But if you get stuck and have a specific question, come back and ask.
The difficult we do right away...
...the impossible takes slightly longer.





Member 13003743 wrote: The biggest block of water would contain 20 units of water. That does not make much sense. Ask your professor what is the connection is between height of building and amount of water.





Always assume that your teacher is reading this site, and will notice your attempt to cheat on your homework.
Expecting other people to do your work for you will not end well. How do you think that would go down in the real world, when you've got a real job and a mortgage to pay?
If you don't know how to start, then talk to your teacher.
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
 Homer





Your main effort was to copy your assignment.
We do not do your HomeWork.
HomeWork is not set to test your skills at begging other people to do your work, it is set to make you think and to help your teacher to check your understanding of the courses you have taken and also the problems you have at applying them.
Any failure of you will help your teacher spot your weaknesses and set remedial actions.
So, give it a try, reread your lessons and start working. If you are stuck on a specific problem, show your code and explain this exact problem, we might help.
As programmer, your job is to create algorithms that solve specific problems and you can't rely on someone else to eternally do it for you, so there is a time where you will have to learn how to. And the sooner, the better.
When you just ask for the solution, it is like trying to learn to drive a car by having someone else training.
Creating an algorithm is basically finding the maths and make necessary adaptation to fit your actual problem.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





Before we start, my textbook declares lgn as base two.
I only have one question, how did log2 become n (both highlighted in yellow in the picture)? Is it because log2 = 1, which is too small to even matter? Below is a link of the equations.
/Users/conrados/Desktop/20170207_091636000_iOS.jpg





The link to the picture won't work as that's your local Windows file (and it would have to be a proper web anchor).
This space for rent





Member 12986878 wrote: how did log2 become n Ask the person who wrote the textbook.





Member 12986878 wrote: how did log2 become n
when a log2 and an exp(n, 2) love each other very much...





What we read is meaningless.
Do not reformulate the question.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein





Hello all,
I do need to send a motor from position A to B accelerating and decelerating accordingly to the defined allowed acceleration.
Constant acceleration.
Different starting speeds.
Different starting positions.
Different ending positions.
0 end speed.
I've tried to make my own which works perfectly when the values allow the motor to reach the maximum speed "plateau" but it is not working well when is not possible to achieve this and v0 (initial speed) and vf (end speed) are different.
Previous notes:
vmax = maximum allowed speed for the movement.
x0 = initial position.
xf = destination position.
v0 = initial speed.
vf = end speed (final).
ta = acceleration time from v0 to vmax.
da = distance to accelerate from v0 to vmax.
tf = braking time from vmax to vf.
df = braking distance from vmax to vf.
dist = total distance I want to move the motor xfx0
The code I've used is:
LimitIterations = 1000
ta = Abs((vmax  v0) / a)
da = (v0 * ta) + (0.5 * a * ta * ta)
tf = Abs((vmax  vf) / a)
df = (vf * tf) + (0.5 * a * tf * tf)
If (da + df > dist + 0.000000001) Then
DistTotal = xf  x0  da  df
RelAccDec = da / (da + df)
dist_corr_acc = DistTotal * RelAccDec
da = da + dist_corr_acc
dist_corr_dec = DistTotal * (1  RelAccDec)
df = df + dist_corr_dec
taux = Sqr(da / (0.5 * a))
taux = (Sqr((2 * a * da) + (v0 * v0))  v0) / a
vmax = v0 + (a * taux)
Do
ta = Abs((vmax  v0) / a)
da = (v0 * ta) + (0.5 * a * ta * ta)
tf = Abs((vmax  vf) / a)
df = (vf * tf) + (0.5 * a * tf * tf)
If (da + df > dist + 0.000000001) Then
vmax = vmax  1
iterations = iterations + 1
If (iterations > LimitIterations) Then
ErrorID = 1
Exit Do
End If
Else
Exit Do
End If
Loop
End If
WRONG APPROACH EXPLANATIONS
The idea of that code was to find the maximum speed that can be reached given the specified conditions.
When the da + df are bigger than the total distance I'm doing a proportional reduction which approximates the vmax to it's desired/needed value.
The problem here I think is that part: I don't have to make a proportional reduction, I do need to find the position in which the acceleration movement and the deceleration movement are coincident once I will have this position then I should check the speed any of the movements has in that position. And that one should be vmax.
Now the issue is doing that...
I could use 0 as the starting position for the acceleration and xf as the starting position for the deceleration.
Both accelerations are the same (different signs).
I've seen examples of that when movements are not accelerated (the typical problem with two trains that leave the station) but nothing when the movements have constant acceleration.
Any hint, example, resource, formula that could solve it...
The solution
OK, at the end I've done it by algebra:
vp = v0 + (a0 * t0)
vp = v1 + (a1 * t1)
v0+(a0*t0) = v1+(a1*t1)
t1=((v0v1)+(a0*t0))/a1
d0 = (v00 * t0) + (0.5 * a0 * t0 * t0)
d1 = (v01 * t1) + (0.5 * a1 * t1 * t1)
D = (v00 * t0) + (0.5 * a0 * t0 * t0) + (v01 * t1) + (0.5 * a1 * t1 * t1)
And solve the quadratic equation to get the positive value (as we are speaking of time).
So.. this previous code substitutes the wrong approach method.
Thank you all,
modified 12Feb17 9:01am.





So at first you need to calculate the distance between both Points. That will be normally the Hypothenuse of a rightangled triangle.
Now you have to calculate the distance you need for speeding up your Motor. This could be calcuated with the final Speed (the Speed when you have finished the accelaration) and the acceleration itself.
The same you do for the decelaration.
If the distance for speeding up and the distance for speeding down is less than your complete distance then the difference is the way you drive with your final Speed and you will get a Trapezoid.
If the distance for speeding up and the distance for speeding down equal your complete distance then you will get a Triangle.
If the distance for speeding up and the distance for speeding down is more than your complete distance then you have to calculate the Point where both triangles meet. In this case your Motor doesn't reach the final Speed and your hullcurve will also be a triangle  but with a lower edge.
But you don't need to do an Interpolation ...





Hello Ralf,
Everything works.
I was simply trying to use a too high speed for a too short movement (totally obfuscated trying to get something impossible).
The only problem that I do still have is that I don't know how to efficiently find the maximum available speed.
What I'm doing is simple as:
Do
ta = Abs((vmax  v0) / a)
da = (v0 * ta) + (0.5 * a * ta * ta)
tf = Abs((vmax  vf) / a)
df = (vf * tf) + (0.5 * a * tf * tf)
If (da + df > dist) Then
If (v0 = vf) Then
taux = (Sqr((a * dist) + (v0 * v0))  v0) / a
vmax = v0 + a * taux
Else
vmax = vmax  1
End If
End If
Loop While (da + df > dist)
This works "perfectly":
 Avoiding the fact the maximum used speed will not be the purest maximum available.
 Avoiding the fact that it takes "ages" to find the maximum allowed speed for the current movement.
Any suggestion on how to find the maximum allowed speed in a faster way when v0 <> vf?
The initial data I do have is:
vmax (the one entered by the user it could be too high for what is possible).
x0 (initial position).
v0 (initial speed).
a (acceleration).
xf (end position).
vf (end speed (now we consider it always 0)).
Thank you.
modified 7Feb17 6:27am.





Perhaps this could be a Solution for you : (PseudoCode)
distance_with_v = x1  x0  s_Acc  s_Dec
if Distance_with_v < 0 then
Relation_Acc_Dec = s_Acc / (s_Acc + s_Dec)
DistanceCorrecting_Accelaration = Distance_with_v * Relation_Acc_Dec
da = s_Acc  DistanceCorrecting_Accelaration
DistanceCorrecting_Decelaration = Distance_with_v * (1  Relation_Acc_Dec)
df = s_Dec  DistanceCorrecting_Decelaration
end if





Hello Ralf,
I can't see how this will help on calculating the vmax...
I understand that at the first line you are testing if the constant speed will be possible or not.
Then you go inside the if clause only if that constant (vmax) is not possible to reach.
So we are at my "(da + df ) > dist" if clause.
But from now on I can't see how this can help me... I'm after the vmax and here I can't see anything like that...
s_Acc and s_Dec are da and df respectively?
Thank you...





Hello Joan,
you are right  s_Acc is equal to your da and s_Dec is equal to your df.
Now I calculate the distance which would be driven with the wanted Speed (vMax).
If this distance is negative I calculate the Relation from the original calculated da to the sum of da + df.
Now the correctingvalue for da is da multiplied with this relation.
If you now reduce da with this value you get the new Point for da with the same Accelaration. Behind this Point (where you haven't reached your wanted Speed) you have to decelarate the Speed. The second calculation is not necessary but it confirms the first calculation.
I hope it helps you with this explaining ...





Hi again,
I've tried it and ported it into the code.
It looks promising as the newly calculated da + df are always the distance to run and moreover in the graphs I can see the numbers are what they should.
But I'm still having problems calculating the time and therefore the maximum speed:
ta = Abs((vmax  v0) / a)
da = (v0 * ta) + (0.5 * a * ta * ta)
tf = Abs((vmax  vf) / a)
df = (vf * tf) + (0.5 * a * tf * tf)
If (da + df > dist + 0.000000001) Then
If (v0 = vf) Then
taux = (Sqr((a * dist) + (v0 * v0))  v0) / a
vmax = v0 + a * taux
Else
DistTotal = xf  x0  da  df
RelAccDec = da / (da + df)
dist_corr_acc = DistTotal * RelAccDec
da = da + dist_corr_acc
dist_corr_dec = DistTotal * (1  RelAccDec)
df = df + dist_corr_dec
taux = (Sqr((a * dist) + (v0 * v0))  v0) / a
vmax = v0 + (a * taux)
End If
End If
For a data set of
vmax = 6000
v0 = 500
a = 2000
x0 = 200
xf = 1200
I should get a vmax of 1457 but I'm getting a vmax of 1500. as a first approximation this is ok, but I would like to get the right one from start.
Can you see something wrong with the approach?
Thank you very much Ralf.
PS: I'm sorry to annoy you.





Hola Joan,
I can't understand in the Moment from where the formula for taux comes.
I would work with the formula s = 0,5 * a * t² which is for t=(s / (0,5 * a))^0,5  you have the Acceleration and also the new calculated distance (s = da or df).
Would you give this approach a try ?
If it also fails I will tomorrow look and try something else.
PS : don't think about it  you're welcome  de nada





Hi again Ralf,
Well, that formula works perfectly if v0 is 0...
If v0 > 0 then I need to loop to decrease the vmax to make it suitable to the movement... which is superugly in the best case.
So... I guess that the formula you sent me is good, but it lacks the control of v0.
LimitIterations = 1000
ta = Abs((vmax  v0) / a)
da = (v0 * ta) + (0.5 * a * ta * ta)
tf = Abs((vmax  vf) / a)
df = (vf * tf) + (0.5 * a * tf * tf)
If (da + df > dist + 0.000000001) Then
DistTotal = xf  x0  da  df
RelAccDec = da / (da + df)
dist_corr_acc = DistTotal * RelAccDec
da = da + dist_corr_acc
dist_corr_dec = DistTotal * (1  RelAccDec)
df = df + dist_corr_dec
taux = Sqr(da / (0.5 * a))
taux = (Sqr((2 * a * da) + (v0 * v0))  v0) / a
vmax = v0 + (a * taux)
Do
ta = Abs((vmax  v0) / a)
da = (v0 * ta) + (0.5 * a * ta * ta)
tf = Abs((vmax  vf) / a)
df = (vf * tf) + (0.5 * a * tf * tf)
If (da + df > dist + 0.000000001) Then
vmax = vmax  1
iterations = iterations + 1
If (iterations > LimitIterations) Then
ErrorID = 1
Exit Do
End If
Else
Exit Do
End If
Loop
End If
So this is what I've done till now... It should be much easier to find the maximum speed available for the movement.
so, thank you very much for your time.
Joan.





Hi Joan,
I think I will later take a look to this specific part of your Problem.
Until now I only saw the regular MovementCharacteristic (Start with v=0, Accelerate, perhaps drive with vMax, Decelerate to v=0).
What you now have is : your Movement is not finished a Point x1, from this Point you start a new Movement to Point x2 with perhaps new Parameters. So your EndingSpeed a x1 is not =0  it should be the workingspeed for the new Movement.
Am I right so far ?
What kind of machine do you want to control ?
I think your Motor is not a Synchron(Servo)Motor  I suppose you have an ASynchron(Frequencycontrolled)Motor or a StepperMotor ...?





Hi again Ralf,
Thank you.
Yes and no, a normal movement will be from x0 (at v0) to xf (at vf) (usually both speeds will be 0).
But, Imagine that while on the path to x0 to xf the user press stop and the motor must stop as soon as possible.
Then I'll have to send the motor at it's nearest possible position and therefore the v0 will be the one it was used at the moment the user pressed the stop button. So a normal movement but with a v0 > 0.
The machine I want to control is a special prototype for cutting and pile paper sheets at a very fast rate, but the worst part here is that the customer has decided to use asynchronous motors and drives to move the axis on the part of the machine I'm in charge... with servomotors this would be supereasy... drives and asynchronous motors offer some problems due to accelerations, inertia... and of course the position, speed, torque loops must be created from scratch as the CNC can't handle them... (well, it could using a virtual axis and using that virtual axis as the master of the asynchronous drive, but the customer doesn't want it).
PS: the strange formula just before the ugly code comes from this page: Help w/ acceleration formula  Physics Forums  The Fusion of Science and Community[^] :
a = Vc/t
a = (VeVo)/t
a = ( (Vo^2 + 2ad)^(1/2)  Vo )/t
at = ( (Vo^2 + 2ad)^(1/2)  Vo )
t = ( (Vo^2 + 2ad)^(1/2)  Vo )/a
You are right so far...
PS2: And a little bit more of information:
This:
taux = (Sqr((2 * a * da) + (v0 * v0))  v0) / a
vmax = v0 + (a * taux) Gives exactly the same than this:
vmax = Sqr((v0 * v0) + 2 * a * (da))
which is wrong...
Joan.
modified 8Feb17 3:29am.





Hi Joan,
I think I understand your Problem because Automation of machines is also my Profession.
I'm not sure that an asynchronous Motor is the right approach  but that would be another Story.
If you want to stop the Motor during it's cycle (because of urgency or a fault) you don't need to calculate the distance  here it is necessary (my opinion) to realize a maximum of decelaration.
I thought that you wanted to change from one Speed to another during positioning (splining).
In this case the formula's should be corrected ... I think I have a Solution for this.
Cheers
Ralf





Hi Ralf,
Ralf Meier wrote: I'm not sure that an asynchronous Motor is the right approach
It is not... but customers are here to make our lives easy, aren't they?
Ralf Meier wrote: If you want to stop the Motor during it's cycle (because of urgency or a fault) you don't need to calculate the distance  here it is necessary (my opinion) to realize a maximum of decelaration.
Yes, in that case that would be the desired thing. I'm not thinking on an emergency situation, just a stop button press (aborting the movement of an axis gracefully).
And of course, having the possibility to change the destination while the axis is moving would be a plus.
Ralf Meier wrote: In this case the formula's should be corrected ... I think I have a Solution for this.
Thank you again.





OK ... this is my Approach :
I have a movement x0 to x1 completed and change now directly to the movement x1 to x2.
The movement x1 to x2 has a different speed and perhaps a different accelaration.
To calculate the time for the speedchange I use your formula t = v / a but now v is the difference between v_x0_x1 and v_x1_x2
So : t = abs(v_x0_x1  v_x1_x2) / a_x1
Then you get the distance for the speedchange (slower or faster) = 0,5 * a_x1 * t^2
Be so kind and put this into your test and tell me your results ...
... to be continued





Hi again Ralf,
Ralf Meier wrote: So : t = abs(v_x0_x1  v_x1_x2) / a_x1
So... In my case, given the axis was still moving when a new command has entered:
t = abs(v0  vmax)/a
As the acceleration must be constant for all the axis movements.
v0 is the speed it was active at the new command reception, so it was the speed the axis was moving from x0 to x1, vmax is the speed I want from x1 to x2 and again, a is constant.
This gives me the time to change from v0 to vmax... so the ta time in my code.
Then I'm using the 0.5*a*t^2 and I get
da = 0.5*a*ta^2
Which again gives me the same results that I had before...
Thank you very much.



