August 29, 2015 | Ajinkya Wavare

Cut the sticks

Problem Statement

You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:

5 4 4 2 2 8

Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:

3 2 2 6

The above step is repeated until no sticks are left.

Given the length of N sticks, print the number of sticks that are left before each subsequent cut operations.

Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

Input Format
The first line contains a single integer N.
The next line contains N integers: a₀, a₁,…a_N-1 separated by space, where a_i represents the length of i^th stick.

Output Format
For each operation, print the number of sticks that are cut, on separate lines.

Constraints
1 ≤ N ≤ 1000
1 ≤ a_i ≤ 1000

Sample Input #00

6
5 4 4 2 2 8

Sample Output #00

Sample Input #01

8
1 2 3 4 3 3 2 1

Sample Output #01

Explanation

Sample Case #00 :

sticks-length        length-of-cut   sticks-cut
5 4 4 2 2 8             2               6
3 2 2 _ _ 6             2               4
1 _ _ _ _ 4             1               2
_ _ _ _ _ 3             3               1
_ _ _ _ _ _           DONE            DONE

Sample Case #01

sticks-length         length-of-cut   sticks-cut
1 2 3 4 3 3 2 1         1               8
_ 1 2 3 2 2 1 _         1               6
_ _ 1 2 1 1 _ _         1               4
_ _ _ 1 _ _ _ _         1               1
_ _ _ _ _ _ _ _       DONE            DONE

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define max 1000
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int l,i,j,num[max],min=1000,count=0;
    cin>>l;
    for(i=0;i<l;i++){
        cin>>num[i];
        if(num[i]<min)
            min=num[i];
    }
    sort(num,num+l);
    for(j=0;j<l;j++)
    {
        count=0;
        if(num[l-1]==0)
            break;
        for(i=0;i<l;i++){
            if(num[i]>=min){
                num[i]-=min;
                count++;
            }
        }
        cout<<count<<endl;
        min=1000;
        for(i=0;i<l;i++){
            if(num[i]!=0 & num[i]<min)
                min=num[i];
        }    
    }
    return 0;
}

Calvin is driving his favorite vehicle on the 101 freeway. He notices that the check engine light of his vehicle is on, and he wants to service it immediately to avoid any risks. Luckily, a service lane runs parallel to the highway. The length of the service lane is N units. The service lane consists of N segments of equal length and different width.

Calvin can enter to and exit from any segment. Let’s call the entry segment as index i and the exit segment as index j. Assume that the exit segment lies after the entry segment (i≤j) and 0≤i. Calvin has to pass through all segments from index i to index j (both inclusive).

Paradise Highway

Calvin has three types of vehicles – bike, car, and truck – represented by 1, 2 and 3, respectively. These numbers also denote the width of the vehicle.

You are given an array width of length N, where width[k] represents the width of the k^th segment of the service lane. It is guaranteed that while servicing he can pass through at most 1000 segments, including the entry and exit segments.

If width[k]=1, only the bike can pass through the k^th segment.
If width[k]=2, the bike and the car can pass through the k^th segment.
If width[k]=3, all three vehicles can pass through the k^th segment.

Given the entry and exit point of Calvin’s vehicle in the service lane, output the type of the largest vehicle which can pass through the service lane (including the entry and exit segments).

Input Format

The first line of input contains two integers, N and T, where N denotes the length of the freeway and T the number of test cases. The next line has N space-separated integers which represent the width array.

T test cases follow. Each test case contains two integers, i and j, where i is the index of the segment through which Calvin enters the service lane and j is the index of the lane segment through which he exits.

Constraints
2≤N≤100000
1≤T≤1000
0≤i<j<N
2≤j−i+1≤min(N,1000)
1≤width[k]≤3,where 0≤k<N

Output Format

For each test case, print the number that represents the largest vehicle type that can pass through the service lane.

Note: Calvin has to pass through all segments from index i to index j (both inclusive).

Sample Input

8 5
2 3 1 2 3 2 3 3
0 3
4 6
6 7
3 5
0 7

Sample Output

Explanation

Below is the representation of the lane:

   |HIGHWAY|Lane|    ->    Width

0: |       |--|            2
1: |       |---|           3
2: |       |-|             1
3: |       |--|            2
4: |       |---|           3
5: |       |--|            2
6: |       |---|           3
7: |       |---|           3

(0, 3): Because width[2] = 1, only the bike can pass through it.
(4, 6): Here the largest allowed vehicle which can pass through the 5^th segment is the car and for the 4^th and 6^th segment it’s the truck. Hence the largest vehicle allowed in these segments is a car.
(6, 7): In this example, the vehicle enters at the 6^th segment and exits at the 7^th segment. Both segments allow even trucks to pass through them. Hence the answer is 3.
(3, 5): width[3] = width[5] = 2. While the 4^th segment allows the truck, the 3^rd and 5^th allow up to a car. So 2 will be the answer here.
(0, 7): The bike is the only vehicle which can pass through the 2^nd segment, which limits the strength of the whole lane to 1.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#define max 100000
using namespace std;

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int l,t,i,a,b,min,width[max];
    cin>>l>>t;
    for(i=0;i>width[i];
    while(t--){
        cin>>a>>b;
        min = 3;
        for(i=a;i<=b;i++)
        {
           if(width[i]<min)
               min=width[i];
        }
        cout<<min<<endl;
    }
    return 0;
}

Sherlock And Squares

Problem Statement

Watson gives two integers (A and B) to Sherlock and asks if he can count the number of square integers between A and B (both inclusive).

Note: A square integer is an integer which is the square of any integer. For example, 1, 4, 9, and 16 are some of the square integers as they are squares of 1, 2, 3, and 4, respectively.

Input Format
The first line contains T, the number of test cases. T test cases follow, each in a new line.
Each test case contains two space-separated integers denoting A and B.

Output Format
For each test case, print the required answer in a new line.

Constraints
1≤T≤100
1≤A≤B≤109

Sample Input

2
3 9
17 24

Sample output

2
0

Explanation
Test Case #00: In range [3,9], 4 and 9 are the two square numbers.
Test Case #01: In range [17,24], there are no square numbers.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    long int t,n1,n2;
    cin>>t;
    while(t--)
        {
        cin>>n1>>n2;
        cout<<floor(sqrt(n2))-ceil(sqrt(n1))+1<<endl;
    }
    return 0;
}

S	M	T	W	T	F	S
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

Day: August 29, 2015

Cut the sticks

Service Lane

Sherlock And Squares