10769 - Pillars

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim »

Just for the record, the input file actually does not have a blank line between some cases and not extra blank lines.

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

Hi,
You're right. My problem was the handling of blank lines. My first approach was:
while( scanf("%ld",&h)==1){
. . .
and I got WA (however it worked on my computer!) .
Now I changed it to while(gets(we)!=NULL){ . . .
and I got AC. :lol:

Thanks for Your help.

Wojciech

By the way, could anybody explain why "while( scanf("%ld",&h)==1){" doesn't work properly on Judge system?
[/code]

w k
Learning poster
Posts: 74
Joined: Wed Apr 14, 2004 11:14 pm

Post by w k »

Once again,

Since the problem description says that " A blank line separate test cases". I think it should be corrected to " blank lines ".

Wojciech

Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by Carlos »

I've just checked judge's input and there are not blank lineS in the input (only one). Input specification looks ok, so if you want me to check you codes by hand send me them to:

problemset@acm.uva.es

Carlos
System administrator
Posts: 1286
Joined: Sat Oct 13, 2001 2:00 am
Location: Valladolid, Spain
Contact:

Post by Carlos »

at last I found the mistake, there was a blank line missing in the input file. I've added it, and you should get aC now. I'm rejudging every submission.

Thanks to Wojciech for his code.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

10769 - Want ot see another bad code?

Post by serur »

Well, fellows, this stuff passes all testcases suggested here, but WA...
I myself don't approve of posting bad source codes, but having this looked through by more experienced persons and listen what they say is more likely to lead to any success here...

Code: Select all

[i][//*"Pillars"*/
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define N 100
typedef unsigned long T;

T w[N],b[N];
T H;
int n,m;
int a[4];
int used_b[N],used_w[N];

int compare(const T *a,const T *b){
	return (*b-*a);
}

int F(T Total_Len, int k)
{
	int t;
	if(k==4 && Total_Len==H)
	{
		printf("%lu ",b[a[0]]);
		printf("%lu ",w[a[1]]);
		printf("%lu ",b[a[2]]);
		printf("%lu\n",w[a[3]]);
		return 1;
	}
	else if(k<4 && Total_Len<H)
	{
		k++;
		if(k%2==1)
		{
			for(t=0;t<n;t++)
				if(!used_b[t])
					if(Total_Len<H-b[t])
					{
						used_b[t]=1;
						a[k-1]=t;
						if(F(Total_Len+b[t],k))
							return 1;
						used_b[t]=0;
					}
		}
		else
		{
			for(t=0;t<m;t++)
				if(!used_w[t])
					if(Total_Len<=H-w[t])
					{
						used_w[t]=1;
						a[k-1]=t;
						if(F(Total_Len+w[t],k))
							return 1;
						used_w[t]=0;
					}
		}
	}
	return 0;
}

int main()
{
	int L,t;
	char buff[200000];
#ifndef ONLINE_JUDGE
	freopen("A.in","r",stdin);
#endif
	while(scanf("%lu\n",&H)!=EOF)
	{
		n=0;
		b[n]=0;
		gets(buff);
		L=strlen(buff),t=0;
		while(t<L)
		{
			while(t<L && isdigit(buff[t]))
				b[n]=10*b[n]+(buff[t++]-'0');
			while(t<L && !isdigit(buff[++t]));
			n++;
			b[n]=0;
		}
		m=0;
		w[m]=0;
		gets(buff);
		L=strlen(buff),t=0;
		while(t<L)
		{
			while(t<L && isdigit(buff[t]))
				w[m]=10*w[m]+(buff[t++]-'0');
			while(t<L && !isdigit(buff[++t]));
			m++;
			w[m]=0;
		}
		qsort(b,n,sizeof(T),compare);
		qsort(w,m,sizeof(T),compare);
		for(t=0;t<n;t++)
			used_b[t]=0;
		for(t=0;t<m;t++)
			used_w[t]=0;
		if(!F(0,0))
			printf("no solution\n");
	}
	return 0;
}


code][color=green][/color][/i]

dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan »

At first glance your code looks fine to me. The only input I can come up with, which your program would fail on, is one that contains pieces of 0 height. Such as:

Code: Select all

3
1 1
1 0

1
1 0
0 0
As I read the problem statement, the total height h is equal or greater to 1, but no such guarantee is made for the induvidual pieces.

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

Re: 10769 - Pillars

Post by shantanu18 »

I am getting TLE! maybe i don't have any problem with extra blank line. please give some IO

Code: Select all

#include <cstdio>
#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <utility>
#define pa pair<int,int>
#define white 10
#define black 11
#define red 0
#define green 1
using namespace std;
int n;

int arr[50];
bool gf;
bool com(pa a,pa b)
{
	return b.first<a.first;
}
void call_me(int node,int pos,int state,int n,vector <pa>B,vector <pa> W,int sum)
{
	if(gf) return;
	arr[pos]=node;
	if(pos==3)
	{
		if(sum!=n)return;
		for(int i=0;i<4;i++)
		{
			if(i==0) printf("%d",arr[i]);
			else printf(" %d",arr[i]); 
		}
		cout<<endl;
		gf=true;
		return;
	}
	if(state==black)
	{
		for(int i=0;i<(int)W.size();i++)
		{
			if(W[i].second==red && (sum + W[i].first<=n))
			{
				W[i].second=black;
				call_me(W[i].first,pos+1,white,n,B,W,sum + W[i].first);
				W[i].second=red;
			}
		}
	}
	else if(state==white)
	{
		for(int i=0;i<(int)B.size();i++)
		{
			if(B[i].second==red && (sum + B[i].first<=n))
			{
				B[i].second=black;
				call_me(B[i].first,pos+1,black,n,B,W,sum + B[i].first);
				B[i].second=red;
			}
		}
	}
}
int main()
{
	//freopen("10769.in","r",stdin);
	while(scanf("%d",&n)==1 && n)
	{
		vector <pa> B;
		vector <pa> W;
		getchar();
		string st="";
		getline(cin,st);
		stringstream ss(st);
		int num;
		while(ss>>num)
			B.push_back(pa(num,red));
		getline(cin,st);
		stringstream s(st);
		while(s>>num)
			W.push_back(pa(num,red));
		sort(B.begin(),B.end(),com);
		sort(W.begin(),W.end(),com);
		gf=false;
		if(B.empty() || W.empty()) {printf("no solution\n");continue;}
		for(int i=0;i<(int)B.size();i++)
		{
			if(gf)break;
			B[i].second=black;
			call_me(B[i].first,0,black,n,B,W,B[i].first);
			B[i].second=red;
		}
		if(!gf)
			printf("no solution\n");
	}
	return 0;
}

Post Reply

Return to “Volume 107 (10700-10799)”