Counterfeit Dollar 1013 pku

Description：

http://acm.pku.edu.cn/JudgeOnline/problem?id=1013

有12枚硬币，11枚硬币是正常的，1枚是假的，可能轻也可能重，Sally通过三次称能够找出假的而且能够找出其轻重

通过枚举每一枚的轻重看其是否符合，可以通过even剪枝一些情况

Solution：

1 #include < stdio.h >

2 #include < string .h >

3

4   #define CHARSIZE 16

5

6 char left[ 4 ][CHARSIZE],right[ 4 ][CHARSIZE],type[ 4 ][CHARSIZE];

7

8 int Check( int p, int flag)

9 {

10 int i = 0 ,j = 0 ,leftSum = 0 ,rightSum = 0 ;

11 for (i = 0 ; i < 3 ; i ++ )

12 {

13 leftSum = 0 ;

14 rightSum = 0 ;

15 for (j = 0 ;left[i][j] && right[i][j];j ++ )

16 {

17 if (p + ' A ' == left[i][j])

18 leftSum += flag;

19 else

20 leftSum += 2 ;

21

22 if (p + ' A ' == right[i][j])

23 rightSum += flag;

24 else

25 rightSum += 2 ;

26 }

27 if (leftSum == rightSum && strcmp(type[i], " even " ))

28 return 0 ;

29 if (leftSum < rightSum && strcmp(type[i], " down " ))

30 return 0 ;

31 if (leftSum > rightSum && strcmp(type[i], " up " ))

32 return 0 ;

33 }

34

35 return 1 ;

36 }

37

38 int main ()

39 {

40 const int len = 12 ;

41 int testcase = 0 ,i = 0 ,j = 0 ;

42 int mark[len];

43

44 scanf ( " %d " , & testcase);

45

46 while (testcase -- )

47 {

48 memset(( void * )mark, 0 , sizeof (mark));

49 for (i = 0 ; i < 3 ; i ++ )

50 {

51 scanf ( " %s %s %s " ,left[i],right[i],type[i]);

52 if (strcmp(type[i], " even " ) == 0 )

53 {

54 for (j = 0 ; left[i][j] && right[i][j]; j ++ )

55 {

56 mark[left[i][j] - ' A ' ] = 2 ;

57 mark[right[i][j] - ' A ' ] = 2 ;

58 }

59 }

60 }

61

62 for (i = 0 ; i < len; i ++ )

63 {

64 if (mark[i] == 2 )

65 continue ;

66

67 mark[i] = 1 ;

68 if (Check(i, 1 ))

69 {

70 printf ( " %c is the counterfeit coin and it is light.\n " ,i + ' A ' );

71 break ;

72 }

73 if (Check(i, 3 ))

74 {

75 printf ( " %c is the counterfeit coin and it is heavy.\n " ,i + ' A ' );

76 break ;

77 }

78 }

79 }

80

81 return 0 ;

82 }

转载于:https://www.cnblogs.com/eavn/archive/2010/06/07/1753050.html