10344 - 23 out of 5

[Abednego]

Ah! That's better. I missed the email with the new judgement.

[Zaspire]

Help Please a don't known why WA?

Code: Select all

#include <stdio.h>

int store[5],col;
bool use[5];

bool need(int j)
{
	if (col==1)
	{
		for (int i=0;i<5;i++)
			if (use[i])
				if (store[i]==j) return true;
				else
					return false;
	}
	else
	{
		col--;
		for (int i=0;i<5;i++)
			if (use[i])
			{
				use[i]=false;
/*+*/			if (need(j-store[i])) return true;
/*-*/			if (need(j+store[i])) return true;
/***/			if (j%store[i]==0) 
				{
					if (need(j/store[i])) return true;
					if (need(-j/store[i])) return true;
				}
				use[i]=true;
			}
		col++;
		return false;
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	int i;
	bool res;
	scanf("%d %d %d %d %d",&store[0],&store[1],&store[2],&store[3],&store[4]);
	while ((store[0]!=0)||(store[1]!=0)||(store[2]!=0)||(store[3]!=0)||(store[4]!=0))
	{
		for (i=0;i<5;i++)
			use[i]=true;
		col=4;
		res=false;
		for (i=0;i<5;i++)
		{
			use[i]=false;
			if (need(23-store[i])) {res=true;break;}
			if (need(23+store[i])) {res=true;break;}
			use[i]=true;
		}
		if (res) puts("Possible");
		else puts("Impossible");
		scanf("%d %d %d %d %d",&store[0],&store[1],&store[2],&store[3],&store[4]);
	}
	return 0;
}

[898989]

Pleasee, i need some help, i do not know the problem
my code give time limit,, and this is starnge, i try many input, i found it very fast, i do not........If any one can help.

Code: Select all

#include <iostream>
//#include <fstream>
#include <string>
#include <vector>
using namespace std;

const int MAX = 9721;	//!120 * 3^4 //All combinations

int used[5] = {0}, op[5], combs[MAX][9];
int _operator[3] = {'+', '-', '*'};
int count;

int calc(int op1, int opertor, int op2)
{
	if(opertor == '+')		return (op1 + op2);
	
	if(opertor == '-')		return (op1 - op2);
	
	if(opertor == '*')		return (op1 * op2);
	
	return -1;	//Can not be reached
}

bool foundSeq(int a[9])
{	
	int total;
	//1 2 3 4 5 =>(((1*2)+4)*3)+5 =((2+4)*3)+5 =(6*3)+5 = 18+5 = 23
	total = calc(op[a[0]],  _operator[a[1]], op[a[2]]);
	
	total = calc(total, _operator[a[3]], op[a[4]]);
	
	total = calc(total, _operator[a[5]], op[a[6]]);
	
	total = calc(total, _operator[a[7]], op[a[8]]);

	return (total == 23 || total == -23);
}

void generate(int len, int result[9])
{
	int i;
	if(len == 9) //5 operands + 4 operators (repeated)
	{
		for(i=0; i<9;i++)
			combs[count][i] = result[i];	//Save
		count++;
	}
	
	else if(len%2 == 0)			//We must set operands
	{
		for(i=0;i<5;i++)
		{
			if(used[i] == 0)	//Only use once in a Seq
			{
				result[len] = i;
				used[i] = 1;
				generate(len+1, result);
				used[i] = 0;
			}
		}
	}
	else
	{
		for(i=0;i<3;i++)	//Set +, -. *
		{
			result[len] = i;
			generate(len+1, result);
		}
	}
}

int main()
{
//	ifstream fin ("in.txt");
//	cin = fin;

	int i, result[9];
	generate(0, result);	//Take 0.006s
	
	//Generate all combination of indexes then test(optimization)
	while(cin>>op[0]>>op[1]>>op[2]>>op[3]>>op[4])
	{
		if(!op[0] && !op[1] && !op[2] && !op[3] && !op[4])
			break;

		for(i=0;i<MAX;i++)
			if(foundSeq( combs[i] ))	//Test the data directly
				break;

			if(i < MAX )				//Found one of Sequences
				cout<<"Possible\n";
			else
				cout<<"Impossible\n";
	}	
	return 0;
}

I am sorry for posting my code, but i do not know where is my problem

[shihabrc]

Hi all,

I'm getting TLE in 10344. I've used recursion to denerate all possible strings of "+*-". since there are 4 slots for operators and 5 operands. so there can be at most 3^4 * 5! or 9720 possible expressions. I think this can be evaluated within time. But i'm getting TLE.some1 plz hlp.

Code: Select all

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

vector<int> num;
char ops[5];
char operators[] = "+-*\0";
bool possible;

void evaluateExpression();
void makeExpression(int);

void main()
{
	int a,b,c,d,e;

	freopen("C:\\4.txt","rb",stdin);

	while(scanf("%d %d %d %d %d",&a,&b,&c,&d,&e) == 5)
	{
		if( a == 0 && b == 0 && c == 0 && d == 0 && e == 0) break;
		possible = false;
		num.clear();
		num.push_back(a);num.push_back(b);
		num.push_back(c);num.push_back(d);num.push_back(e);
		makeExpression(0);
		if(possible) puts("Possible");
		else puts("Impossible");
	}
}


void makeExpression(int k)
{
	int i;

	for( i = 0; i < 3; i++)
	{
		ops[k] = operators[i];
		if( k == 3) evaluateExpression();
		else makeExpression(k+1);

		if(possible) return;
	}
}

void evaluateExpression()
{
	int i,result = 0, j = 0;
	sort(num.begin(),num.end());

	do
	{
		result = num[0];
		j = 1;
		for( i = 0; i < 4; i++)
		{
			switch(ops[i])
			{
			case '+':
				result+=num[j];
				j++;
				break;
				
			case '-':
				result-=num[j];
				j++;
				break;
			
			case '*':
				result*=num[j];
				j++;
				break;
			}
		}

		if( result == 23)
		{
			possible = true;
			break;
		}

	} while( next_permutation(num.begin(),num.end()) );
}

[mosaick2]

Your Backtracking implementation is a little bad.
I used the same algorithm and I also used the next_permutation.
But, when I tested your program and mine. The count results that recall the function was like below.

input => count result
1 1 1 1 1 => you: 324, me: 121
1 2 3 4 5 => you: 2948, me: 456
2 3 5 7 11 => you: 7260, me:1137

I think you can do more pruning with your state space.
I hope It'll be helpful to you.

Good Luck!! : )

[abhiramn]

WAjavascript:emoticon('')

Code: Select all

#include<stdio.h>
#include<math.h>
long poss(long num,long index,long a[])
{
        long ret,ans=0;
        if(index==0)
                return (a[index]==num);
        ret=poss(num-a[index],index-1,a);
        ans|=ret;
        ret=poss(num+a[index],index-1,a);
        ans|=ret;
        if(!(abs(num)%a[index]))
        {
                ret=poss(num/a[index],index-1,a);
                ret|=poss(num/a[index]*(-1),index-1,a);
        }
        ans|=ret;
        return ans;
}
int main()
{
        long a[5];
        while(1)
        {
                scanf("%ld%ld%ld%ld%ld",&a[0],&a[1],&a[2],&a[3],&a[4]);
                if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0&&a[4]==0)
                        break;
                if(poss(23,4,a))
                        printf("Possible\n");
                else
                        printf("Impossible\n");
        }
        return 0;
}

[Jan]

Try the cases...

Input:

Code: Select all

25 29 9 13 15
42 5 3 4 43
15 42 12 4 19
0 0 0 0 0

Output:

Code: Select all

Possible
Possible
Possible

Reason:

Code: Select all

13-9+15-25+29
(43-42)*4*5+3
(4+12-15)*42-19

Hope these help.

[abhiramn]

Problem!!!! What is the problem with this. I am getting TLE!!!



CODE ACCEPTED[/b]

[abhiramn]

Got AC... The worst problem ever!!!! Anyways, it was fun.

[rezaeeEE]

Code: Select all

#include <iostream>

using namespace std;
long long a1,a2,a3,a4,a5;
int a[6];
int mark[6];
long long adad[6];
int t,pointer=1;

void hesab(int c,long long javab,int shomar)
{
     if(t)return;
     mark[c]=1;
     for(int i=1;i<=5;i++)
     if(!mark[i])
     {            
     hesab(i,javab+a[i],shomar+1);
     hesab(i,javab*a[i],shomar+1);
     hesab(i,javab-a[i],shomar+1);
     mark[i]=1;
     }
     
     if(javab==23 && shomar==5)
     t=1;

     return;    
}

int main()
{
    while(cin>>a1>>a2>>a3>>a4>>a5,(a1 || a2 || a3 || a4 || a5 ))
    {
        t=0;
        for(int i=1;i<=5;i++)
        mark[i]=0;
        a[1]=a1;
        a[2]=a2;
        a[3]=a3;
        a[4]=a4;
        a[5]=a5;
        for(int i=1;i<=5;i++)
        {
                if(!t)
                hesab(i,a[i],1);
                mark[i]=0;
        }
        if(t)
             cout<<"Possible"<<endl;
        else
            cout<<"Impossible"<<endl;
        }
    return 0;
}

i get TLE.
can any body help me?thanks.

[Biks]

I have read the previous posts about 10344.
-->Someone said that there maybe negative numbers in input.
-->Someone said to check for both 23 and -23.
-->Someone said to check for negative input and output.

I have just solved the problem without considering any of the above.

-->There will be at most 120 * 3^4 iterations.
-->precalculate the 3^4 operators and 5!=120 operands(by rearranging)

It might help you.

[wjomlex]

I'm getting TLE, and given that some of the C++ people are getting TLE, I expect that the test input is just really massive and this problem can't be done in Java, even with BufferedReader and StringBuffer.

Code: Select all

import java.util.*;
import java.io.*;

public class Main
{
	static int[] a, b;
	public static void main(String args[]) throws IOException
	{
		BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		while(true)
		{
			a = new int[5];
			StringTokenizer st = new StringTokenizer(scan.readLine());

			for(int i=0;i < 5;i++)
				a[i] = Integer.parseInt(st.nextToken());

			if(a[0] == 0)
				break;

			Arrays.sort(a);
			
			b = new int[4];

			boolean yes = false;

			do
			{
				do
				{
					int rtn = a[0];

					for(int i=0;i < 4;i++)
					{
						switch(b[i])
						{
							case 0:
								rtn += a[i+1];
								break;
							case 1:
								rtn -= a[i+1];
								break;
							case 2:
								rtn *= a[i+1];
								break;
						}
					}

					if(rtn == 23)
						yes = true;


				}
				while (inc() && !yes);
			}
			while (next() && !yes);

			if(yes)
				sb.append("Possible\n");
			else
				sb.append("Impossible\n");
		}

		System.out.print(sb);
	}

	public static boolean next()
	{
		boolean quit = true;
		for(int i=0;i < 4;i++)
			if(a[i] < a[i+1])
				quit = false;

		if(quit)
			return false;

		int i = a.length - 2;

		while(a[i] >= a[i+1])
			i--;

		int j = a.length - 1;
		while(a[i] >= a[j])
			j--;

		int tmp = a[i];
		a[i] = a[j];
		a[j] = tmp;

		i++;
		j = a.length - 1;

		while(i < j)
		{
			tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
			i++;
			j--;
		}

		return true;
	}

	public static boolean inc()
	{
		for(int i=0;i < 4;i++)
		{
			b[i] = (b[i] + 1) % 3;

			if(b[i] > 0)
				break;

			if(i == 3 && b[i] == 0)
				return false;
		}

		return true;
	}
}

[sazzadcsedu]

Can someone tell me how to reduce search space.My approach is brute force and it can't avoid TLE .
Here is my code -

Code: Select all

#pragma warning(disable:4786)


#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<map>
#include<string>
#include<algorithm>


using namespace std;

  
map <char,int> Map;

map <string,int> Used;

int Pos;
int m;


//function to calculate expression

void Cal(char Str[],char oper[])
{
	int num,operat,i,x;
	
	num=Map[Str[0]];

	for(i=1;i<5;i++)
	{
		
	 
		operat=oper[i-1];
		
		x=Map[Str[i]];

		if(operat=='*')
		{

			num=num*x;

		}

		else	if(operat=='-')
		{

			num=num-x;

		}

		else	if(operat=='+')
		{

			num=num+x;

		}

	 
	}

 
	if(num==23)
	{
		Pos=1;
	}

	//printf("str=%s opr=%s num=%d\n",Str,oper,num);
	

}


int main()
{


 
	char Alph[52]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxy";
	char opr[4]="-+*";
	char OP[82][5];
	char S[1000002];

	int a,b,c,d,e,i,j,k,l,r,count;
	char ch;


	k=0;
	for(ch='A';ch<='Z';ch++)
	{
	 
		Map[ch]=k;
		k++;
	}

	for(ch='a';ch<='z';ch++)
	{
	 
		Map[ch]=k;
		k++;
	}


		r=1;
		for(i=0;i<3;i++)
		{

			for(j=0;j<3;j++)
			{
				for(k=0;k<3;k++)
				{
					for(l=0;l<3;l++)
					{
						OP[r][0]=opr[i];
						OP[r][1]=opr[j];
						OP[r][2]=opr[k];
						OP[r][3]=opr[l];
						OP[r][4]='\0';
						r++;
					}
				}
			}
		}



	while(scanf("%d %d %d %d %d",&a,&b,&c,&d,&e)==5)
	{


		if(a==0 && b==0 && c==0 && d==0 && e==0)
			break;


		if(a%2==0 && b%2==0 && c%2==0 && d%2==0 && e%2==0)
		{
			printf("Impossible\n");
			continue;

		}
 

	 

		S[0]=Alph[a];
		S[1]=Alph[b];
		S[2]=Alph[c];
		S[3]=Alph[d];
		S[4]=Alph[e];


		S[5]='\0';
		
		Used.clear();
	
		Pos=0;
	


		count=0;
		for(i=1;;i++)
		{

			if(Used[S]==1 || Pos==1)
			{
				break;
			}

			Used[S]=1;

			for(j=1;j<=81;j++)
			{
				Cal(S,OP[j]);

				if(Pos==1)
					break;
				
				 count++;

			}

			 
			next_permutation(S,S+5);
		}


		if(Pos==1)
		{
			printf("Possible\n");
		}

		else
			printf("Impossible\n");


		printf("Number of chaecking =%d\n",count);


	}
	return 0;
}

I did not find anyway to reduce search space.So plz someone help me.

[xusang]

WA~ help me ..............
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std ;
const int maxn = 6;
int str[maxn] ;
int ok ;
int vis[maxn] ;
void dfs(int cur , int sum)
{
// cout << sum ;
if(cur == 5 && sum == 23 )
{
ok = 1 ; return ;
}
else if( cur <= 5 )
//// for(int i = 0 ; i < 5 ; i++ )
{
//// if(!vis)
// {
// vis = 1 ;
dfs(cur + 1 , sum + str[cur]) ;
dfs(cur + 1 , sum * str[cur] ) ;
dfs(cur + 1 , sum - str[cur] ) ;
// vis = 0 ;
// }
}
}
int main()
{
while(1)
{

for(int i = 0 ;i < 5 ; i++ )
cin >> str ;
if(str[0] == 0 )
break ;
// for(int i = 0 ; i < 5 ; i ++ )
// cout << str ;
// cout << endl ;
ok = 0 ;
// for(int i = 0 ; i < 5 ; i ++ )
// {
// memset(vis , 0 , sizeof(vis) ) ;
////
////
// vis=1;

dfs(0 , str[0]) ;
// }
if( ok )
cout << "Possible" <<endl ;
else cout << "Impossible" <<endl ;
}
return 0 ;
}

[helloneo]

Try Jan's test case..
Your code doesn't pass..