10769 - Pillars

[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]

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.

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]

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]

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]

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]

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]

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]

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;
}