How many followed the rules?

Computer Science Level 2

In a classroom, the teacher ordered the students to line up according to their heights from the shortest to the tallest.

However, some mischievous kids did not follow their teacher's order and lined up in a random order.

Given a list of integers, which are the heights of the kids in the order that they lined up, find the length of the longest queue that follows the teacher's order.

Example:

The queue = { 134 , 154 , 127 , 142 , 145 , 152 , 133 } \{134, 154, 127, 142, 145, 152, 133\}

The answer is 4 4 , as the longest queue that satisfies the instruction is 127 , 142 , 145 , 152 {127, 142, 145, 152}

Problem:

There are 36 36 students.

The queue

Details and Assumptions:

When two kids with the same height stand next to each other, they are considered as following the rule.


The answer is 6.

Daniel Lim by Daniel Lim , 21, Singapore

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Mbah Abal
Dec 28, 2015

Alhail, Bruteforce 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int array[]={135,145,123,140,129,112,116,119,122,131,142,132,137,125,138,108,129,126,116,117,124,132,137,152,124,128,139,116,111,127,106,131,123,137,115,141};
    int maks=0,count=1;

    for(int i=0;i<36;i++){
        if(array[i]<array[i+1]){
            count++;
        }
        else if(array[i]>array[i+1]){
            maks=max(maks,count);
            count=1; 
        }
    }
    cout<<maks<<endl;
}

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Daniel Lim
Sep 5, 2014

C++ 

 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
32
33
34
35
36
37
38
 
#include <iostream>
#include <vector>
using namespace std;

void longestQueue(vector <int> v) {

    int answer = 1;
    vector <int> answers(v.size());
    answers[0] = 1;
    for (int i = 1; i < v.size(); i++) {
        if (v[i] >= v[i - 1])
            answers[i] = answers[i - 1] + 1;
        else
            answers[i] = 1;

        if (answers[i] > answer)
            answer = answers[i];
    }

    cout << answer << endl;
}

int main() {

    int TC; cin >> TC;
    while (TC--) {
        int n; cin >> n;
        vector <int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
        }

        longestQueue(v);
    }

    system("pause");
    return 0;
}

Basically what this code does is for every element in the array it checks if it is bigger than the previous integer and if it is, in the answers array, store the previous value plus one, or else, store 1 in the answers array.

0 Helpful 0 Interesting 0 Brilliant 0 Confused

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...