北大poj- 1013
2024-09-23 03:59:10
Counterfeit Dollar
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 50515 | Accepted: 15808 |
Description
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.
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.
Input
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.
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.
Output
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.
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.
Sample Input
1
ABCD EFGH even
ABCI EFJK up
ABIJ EFGH even
Sample Output
K is the counterfeit coin and it is light.
Source
分析:
很有意思的题目,人脑很好处理,但是用计算机来做就有点不知如何下手了。
拿到题目,列出方程,各种约,就能得到答案,但是这种方法,用计算机不好实现。后来突然想到,可以用“嫌疑人”的方法来做。
解题:
已知条件:1、只有一枚假币;2、假币可重可轻;3、一定可以根据已知的3次测量来判断出假币。
给每个硬币设置2个属性:1)是否为真;2)可疑度。
解题步骤:
先遍历所有even的case,设置even场景下的硬币都为真。
再遍历剩余的case,
当为up的时候,除去已知为真的硬币,对左硬币可疑度+1,对右硬币可疑度-1。
当为down的时候,除去已知为真的硬币,对右硬币可疑度+1,对左硬币可疑度-1。
结束后,
查找硬币中,可疑度绝对值最大的硬币,就是假币了。当可疑度为正,那么假币重;当可疑度为负,那么假币轻。
PPS:话说poj为啥会挂了呢。。。
#include <stdio.h>
#include <string.h>
#include <stdlib.h> #define TRUE (int)1
#define FALSE (int)0 #define CASE_NUM 3
#define MAX_COIN_NUM 12 typedef int BOOL; typedef struct
{
int strLen;
char str1[MAX_COIN_NUM+];
char str2[MAX_COIN_NUM+];
char delta[];
}WeightCase; WeightCase g_case[CASE_NUM];
BOOL g_isEvenCoin[MAX_COIN_NUM];
char g_coin[MAX_COIN_NUM]; const char up[] = "up\0";
const char down[] = "down\0";
const char even[] = "even\0"; void Input()
{
int i = ;
for(i = ; i < CASE_NUM; i++)
{
scanf(" %s", g_case[i].str1);
scanf(" %s", g_case[i].str2);
scanf(" %s", g_case[i].delta);
g_case[i].strLen = strlen(g_case[i].str1);
}
} void ProcEvenCase()
{
int i, j; for(i = ; i < CASE_NUM; i++)
{
if( != strcmp(g_case[i].delta, even)) continue; for(j = ; j < g_case[i].strLen; j++)
{
g_isEvenCoin[g_case[i].str1[j] - 'A'] = TRUE;
g_isEvenCoin[g_case[i].str2[j] - 'A'] = TRUE;
}
}
} void ProcOtherCase()
{
int i, j, delta; for(i = ; i < CASE_NUM; i++)
{
if( == strcmp(g_case[i].delta, even)) continue; if( == strcmp(g_case[i].delta, up))
delta = ;
else
delta = -; for(j = ; j < g_case[i].strLen; j++)
{
if(!g_isEvenCoin[g_case[i].str1[j] - 'A']) g_coin[g_case[i].str1[j] - 'A'] += delta;
if(!g_isEvenCoin[g_case[i].str2[j] - 'A']) g_coin[g_case[i].str2[j] - 'A'] -= delta;
}
}
} void Proc()
{
memset(g_coin, , sizeof(g_coin));
memset(g_isEvenCoin, FALSE, sizeof(g_isEvenCoin)); ProcEvenCase();
ProcOtherCase();
} void Output()
{
int i, tmp, pos = , max = ;
char coin;
for(i = ; i < sizeof(g_coin); i++)
{
tmp = abs(g_coin[i]);
if(tmp > max)
{
max = tmp;
pos = i;
}
}
coin = pos+'A'; if(g_coin[pos] < )
printf("%c is the counterfeit coin and it is light.\n", coin);
else
printf("%c is the counterfeit coin and it is heavy.\n", coin);
} int main()
{
int num = ;
scanf("%d", &num);
while(num--)
{
Input();
Proc();
Output();
} return ;
}
最新文章
- css3 背景渐变
- 2013 duilib入门简明教程 -- 结合win32和MFC (16)
- python 汇总
- 高清VGA编码器|上海视涛科技
- iOS开发资源整理【01】
- 【海岛帝国系列赛】No.4 海岛帝国:LYF的太空运输站
- Struts2 Annotation 注解配置
- 妙味课堂——HTML+CSS(第一课)
- hdu1106 字符串水题strtok()&;&;strchr()&;&;sscanf()+atoi()使用
- CentOS 6.5(64bit)安装GCC4.8.2+Qt5.2.1(替换GCC的链接库)
- 每天一个JavaScript实例-递归实现反转数组字符串
- 汇编指令-MOV与ldr区别(7)
- vmware workstation安装教程以及其中出现的错误解决方法
- 【mybatis】mybatis中 <;if test=>;等于的条件怎么写
- hibernate坑边闲话
- IIS添加Expires头
- 算法之LOWB三人组之冒泡排序
- [.NET] GC垃圾回收机制
- 01背包入门 dp
- 第二十四篇configparser(**)