c语言Problem 1_03_guess

一道题目，原题完整叙述如下：

Description

A competition was just over. It had 3 problems and n players. Eachplayer had an ID number from 1 to n. The ?nal rank wasdecided by the total score of the 3 problems. The higher the total score was,the higher a player ranked (the smaller the rank number). If two players gotthe same total score, the one with the smaller ID number got a higher rank.We've known for each problem, how much score each player might get if he didn'tsolve totally wrong (if solved totally wrong, the player got zero in theproblem). However, we don’t know whether a player did get score in a problem.For a predicted ?nal rank, you need to judge if the rank is possible.

Input

Input contains several cases. For each case, the ?rst line is an integer n, (n <= 16384) to indicate the number ofplayers, followed by n lines, the ith of which contains three real numbers a,b, c (0<=a, b, c < 1000. a, b and c have 2 decimal places at most.) torespectively indicate the score of each problem Player i might get if he didn’tsolve totally wrong. Another line containing n integers follows to indicate theplayer ID number in the order from rank 1st to rank nth .

The last caseis followed by a line containing only a zero.

Output

No solution" (quotes for clarity).

Sample Input

3

100 200 300

100 200 300

100 200 300

1 2 3

3

100 200 300

100 200 300

100 200 300

3 2 1

0

Sample Output

Case 1: 600.00

Case 2: 400.00

这道题的来源是：ACM Beijing 2006-E

自己写了代码，提交以后AC了，代码如下：

1. #include <stdio.h> 2. #include <stdlib.h> 3. 4. #define PROBLEM_NUM 3 5. 6. int main () 7. { 8. int n = 0; // number of players 9. float** grades = NULL; // possible grades if not totally wrong 10. float results[1000]; 11. int* rank = NULL; // predicted rankings 12. float grade = 0, temp = 0, temp1 = 0; 13. int m = 0; // case counter: case m 14. int i = 0, j = 0, k = 0; // loop counter 15. 16. scanf("%d", &n); 17. while (n) { 18. rank = (int*)malloc(sizeof(int) * n); 19. grades = (float**)malloc(sizeof(float*) * n); 20. for (i = 0; i < n; i++) 21. grades[i] = (float*)malloc(sizeof(float) * PROBLEM_NUM); 22. 23. // get input 24. for (i = 0; i < n; i++) 25. for (j = 0; j < PROBLEM_NUM; j++) { 26. scanf("%f", &temp); 27. getchar(); // get rid of white spaces 28. /* Insertion Sort */ 29. for (k = j; k > 0 && temp < grades[i][k]; k--) 30. grades[i][k] = grades[i][k-1]; 31. grades[i][k] = temp; 32. } 33. 34. for (i = 0; i < n; getchar(), i++) 35. scanf("%d", &rank[i]); 36. 37. // judge the rank and find the score 38. grade = grades[rank[0]-1][0] + grades[rank[0]-1][1] + grades[rank[0]-1][2]; 39. temp = 0; 40. for (i = 1; i < n; i++) { 41. if (rank[i] > rank[i-1]) { 42. for (j = 0; j < 8 && temp <= grade; j++) { 43. switch (j) { // value of "temp" increases with "j" 44. case 0: temp = 0; break; 45. case 1: temp = grades[i][0]; break; 46. case 2: temp = grades[i][1]; break; 47. case 3: 48. temp = grades[i][0] + grades[i][1] >= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 49. break; 50. case 4: 51. temp = grades[i][0] + grades[i][1] <= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 52. break; 53. case 5: temp = grades[i][0] + grades[i][2]; break; 54. case 6: temp = grades[i][1] + grades[i][2]; break; 55. case 7: temp = grades[i][0] + grades[i][1] + grades[i][2]; break; 56. default: break; 57. } 58. temp1 = temp <= grade ? temp : temp1; 59. } 60. } 61. else { 62. for (j = 0; j < 8 && temp < grade; j++) { 63. switch (j) { // value of "temp" increases with "j" 64. case 0: temp = 0; break; 65. case 1: temp = grades[i][0]; break; 66. case 2: temp = grades[i][1]; break; 67. case 3: 68. temp = grades[i][0] + grades[i][1] >= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 69. break; 70. case 4: 71. temp = grades[i][0] + grades[i][1] <= grades[i][2] ? grades[i][2] : grades[i][0] + grades[i][1]; 72. break; 73. case 5: temp = grades[i][0] + grades[i][2]; break; 74. case 6: temp = grades[i][1] + grades[i][2]; break; 75. case 7: temp = grades[i][0] + grades[i][1] + grades[i][2]; break; 76. default: break; 77. } 78. temp1 = temp < grade ? temp : temp1; 79. } 80. } 81. 82. if (j == 1) break; 83. 84. grade = temp1; 85. temp = temp1 = 0; 86. } 87. if (i==n && j!= 1) 88. results[m] = grade; 89. else 90. results[m] = -1; 91. m ++; 92. 93. // release storage 94. for (i = 0; i < n; i++) 95. free(grades[i]); 96. free(grades); 97. free(rank); 98. 99. scanf("%d", &n); // player number of next case 100. } 101. 102. for (i = 0; i < m; i++) { 103. if (results[i] != -1) 104. printf("Case %d: %.2f\n", i, results[i]); 105. else 106. printf("Case %d: No solution\n"); 107. } 108. //free(results); 109. 110. return 0; 111. }

补充：软件开发 , C语言 ,

上一个：SQL注射辅助工具的编写
下一个：c语言Problem 1_03_guess