There are a N students in a high school class. For simplicity the students are named A, B, C, . . . (up to the Nth letter of the alphabet). No two students have exactly the same height. The Principal of the school wants to organize a class photograph where the students are arranged in descending order of heights. The class teacher has been asked to list the students in descending order of heights to send to the photographer. The teacher does not know the heights of the various students. However, there are a set of photographs, which between them have all the students in that class. From each of the photographs the teacher obtained a list of students in descending height order, and needs to combine them into one list of students in descending height order. It is possible that the photographs do not fully determine the ordering in the list. In this case, as it is vacation time, the teacher needs to write to some of the students to send her their exact height, so that she can create the complete list. The objective is to write a program that can list the students to whom she must write to determine their heights. Constraints N<=26, K<=10 Input Format Line 1 contains two comma separated positive integers, N and K. N gives the number of students in the class (A,B,C, . . .), and K is the number of photographs The next K lines each contain a comma separated list of the students in descending order from the corresponding photograph. Output Output should be one comma separated list (in alphabetical order) of students whose height must be known to create the ordered list. If it is not necessary to write to any student, the output should be N/A
Example 1 Input 8,3 D,C,E,F,G,H C,A,B,E D,B Output N/A Explanation N is 8 and K is 3, and so there are 8 students and 3 photographs. As the students are named the first N letters of the alphabet, the students are A, B, C, D, E, F, G, H. The first photograph shows the ordering as D, C, E, F, G, H, that is D is taller than C who is taller than E and so on. The second photograph shows that C is taller than A, who is taller than B who is taller than E. The third photograph shows that D is taller than B. From photograph 1, E, F, G and H are all shorter than C, and are in that order. From photograph 2, A and B are taller than E and in that order. Hence A, B, C and D are all taller than E, F, G and H. Hence the last four in the final ordered list must be E, F, G, H in that order. From the first photograph, D is taller than C, and from the second photograph, C is taller than A who is taller than B. Hence the order of the first four is D, C, A, B. The third photograph confirms this order. Hence the full list is D, C, A, B, E, F, G, H. The full order can be determined without writing to any student to get their height. Hence the output is N/A Example 2 Input 8,3 D,C,E,F,G,H C,A,E D,C,B,E Output A,B Explanation N is 8 and K is 3. The students are A, B, C, D, E, F, G, H (the first N letters of the alphabet) As before, from photographs 1, 2 and 3, we can determine that A, B, C and D are taller than E, F, G, H, and that E, F, G, H are the last four in the ordered list. From the first photograph, D is taller than C, and from the second photograph, C is taller than A. From the third photograph, C is taller than B. The possible orders of the first four could be D, C, A, B or D, C, B, A. No information is present in any of the photographs which says which order is correct. Hence the teacher must write to both B and A to determine their heights so as to establish the correct order. The output must be sorted in alphabetic order, and hence the output is A,B. sorry if i spoiled it for anyone who was actually trying to figure this out lol. yes i copy and pasted this still makes no sense. anyone care to elaborate? then again i didn't thoroughly read through everything.
Can the teacher not just arrange them by looking at them on the day of the photo instead of making pointless lists?
It makes sense but it’s hard to explain. The difference between the two examples is the students given per photograph. In example A there IS enough information given in each photograph that we can determine the entire order in which the students would be arranged by height therefore not needing to write any students. In the second example, there’s not enough information in the given photographs to determine if A or B is taller so the teacher must write A, B (the output). Question tho, are you supposed to add your own values for N, K, and the students shown on each photograph or? If not then I don’t have all the information. Also, what software are you using to write the program? We only ever used c++ and dreamweaver in school
I think I understand tho, but I don’t know how to explain. Ask me questions and I’ll see if I can answer
So I guess you just input your own values for N, K, and the photographs. And I made my own example to try and understand better (idk if this is right but ??♀️) Input: 10,5 C,J,H,I,G,A F,B,J,E,I B,J,G,A H,E,D,G C,F,B Output: N/A (because the order of height for all students is able to be determined from the photographs given) Sooooo then all you have to do is write the code to put the values in order and if I remember correctly from my classes six years ago that’s pretty simple to do. Lots of nested if() statements I would think ? or maybe they just taught us how to do it the long way to understand the code better idk