ECOO '17 R1 P4 - Almost Sorted

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 13.0s
Memory limit: 64M

Author:
Problem type

After the lecture on sorting, Diana's CS teacher has given the class a challenge: what's the most efficient way to sort the class list? Students are only allowed to sort by repeatedly swapping two names in the list, and the person who makes the fewest swaps wins.

Diana really wants to win, so she decides to do something sneaky. When showing the teacher her efficient sort, she will omit one of the names in the list, which will let her use fewer swaps. Using her tactical advantage, what is the fewest swaps she has to do?

Input Specifications

The input will contain 10 test cases. Each test case starts with an integer N (1 \le N \le 1\,000). The next N lines represent the class list, with one name on each line in capital letters. Names will be unique and only contain uppercase letters.

Output Specifications

For each test case, your program should output the minimum number of swaps Diana needs to sort the list using her trick.

Sample Input

3
SAM
DIANA
REBECCA
5
DEREK
MEGAN
BRIAN
BOB
DIANA

Sample Output

0
1

Note: Only 2 cases are shown in this sample.

Explanation

In the first example, removing SAM will leave the list sorted, so no swaps are required.

In the second example, Diana could omit MEGAN and then sort the list by swapping DEREK and BOB.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org


Comments


  • -4
    FMGTeamTwo  commented on May 8, 2017, 12:33 a.m.

    there are only 3 test cases, not the 10 described in the problem.


    • 3
      JohnWinter  commented on May 8, 2017, 5:17 p.m.

      The output is clipped, and so only 3 test case results out of the 10 are shown.