A Problem on Sticks SOLUTIONS TREE2

A Problem on Sticks SOLUTION

On a bright day, Akbar and Birbal were going for a relaxed stroll in castle gardens. Unexpectedly, Akbar saw a lot of sticks on the ground and chose to test Birbal’s brains. 
 
There are N leave holders with insignificant size (numbered 1 through N) in succession on the ground. Akbar puts all the sticks in them vertically; for each legitimate I, the underlying stature of the stick in the I-th holder is Ai. Birbal has a stick shaper and his errand is to totally cut every one of these sticks, for example diminish the statures of all sticks to 0. He may perform at least zero activities; in every activity, he ought to do the accompanying: 
 
Pick a number H and fix the shaper at the tallness H over the ground. 
 
The shaper moves from the 1-st to the N-th stick holder. At whatever point it experiences a stick whose current stature is more noteworthy than H, it chops this stick down to tallness H (for example for a stick with stature h>H, it eliminates its upper part with length h−H). 
 
All the upper pieces of sticks that are cut in one activity must have equivalent lengths. Something else, the activity may not be performed. 
 
For instance, in the event that the statures of sticks are at first [5,3,5], at that point some legitimate qualities for H in the primary activity are 3 and 4 ― the shaper cuts the upper pieces of two sticks and their lengths are [2,2] and [1,1] individually. H=2 is an invalid decision since it would cut the upper pieces of each of the three sticks with lengths [3,1,3], which are not all equivalent. 
 
Akbar needs Birbal to totally cut all sticks in the base conceivable number of tasks. In the event that you need to be companions with Birbal, assist him with taking care of the issue. 
 
Info 
 
The main line of the info contains a solitary number T signifying the quantity of experiments. The depiction of T experiments follows. 
 
The primary line of each experiment contains a solitary number N. 
 
The subsequent line contains N space-isolated numbers A1,A2,… ,AN. 
 
Yield 
 
For each experiment, print a solitary line containing one number ― the base number of tasks expected to totally cut all the sticks. 
 
Limitations 
 
1≤T≤50 
 
1≤N≤105 
 
0≤Ai≤109 for each substantial I 
 
Subtasks 
 
Subtask #1 (20 focuses): N≤50 
 
Subtask #2 (80 focuses): unique limitations 
 
Model Input 
 
 
 
1 2 3 
 
Model Output 
 
 
Clarification 
 
Model case 1: Birbal may play out the accompanying three tasks: 
 
Fix the shaper at H=2. The statures of the sticks after this activity are [1,2,2]. 
 
Fix the shaper at H=1. The statures of the sticks after this activity are [1,1,1]. 
 
Fix the shaper at H=0. After this activity, all sticks are totally cut.
 
LOGIC VIDEO IS REMOVED

5 thoughts on “A Problem on Sticks SOLUTIONS TREE2”

  1. bhia padh na nahi ata hai kya tere ko english they said no solutions will be uploaded atleast they are helping with logic which is not cheating. first of all itna problem hai toh why are you seraching for solutions be people like you are cancer to the society

    Reply

Leave a Comment

close
error: Content is protected !!