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

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

Post by shamim » Wed Nov 10, 2004 2:40 pm

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 » Wed Nov 10, 2004 9:27 pm

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 » Wed Nov 10, 2004 9:30 pm

Once again,

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

Wojciech

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

Post by Carlos » Tue Nov 16, 2004 8:22 pm

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

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

Post by Carlos » Thu Nov 18, 2004 2:26 am

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 » Thu Apr 20, 2006 8:07 pm

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]

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

Post by dumb dan » Mon May 22, 2006 6:42 pm

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 » Sun Sep 05, 2010 7:08 pm

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)”