HELP NEEDED! :)

[nathan_drake]

Nothing bothers Bob more than when taller people stand up in front and block his view at sporting events. It
bothers him so much, that he has developed a measure for the displeasure that a crowd feels because of this
phenomenon. Most days, he calls his measure the Index of Identifiable Inversions. Although when his view is
blocked by this phenomenon, he calls it the "Down In Front" Aggravation Metric.
The measure works as follows. In a line of standing people, the measure is equal to the number of people who are
blocking others' views. Person A is blocking B's view, if
# A is taller than B
# A is standing in front of B
Assuming that everyone is standing, the line below has a "Down in Front" Aggravation Measure of 8. Bob's view is
blocked by Alice; Chuck's view is blocked by Bob and Alice; Dave's view is blocked by Chuck, Bob and Alice; and
Eve's view is blocked by Alice and Bob.

Input
The input consists of an initial line with an integer n, 0  n < 10,000 on a line by itself representing the number of
people standing in line. The rest of the lines give the line configuration, starting at the front of the line and going
in order, in the following format:
Feet Inches
Where

Feet is a integer from 0 to 8, inclusive, that indicates the feet portion of a person's height.

Inches is an integer between 0 and 11, inclusive, that represents the inches portion of a person's height.

Output
The output of the program should be a single integer representing the Index of Indentifiable Inversions of the
configuration.
Sample Input
5
5 10
5 9
5 8
5 6
5 8
Sample Output
8

Can someone help me on how to approach this program? I'm really lost. Any help is appreciated.

[Bob]

Hi Nathan Drake,

You know what format input to expect, that's pretty well defined for you, so why not figure out how you intend to store it, then how you're going to read it in. That will get you started, at least.

[myk45]

Can someone help me on how to approach this program? I'm really lost. Any help is appreciated.

have you tried giving it a shot? Anything at all? If yes, please post it here. If not, here are some thoughts that might help solve it. We can think of an optimal solution after we have found a solution. Here we go.

We need two main things.

1) To check condition "A is taller than B".
2) Some way to represent "A is standing in front of B"

For (1), a simple if condition would do.
For (2), try using an array to denote position. So, read your input into an array, say lineHeights[]. Now, if (lineHeights[0] > lineHeights[1]) is true, then it means person at positon 0 is taller than person at position 1, thereby blocking 1's view.

Now, lets use a nested for, do the following:

loop1 from 0 to n
  loop2 from loop1 + 1 to n
    if (arr[loop1] > arr[loop2])
      then increment counter.
    end if  
  end loop2
end loop1  

Optimizing this can be seen later. Hope this helps for a start.

[iamthwee]

Sounds like a question from the olympiad.

[nathan_drake]

Thanks a lot for your help, guys! This is what I have come up with so far, but it is not right. Can anybody help me where I'm wrong?

#include <iostream>
using namespace std;

int main ()
{
    int count = 0, i, n;
    int heights [10000];
    int feet, inches;

    cin >> n;

    while (n > 0 && n <= 10000)
    {
    for (i=0; i<n; i++)
    {
        cin >> feet>> inches;

        heights[i] = feet * 12 + inches;
    }

    for (i=0; i<n; i++)
    {
        for (int j=i+1; j<n; j++)
        {
            if (heights[i] > heights[j])
                count++;
        }
    }
    cout << count;
    }
    return 0;
}

[myk45]

Hi,

I tried with the sample input in the question. It seems to work.

[Ladis]

Actually, I think you have to replace the While LOOP with the IF conditional statement.
By using the while loop, your program will continue on and on....

Nice Program by the way