/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://acm.hdu.edu.cn/showproblem.php?pid=1482
Name : 1482 Counterfeit Dollar
Date : Sunday, January 22, 2012
Time Stage : 2 hours
Result:
5285719 2012-01-22 11:47:15 Accepted 1482
0MS 236K 2462 B
C++ pyy
Test Data :
Review :
不是什么难题,慢慢推敲一下就出来了。
首先,基本原理是,把全部倾斜的天平摆成一个方向,设为左低右高,
那么假币肯定在任意一边。设它在左边,则左边3组中必然都存在假币,
所以只要枚举左边所有倾斜组,得到共有的那个硬币,便是假币。如果左边
找不到所有组共有的硬币,则在右边找。
如果遇到平衡的天平,那么此天平两边的硬币都是真币,就可以在枚举的时候过滤
掉这些真币了,同时也要减少枚举的组数。比如示例中,有两组真币,那么只枚举
一组就行了。
//----------------------------------------------------------------------------*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std ;
#define INF (-1)
#define MAXN ('L'-'A'+2)
int evenCnt ;
int getsum (bool side[MAXN][3], bool even[MAXN])
{
int i, j, sum ;
for (i = 0 ; i < 12 ; ++i)
{
sum = 0 ;
if (even[i]) // 不枚举真币
continue ;
for (j = 0 ; j < 3 ; ++j)
sum += side[i][j] ;
if (sum == 3 - evenCnt) // 只枚举倾斜的天平
break ;
}
return i ;
}
int main ()
{
int i, j ;
int tcase, k, id ;
string a, b, c, lf, rh ;
char *pWei ;
bool even[MAXN], left[MAXN][3], right[MAXN][3] ;
while (scanf ("%d", &tcase) != EOF)
{
k = 0 ;
while (k++ < tcase)
{
MEM (even, 0) ;
MEM (left, 0) ;
MEM (right, 0) ;
evenCnt = 0 ;
for (i = 0 ; i < 3 ; ++i)
{
cin >> a >> b >> c ;
if (c[0] == 'e') // 记录真币
{
++evenCnt ;
for (j = 0 ; j < a.size() ; ++j)
{
even[a[j]-'A'] = true ;
}
for (j = 0 ; j < b.size() ; ++j)
{
even[b[j]-'A'] = true ;
}
continue ;
}
else if (c[0] == 'u')
lf = a, rh = b ;
else
lf = b, rh = a ;
for (j = 0 ; j < lf.size() ; ++j)
left[lf[j]-'A'][i] = true ;
for (j = 0 ; j < rh.size() ; ++j)
right[rh[j]-'A'][i] = true ;
}
id = getsum (left, even) ;
pWei = "heavy" ;
if (id == 12)
{
id = getsum (right, even) ;
pWei = "light" ;
}
printf ("%c is the counterfeit coin and it is %s.\n", id+'A', pWei) ;
}
}
return 0 ;
}
分享到:
相关推荐
杭电hdu acm资料所用杭电的acm题
杭州电子科技大学ACM培训课件 来自杭电ACM官方论坛 拿来和大家分享一下 想到有些朋友论坛积分不够 现在特地拿来免费供大家下载 希望对ACM初学者能够有所帮助
杭电acm培训课件 杭电acm培训课件 杭电acm培训课件 杭电acm培训课件
杭电ACMhdu1163
杭电ACM1005题源代码,AC了的程序,无问题……
acm 杭电 杭州电子科技大学 2386-2393 解题报告
杭电ACM分类杭电ACM分类杭电ACM分类杭电ACM分类
杭电 hdu acm 第1084题的解法,ac过了,是一位学长教我的.内有一些中文说明.
ACM杭电Problem 1002 C++程序 大数相加问题,注意输出的限制
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
acm杭电课件+博弈的一篇英文论文+背包九讲的论文
本人杭电amc和浙大acm做题ac代码集合
ACM刷题模式~进入状态~ 杭州电子科技大学OJ
lecture_01初识ACM lecture_02老少皆宜数学题 lecture_03大整数运算 lecture_04_1归纳与递推
ACM HDU题目分类,我自己总结的大概只有十来个吧
美国计算机协会(Association for Computing Machinery , 简称ACM)是一个世界性的计算机从业员专业组织,创立于1947年,是世界上第一个科学性及教育性计算机学会。ACM每年都出版大量计算机科学的专门期刊,并就每项...
acm的经典算法之动态规划,杭电课件,很好的
100道 acm C语言 hdu 解题报告
ACM 北大ACM 杭电ACM 试题分类
ACM杭电课件供热爱ACM的同学一次很好的课后练习