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(':cry:')

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[i])
// {
// vis[i] = 1 ;
dfs(cur + 1 , sum + str[cur]) ;
dfs(cur + 1 , sum * str[cur] ) ;
dfs(cur + 1 , sum - str[cur] ) ;
// vis[i] = 0 ;
// }
}
}
int main()
{
while(1)
{

for(int i = 0 ;i < 5 ; i++ )
cin >> str[i] ;
if(str[0] == 0 )
break ;
// for(int i = 0 ; i < 5 ; i ++ )
// cout << str[i] ;
// cout << endl ;
ok = 0 ;
// for(int i = 0 ; i < 5 ; i ++ )
// {
// memset(vis , 0 , sizeof(vis) ) ;
////
////
// vis[i]=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..