9도 OJ 1150: Counterfeit Dollar(가짜 달러)(분석, 검사)

시간 제한: 1초
메모리 제한: 32메가
특수 판제:아니오
제출: 485
해결: 215
제목 설명:
    Sally Jones has a dozen Voyageur silver dollars. However, only eleven of the coins are true silver dollars; one coin is counterfeit even though its color and size make it indistinguishable from the real silver dollars. The counterfeit coin has a different weight from the other coins but Sally does not know if it is heavier or lighter than the real coins.      Happily, Sally has a friend who loans her a very accurate balance scale. The friend will permit Sally three weighings to find the counterfeit coin. For instance, if Sally weighs two coins against each other and the scales balance then she knows these two coins are true. Now if Sally weighs one of the true coins against a third coin and the scales do not balance then Sally knows the third coin is counterfeit and she can tell whether it is light or heavy depending on whether the balance on which it is placed goes up or down, respectively.      By choosing her weighings carefully, Sally is able to ensure that she will find the counterfeit coin with exactly three weighings.
입력:
    For each case, the first line of input is an integer n (n > 0) specifying the number of cases to follow. Each case consists of three lines of input, one for each weighing. Sally has identified each of the coins with the letters A--L. Information on a weighing will be given by two strings of letters and then one of the words ``up'', ``down'', or ``even''. The first string of letters will represent the coins on the left balance; the second string, the coins on the right balance. (Sally will always place the same number of coins on the right balance as on the left balance.) The word in the third position will tell whether the right side of the balance goes up, down, or remains even.
출력:
    For each case, the output will identify the counterfeit coin by its letter and tell whether it is heavy or light. The solution will always be uniquely determined.
샘플 입력:
1
ABCD EFGH even 
ABCI EFJK up 
ABIJ EFGH even 

샘플 출력:
K is the counterfeit coin and it is light.

출처:
2010년 북경대학 컴퓨터 연구 생기 시험 진제
아이디어:
쉽게 말하면 동전 12개가 있고 1개는 가짜이며 무게는 다른 것과 다르지만 무거운지 가벼운지 알 수 없다.천평은 세 번만 찾으면 된다고 할 수 있다.
지금 세 번의 결과를 내서 그 하나가 가짜인지 무거운지 가벼운지 빌어라.
두 가지 방법이 있는데 하나는 분석이고 비교적 강한 논리가 필요하다.그리고 24가지 상황을 직접 검증에 대입하여 결과를 만족시키는 것이 답이라고 추천합니다.
내가 9도에서 AC 코드를 POJ에서 통과하지 못한 것은 반드시 천평 양쪽이 네 개의 동전이 되는 것은 아니기 때문이다.
코드 1은 9도의 C 코드이고 코드 2는 POJ의 C++ 코드입니다.
코드 1:
#include <stdio.h>
#include <string.h>
 
int c2i(char c)
{
    return c-'A';
}
 
char i2c(int i)
{
    return i+'A';
}
 
int trans(char s[])
{
    if (strcmp(s, "even") == 0)
        return 0;
    else if (strcmp(s, "up") == 0)
        return 1;
    else
        return -1;
}
 
int main(void)
{
    int i, j, k, r;
    int n, res[3];
    char s1[3][5], s2[3][5], s3[3][5];
 
    while (scanf("%d", &n) != EOF)
    {
        while (n--)
        {
            for (i=0; i<3; i++)
            {
                scanf("%s%s%s", s1[i], s2[i], s3[i]);
                res[i] = trans(s3[i]);
            }
            int flag = 0;;
            for (j=-1; j<=1; j+=2)
            {
                for (k=0; k<12; k++)
                {
                    for (i=0; i<3; i++)
                    {
                        int value = 0;
                        for (r=0; r<4; r++)
                        {
                            if (c2i(s1[i][r]) == k)
                                value = j;
                            if (c2i(s2[i][r]) == k)
                                value = -j;
                        }
                        if (value != res[i])
                            break;
                    }
                    if (i == 3)
                    {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 1)
                    break;
            }
            if (j == -1)
                printf("%c is the counterfeit coin and it is light.
", i2c(k)); else printf("%c is the counterfeit coin and it is heavy.
", i2c(k)); } } return 0; } /************************************************************** Problem: 1150 User: liangrx06 Language: C Result: Accepted Time:0 ms Memory:912 kb ****************************************************************/

코드 2:
#include <stdio.h>
#include <string.h>
 
int c2i(char c)
{
    return c-'A';
}
 
char i2c(int i)
{
    return i+'A';
}
 
int trans(char s[])
{
    if (strcmp(s, "even") == 0)
        return 0;
    else if (strcmp(s, "up") == 0)
        return 1;
    else
        return -1;
}
 
int main(void)
{
    int i, j, k, r;
    int n, res[3];
    char s1[3][5], s2[3][5], s3[3][5];
 
    while (scanf("%d", &n) != EOF)
    {
        while (n--)
        {
            for (i=0; i<3; i++)
            {
                scanf("%s%s%s", s1[i], s2[i], s3[i]);
                res[i] = trans(s3[i]);
            }
            int flag = 0;;
            for (j=-1; j<=1; j+=2)
            {
                for (k=0; k<12; k++)
                {
                    for (i=0; i<3; i++)
                    {
                        int value = 0;
                        for (r=0; r<4; r++)
                        {
                            if (c2i(s1[i][r]) == k)
                                value = j;
                            if (c2i(s2[i][r]) == k)
                                value = -j;
                        }
                        if (value != res[i])
                            break;
                    }
                    if (i == 3)
                    {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 1)
                    break;
            }
            if (j == -1)
                printf("%c is the counterfeit coin and it is light.
", i2c(k)); else printf("%c is the counterfeit coin and it is heavy.
", i2c(k)); } } return 0; } /************************************************************** Problem: 1150 User: liangrx06 Language: C Result: Accepted Time:0 ms Memory:912 kb ****************************************************************/

좋은 웹페이지 즐겨찾기