9도 OJ 1150: Counterfeit Dollar(가짜 달러)(분석, 검사)
메모리 제한: 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
****************************************************************/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
C 언어 체인 시계는 뱀을 탐식하는 작은 게임을 실현한다본고의 실례는 여러분에게 C 언어 체인표가 뱀 탐식 게임을 실현하는 구체적인 코드를 공유하여 참고하도록 하였으며, 구체적인 내용은 다음과 같다. 프로젝트 이름: 뱀놀이 운영 환경: Linux 프로그래밍 언어: C 언...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.