Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

我写的除了1000题以外,第一个0ms的代码!好高兴……

Posted by 1200017623 at 2012-12-27 17:25:36 on Problem 1029
//POJ 1029 False Coin

#include<iostream>
using namespace std;
struct Message{
	int CoinNum;
	int left[500];       //1000 coin most, so 500 max on each pan
	int right[500];
	int balance;         //left pan!
};

int judge(int coin,int wei,Message& mes){
	int i;
	for(i = 0;i < mes.CoinNum;++i){
		if(mes.left[i] == coin){
			if(wei != mes.balance)return 0;
			return 1;
		}
		if(mes.right[i] == coin){
			if(wei != -mes.balance)return 0;
			return 1;
		}
	}
	if(mes.balance)return 0;
	return 1;
}

int main(){
	int num,weight,i,j,flag;
	int valid = 0,status = 0,coin,we;
	char c;
	Message m[100];
	scanf("%d%d",&num,&weight);
	for(i = 0;i < weight;++i){
		scanf("%d",&m[i].CoinNum);
		for(j = 0;j < m[i].CoinNum;++j){
			scanf("%d",&m[i].left[j]);
		}
		for(j = 0;j < m[i].CoinNum;++j){
			scanf("%d",&m[i].right[j]);
		}
		getchar();  //blank
		c = getchar();
		if(c == '>')m[i].balance = 1;
		else if(c == '<')m[i].balance = -1;
		else if(c == '=')m[i].balance = 0;
	}
	for(i = 1;i <= 2 * num;++i){  //We must check for every possibility
		flag = 1;
		we = -1 + 2 * (i%2);     //1 for heavy -1 for light
		coin = (i + 1)/2;
		for(j = 0;j < weight;++j){
			if(judge(coin,we,m[j]) == 0){
//下面这一行是调试用的,提交时没有这行
				printf("%d %d Wrong\n",coin,we);
//
				flag = 0;
				break;
			}
		}
		if(flag){
			++valid;
			/* Important! Even if we can't figure out whether the
			   false cion is heavier or lighter, we can still give answers*/
			if(valid > 1 && coin != status){   
				printf("0\n");
				return 0;
			}
			status = coin;
		}
	}
	if(valid)printf("%d\n",status);
	else printf("0\n");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator