Problem H
The Most Wanded Man In The History of Mankind
Input: Spot.in
Output: Standard Output
There is a search around the world for the most wanted man (MWM) in the history of mankind. He is believed to have an extraordinary quality, either superior or inferior, compared to a normal person. He is likely to be present any where in the world. If he is spotted precisely then he may be captured without much difficulty. However the problem is in spotting him because a number of look-alikes are known to exist at different parts of the world.
Apart from conventional resources, modern satellite communication and surveillance systems that can precisely identify, measure, record and monitor the physical, social, cultural and behavioral characteristics of a person, are available for collecting data on the MWM. In addition, the services of competent Professionals in Different Disciplines Are Available To Analyze and Interpret Data Collected from All Sources.
Professional Psychologists and Statisticians admit that it is difficult for them to distinguish precisely between two persons using physical and behavioral data. However, by analyzing and interpreting group data, they claim that they can differentiate precisely between a group of normal persons and a similar group of same size that includes a person of extraordinary quality even if it is not known in advance whether the extraordinary quality is superior or inferior to that of a normal person. in such a case for a reliable comparison it is necessary that the number of persons in each Group is 3 or more.
In other words, let A, B be two groups of equal number of persons, the number being 3 or more. An unidentified person x having an extraordinary quality classified either superior or inferior, may or may not be present in any of the groups. IT is Possible to Perform A Special Compare ON A, B And State Prepisely by Data Analysis and Interpretation, One of the Following: (A) A = B INDICATING X IS NEITHER IN A NOR IN B,
(b) a> b indeicating eachier ie in a and he is inferior,
.
The Outcome of the Special Compare Operation May Be Denoted by E, H AND L Repensenting The Cases (a), (b) and (c) respectively.
Since collection, analysis and interpretation of data are considered costly and the total number n of look-alikes including the MWM is small, 8 £ n £ 12, it is decided that only three special compare operations on selected groups could be performed successively to spot the MWM and determine his qualitative characteristic. However it is required to select groups Ai, Bi, i = 1,2,3, before each special compare operation. The groups may depend on the outcome of the previous special compare operations.
Write a program that selects the groups to be compared by the professionals in three stages. For each stage, you may assume that the outcomes of special compare operations are known for all previous stages. After selection of groups the program should spot the MWM when successive Outcomes of Special Compare Operations Are Known.
INPUT
The Input May Contain Multiple Test Case.
The Data for A Test Case Are Given in a Single Line. The Line Contains Two Integers, The Case Number C and The Total Number N of Look-Alikes, 8 £ N £ 12. It Also Contains A String S of Three Letters S1, s2, s3 representing the successive outcomes of three special compare operations to be used by your program to form the groups for comparison and to spot the MWM.The look-alikes, including the MWM w, are identified by integers 1, 2, ... n And Each of the Outcomes S1, S2, S3 of the Special Compare Operations I. H or L. The ith letters e, h or l. the ith letters e, h or l. the ith letters, i = 1, 2, 3.
The Entire Input Set Terminates with an input 0 for c.
OUTPUT
For Each Test Case In The Input, Print Four Lines.
The First Line Contains The Input Data, Viz., C, N, S, TOGETHER WITH ANTEger W That Identifies His Quality. IF MWM IS Spotted Then 1 £ W £ N And The Letter Q IS either s or i depending on whether the quality of MWM is identified as superior or inferior. If MWM is not among the look-alikes then w is equal to zero and the letter q is equal to m, representing 'MWM missing'. In case The Comparisons Reveal That The Claims of The Professionals Are Faulty, THEN W Is Equal to -1 and q IS Equal To f Representing 'Faulty Comparisons and Claims Are Not Tenable'.
The next Three Lines Contain Ai, Si, Bi, i = 1, 2, 3 WHERE AI, BI Are The Groups for Comparison At the Ith Stage and Si I '' s Given Outcome of The Special Compare Operation.
Print A Blank Line Between Outputs of Two Test Cases.
Sample Input
1 8 hhh
2 8 hhe
3 8 hhl
4 8 HEH
5 8 Hee
6 8 HEL
7 8 hlh
8 8 Eee
0
Sample Output
1 8 hhh 1 s
1 2 3 H 4 5 6
1 4 7 H 2 5 8
1 5 6 H 2 7 8
2 8 hhe
-1 f
1 2 3 H 4 5 6
1 4 7 H 2 5 8
1 5 6 E 2 7 8
3 8 HHL 5 I
1 2 3 H 4 5 6
1 4 7 H 2 5 8
1 5
6 L
2 7 8
4 8 HEH
-1 f
1 2 3 H 4 5 6
1 4 7 E 2 5 8
1 5 6 H 2 7 8
5 8 Hee 3 S
1 2 3 H 4 5 6
1 4 7 E 2 5 8
1 5 6 E 2 7 8
6 8 HEL 6 I
1 2 3 H 4 5 6
1 4 7 E 2 5 8
1 5
6 L
2 7 8
7 8 hlh
-1 f
1 2 3 H 4 5 6
1 4
7 L
2 5 8
1 5 6 H 2 7 8
8 8 Eee
0 m
1 2 3 E 4 5 6
1 4 7 E 2 5 8
1 5 6 E 2 7 8
// Author iplinger // IDE VC // Data 2004.10.11 // Note This topic is similar to the classic title. The key to this question is to build a group, how the packets can be called different ///////, and indicate that it is lightweight. We can give this grouping for the grouping of 8. So 9 of the packet of 1, 2, 3-4, 5, 6 1, 4, 7-2, 5, 8 1, 5, 6-2, 7, 9 //10 is 1, 2, The packets of 3, 4-5, 6, 7, 8 1, 6, 7, 9-2, 5, 8, 10 1, 3, 5, 7-2, 4, 6, 9//11 are 1, 2, 3, 4-5, 6, 7, 8 1, 6, 7, 9-2, 5, 10, 11 1, 5, 9, 10-2, 6, 3, 8 // 12] 1, 2, 3, 4-5, 6, 7, 8 1, 6, 7, 9-2, 5, 10, 11 3, 8, 9, 10-2, 5, 6, 12 // Another difficult point How to use the program to find MWM, which is a bad ball. My approach is this: first set up 3 arrays, super, infer, except // If it is 'e', put the comparison two groups into except; // If it is two types of 'h' Situation, if the previous group of 'h' or 'L' is compared, the previous group of the two groups is placed in the super SUPER, and all the values of the previous group are // directly into Super. If it is two cases of 'L', if the previous one of 'h' or 'L' is compared, the previous group of the two groups is put into the infer, and there is no direct set of // all The value is placed in Infer. Finally, the two arrays of Super and Infer will cut the value in Except. // Result: If 'h' or 'L' has never appeared, there is no MWM; // If 'h' or 'L' appears, the ultimate Superm and Inferm have been faded. Then there is a contradiction; // If there is no contradiction, the group according to our division will definitely find MWM, and the only one.
#pragma hdrstop # include Static Group Group9 (9, 3, GroupValue9); Static Group Group10 (10, 4, groupvalue10); Static Group Group11 (11, 4, groupvalue11); Static Group Group12 (12, 4, groupvalue12); //// function: It is judged whether or not there is a value to be detected in an array. // Parameter: // Value: Test value // array []: to detect an array // arlength: array length BOOL ISHAVED (int value, int arch) {for (int i = 0; i < Arlesngth; i ) {IF (array [i] == value) return true;} Return False;} // function: Insert a value into an array, replace the given value. // Parameter: // value: To insert value // array []: Array to be inserted // arLength: Array length // ReplaceDValue: To replace the value, see this value override, then insert the end to return TRUE. If this value is not, false // Note: Inserting the random group is not sorted, just replacing the first replacement value from the head. Bool INSERTVALTOAR (Int Value, Int Array "{for (INT i = 0; i Equal InsertArToArbool MergeAr (int ar [], int insertedAr [], int arLength, int insertedArLength, int replacedValue) {if (insertedArLength // Parameter: // ar []: Take an empty array // arlength: Take an empty array length // ReplaceValue: Replace VOID CLEARARRAY (int Ar [], int ArLength, int replaceValue) {for (int i = 0; I Void Comparel (INT I, Group CGROUP) {updateewhenhorl (cgroup.group [i * 2], cgroup.group [i * 2 1], cgroup.numofog); if (! horl) {// cout << "INTO ! horl "<< Endl; Insertartoar (cgroup.group [i * 2], inferm, cgroup.numofog, maxlengthofgroup, 0); Insertartoar (cgroup.group [i * 2 1], superm, cgroup.numofog, maxlengthofgroup, 0); horl = true; // debugprintsuPandInf ();} else {// cout << "@ inor" << Endl; UpdateInsamea (INFERM, CGROUP.GROUP, CGROUP.NUMOFOG); UpdateInSamea (Superm, cgroup.group [i * 2 1], maxlengthofgrow, cgroup.numofog); // debugprintsUpandInf ();}} // Result printing void ResultPrint (Group cgroup) {int resultID; char resultcode; cout << CaseNum << "" << Totalnum << "<< Operation [0] << Operation [1] << Operation [2] <<"; if (! HORL) // If there is never appeared, 'h' or ' L 'is not MWM {resultID = 0; resultCode =' m ';} else if (IsEmptyAr (superM, maxLengthOfGroup, 0) && IsEmptyAr (inferM, maxLengthOfGroup, 0)) // if there is too' H 'or' L ' And eventually Superm and Inferm were faded. Then explain the contradiction. {Resultid = -1; resultcode = 'f';} else if (! ISemptyar (superm, maxlengthofgrow, 0)) // If there is no contradiction, according to our group, you can find MWM, and unique {for (int i) = 0; i DebugprintsUpandInf (); * / resultprint (cgroup);} // Select which case to group Void selectGroup () {Switch (TotalNum) {Case 8: Compare (Group8); Break; Case 9: Compare (Group9); BREAK Case 10: Compare (Group10); Break; Case 11: Compare (Group11); Break; Case 12: Compare (Group12); Break;}} // Read file void readfile () {ifstream OpenFile ("spot.in "); // Open the file, pay attention to if you use Kylix, you need to write a complete path value OpenFile >> CaseNum; while (! Openfile.eof () && codeum! = 0) // EOF () function is used to determine the end of the file. , Specify # {// cout << "casenum =" << Casenum << Endl; OpenFile >> TotalNum; OpenFile >> = = = o o]; / / You can't use OpenFile.Get (Operation [i]), because the GET (CH) function does not ignore spaces, causing Operatio [1] = '' // cout << "TotalNum =" << TotalNum << Endl ; // cout << "Operation =" << Operation [0] << Operation [1] << Operation [2] << endl; selectgroup (); openfile >> CaseNum; // Close file resources} void main () {readfile (); // char A; // cin >> a;
