THE MISSING OPERATOR PROBLEM

You will be given a set of equations without operators. You are to write a program that determines what the missing operators are in each equation.

For example given

8 ? 9 ? 5 ? 2 ? 8 = 1

the correct answer is

8 - 9 * 5 - 2 + 8 = 1

The only operators you need to consider are +, - and * (addition, subtraction and multiplication).

The evaluations are assumed to be left to right with all operators having equal precedence. This means that 8 - 5 * 2 = 6.

The input will consist of an integer 0 For each equation you should output all possible operator assignments that satisfy the equation. It is possible that there is more than one satisfying assignment. Each assignment should be printed on a separate line. The format should be

eqn#: 8 - 9 * 5 - 2 + 8 = 1

with no leading or trailing white space. eqn# is the number of the equation. The first equation is equation 1. If no assignment exists the output should be eqn#: IMPOSSIBLE

SAMPLE INPUT
5 8 9 5 2 8 1
2 1 0 1
2 10 5 16
0

SAMPLE OUTPUT
1: 8 - 9 * 5 - 2 + 8 = 1
2: 1 - 0 = 1
2: 1 + 0 = 1
3: IMPOSSIBLE

Solution

#include < stdio.h>

main()
{
    int n;
    int done;
    int finished;
    int ops[30];
    int vals[30];
    int ans;
    int v;
    int i,j,k,l;
    int count;
    int cnum;
    cnum=0;

    while(1)
    {
        scanf("%d",&n);
        if (n==0)
            exit(0);
        for (i=0; i< n; ++i)
            scanf("%d",&vals[i]);
        scanf("%d",&ans);
        for (i=0; i< n; ++i)
            ops[i]=0;
        finished=0;
        count=0;
        ops[0]= -1;
        ++cnum;
        if (n==1)
        {
            if (vals[0]==ans)
            {
                printf("%d: %d = %d\n",cnum,ans,ans);
            }
            else
            {
                printf("%d: IMPOSSIBLE\n",cnum);
            }
            count=finished=1;
        }
        while (!finished)
        {
            k=0;
            do
            {
                done=1;
                ++ops[k];
                if (ops[k]==3)
                            {
                    ops[k]=0;
                    ++k;
                    done=0;
                }
            }
            while (k< n-1 && !done);
            finished=1;
            if (done)
            {
                finished=0;
                v=vals[0];
                for (i=0; i< n-1; ++i)
                {
                    if (ops[i]==0)
                        v=v+vals[i+1];
                    if (ops[i]==1)
                        v=v-vals[i+1];
                    if (ops[i]==2)
                        v=v*vals[i+1];
                }
                if (v==ans)
                {
                    ++count;
                    printf("%d: %d",cnum,vals[0]);
                    for (i=0; i< n-1; ++i)
                    {
                        if (ops[i]==0)
                            printf(" + ");
                        if (ops[i]==1)
                            printf(" - ");
                        if (ops[i]==2)
                            printf(" * ");
                        printf("%d",vals[i+1]);
                    }
                    printf(" = %d\n",ans);
                }
            }
        }
        if (!count)
            printf("%d: IMPOSSIBLE\n",cnum);
    }
}

THE LAWN MOWER PROBLEM

You will be given three integers describing the dimensions of your yard and the length of the chain. You are to write a program that calculates the percentage of the yard that the mower can reach.

The input consists of a series of cases. Each case consists of 3 integers on a line. The first integer is the length of the yard, the second is the width of the yard, and the third is the length of the chain. All 3 integers will be > 0. The input will be terminated by a line containing a 0.

The output for each case will be on a separate line. The output is simply the percentage of the yard that can be mowed. You should only print two digits to the right of the decimal point.

SAMPLE INPUT 
10 10 2
10 10 4
8 4 5
0

SAMPLE OUTPUT
3.14
12.57
54.97

Solution

#include < stdio.h>
#include < math.h>

main()
{
	long w,h,l;
	int t;
	double a1,a2,a3;
	double a;
	double PI;
	double arc;
	double arc1,arc2;

	PI=4*atan(1.0);
	while (!feof(stdin))
	{
		a=0;
		scanf("%ld %ld %ld",&w,&h,&l);
		if (w==0)
			break;
	
		if (l<=w && l<=h)
			a=l*l*PI/4.0;
		else if (l<=w && l>h)
		{
			arc=asin(h*1.0/l*1.0);
			a=l*l*arc/2.0 + (h*cos(arc)*l)/2.0;
		}
		else if (l>w && l <=h)
		{
			arc=acos(w*1.0/l*1.0);
			a=l*l*(PI/2.0-arc)/2.0 + (w*sin(arc)*l)/2.0;
		}
		else if (l*l <= w*w+h*h)
		{
			arc1=acos(w*1.0/l);
			arc2=asin(h*1.0/l);
			a=l*l*(arc2-arc1)/2.0 + (h*cos(arc2)*l)/2.0+ (w*sin(arc1)*l)/2.0;
		}
		else
		{
			a=w*h;
		}
		printf("%.2lf\n",100*a/(h*w));
	}
}

THE DESPERATELY SEEKING SOMEONE PROBLEM

The input will contain a number of mazes. The first line contains a single integer n indicating the size of the first maze. All the mazes are square. The next n lines each contain n characters. The characters are either space, 'X', 'Y' or '#'. A space is open space. 'X' is the initial position of Person X. 'Y' is the position of Person Y. '#' is an obstacle. The next line contains the size of the second maze, etc. The input will be terminated by a maze with size 0. There will always be an 'X' and a 'Y'.

The output for each maze should be either the number of steps, or the word IMPOSSIBLE. The output for each maze should be on a separate line.

SAMPLE INPUT 
4
    
X   
   Y
    
4
X   
### 
Y#  
    
8
    #  #
  Y     
        
  ######
  #     
###   X 
        
        
0

SAMPLE OUTPUT
4
10
IMPOSSIBLE

Solution

#include < stdio.h>

typedef struct a
{
	int x,y;
	int dist;
	struct a *next;
} que;
	

main()
{
    int n;
    int endx,endy;
    int x,y;
    int i,j;
    que *head,*tail,*t;
    
    char grid[64][64];
    char buffer[256];
    do
    {    
        gets(buffer);
        sscanf(buffer,"%d",&n);
        if (n)
        {
            head=tail=0l;
            for (i=0; i< n; ++i)
            {
                gets(buffer);
                for (j=0; j< n; ++j)
                {
                    if (buffer[j]=='X')
                    {
                        x=j;
                        y=i;
                        buffer[j]=' ';
                    }
                    if (buffer[j]=='Y')
                        endx=j,endy=i,buffer[j]=' ';
                    grid[j][i]=buffer[j];
                }
            }
            tail=head=(que *) malloc(sizeof(que));
            head->x=x;
            head->y=y;
            head->dist=0;
            head->next=0l;
            while (head)
            {
                if (head->x==endx && head->y==endy)
                {
                    break;
                }
                if (grid[head->x][head->y]!='X')
                {
                    grid[head->x][head->y]='X';
                    if (head->x)
                    {
                        if (grid[head->x-1][head->y]==' ')
                        {
                            tail->next=(que *) malloc(sizeof(que));
                            tail=tail->next;
                            tail->x=head->x-1;
                            tail->y=head->y;
                            tail->dist=head->dist+1;
                        }
                    }
                    if (head->x< n-1)
                    {
                        if (grid[head->x+1][head->y]==' ')
                        {
                            tail->next=(que *) malloc(sizeof(que));
                            tail=tail->next;
                            tail->x=head->x+1;
                            tail->y=head->y;
                            tail->dist=head->dist+1;
                        }
                    }
                    if (head->y)
                    {
                        if (grid[head->x][head->y-1]==' ')
                        {
                            tail->next=(que *) malloc(sizeof(que));
                            tail=tail->next;
                            tail->x=head->x;
                            tail->y=head->y-1;
                            tail->dist=head->dist+1;
                        }
                    }
                    if (head->y< n-1)
                    {
                        if (grid[head->x][head->y+1]==' ')
                        {
                            tail->next=(que *) malloc(sizeof(que));
	                    tail=tail->next;
                            tail->x=head->x;
                            tail->y=head->y+1;
                            tail->dist=head->dist+1;
                        }
                    }
                }
                t=head;
                head=head->next;
            }            
            if (head)
            {
                printf("%d\n",head->dist);
            }
            else
                printf("IMPOSSIBLE\n");
        }
    }    
    while (n);
}

NONREPEATING NUMBERS

Compute the number of such values for systems with radix M where 2 <= M <= 12.

The input will consist of a series of integer values M. A value of 0 ends the input.

The output is simply the number of integers containing no digit more than once.

An efficient algorithm is needed for this problem. For every minute your program runs, 3 minutes will be added to your time. For example, if you send in a solution in 50 minutes, and your program takes 5 minutes to run, we will score you as if it took you 65 minutes to solve the problem.

Your program will be tested with all 11 values of M in some random order. Your program will be run on a Sparc 10.

SAMPLE INPUT 
2
3   
4   

SAMPLE OUTPUT
2
10
48

Solution

#include < stdio.h>

main()
{
	int i,j,k;
	int n;
	long s,p;

	while(1)
	{
		scanf("%d",&n);
		if (n!=0)
		{
			s=0;
			for (j=0; j< n; ++j)
			{
				p=(n-1);
				for (k=j+1; k< n; ++k)
					p=p*k;
				s+=p;
			}
			printf("%ld\n",s);
		}
		else
			break;
	}
}

Lots of Comments:

You are to write a program that reads in text and determines if legal comment structures are used.

The precedence rules mean that /* and */ are meaningless inside a { } comment, and that everything is meaningless in a // comment.

The input will consist of a series of text blocks. A text block may be several lines long. Each text block is separated by a blank line. The input is terminated by the end of file. For each text block you are to print out VALID if the text block contains legal comment structures. That means that all comments are properly terminated. Otherwise you are to print out INVALID. The sample inputs contain numerous examples of valid and invalid comment structures.

SAMPLE INPUT
For example
{ this is a {very important} comment}
is legal because { } nests.

However /* this is a /* very important */ comment */
is illegal because /* */ does not nest.

This line /* is /* ok */

{ this is ok /* because of precedence rules }

/* this is bad { because of precedence rules */

A legal multiple line example is
This is /* {a comment // none of the rest of this line is important }
but this line is ok}*/

Note, the two character delimiters cannot be split /
* across lines and /{cannot be split by comments}* */
// which means that this is a invalid input.

It is a bad thing to have comment terminators like } without
having the appropriate comment beginning. 

//But you you have to be careful, this is trickier } than it
looks.


SAMPLE OUTPUT
VALID
INVALID
VALID
VALID
INVALID
VALID
INVALID
INVALID
VALID

Solution

#include < iostream.h>
main()
{
  int valid=1,bracket=0,cstyle=0,cplus=0,one=0,done=0,done2=0,returns=1;
  char buf;
  cin.get(buf);  
  while(!cin.eof())
    {
      valid=1;
      cstyle=0;
      bracket=0;
      cplus=0;
      one=0;
      done=0;
      while((buf!='\n')&&!cin.eof())
	{
	  switch(buf)
	    {
	     case '{':
	      bracket++;
	      break;
	     case '}':
	      bracket--;
	      if (bracket<0)
		  valid=0;
	      break;
	     case '/':
	      buf=cin.peek();
	      switch(buf)
		{
		 case '*':
		  if (bracket==0)
		    {
		      cin.get(buf);
		      if (cstyle==0)
			{
			  cstyle=1;
			}
		    }
		  break;
		 case '/':
		  cin.get(buf);
		  cplus=1;
		  break;
		 default:
		  break;
		}
	      break;
	     case '*':
	      if (bracket==0)
		{
		  buf=cin.peek();
		  if (buf=='/')
		    {
		      cin.get(buf);
		      cstyle--;
		    }
		  if (cstyle <0)
		    {
		      valid=0;
		    }
		}
	      break;
	     default:
	      break;
	    }
	  if (cplus)
	    {
	      while (cplus)
		{
		  buf=cin.peek();
		  if (buf=='\n')
		      cplus=0;
		  else
		      cin.get(buf);
		}
	    }
	  if (!valid)
	      break;
	  if (!cin.eof())
	      cin.get(buf);
	  returns=0;
	  if ((buf=='\n'))
	    {
	      done2=0;
	      returns=1;
	      buf=cin.peek();
	      while(!cin.eof() && !done2)
		{
		  switch(buf)
		    {
		     case ' ':
		      cin.get(buf);
		      buf=cin.peek();
		      break;
		     case '\n':
		      returns++;
		      cin.get(buf);
		      buf=cin.peek();
		      break;
		     default:
		      done2=1;
		      cin.get(buf);
		      break;
		    }
		}
	    }
	  if (returns > 1)
	      break;
	}
      if (!valid)
	{
	  done=0;
	  while(!done&&!cin.eof())
	    {
	      cin.get(buf);
	      if (buf=='\n')
		  one++;
	      else if (buf != ' ')
		  one=0;
	      if (one==2)
		{
		  done=1;
		  buf=cin.peek();
		  while (((buf=='\n')||(buf==' '))&&!cin.eof())
		    {
		      cin.get(buf);
		      buf=cin.peek();
		    }
		}
	    }
	}
      if (valid)
	{
	  if (bracket!=0) valid=0;
	  if (cstyle!=0) valid=0;
	}
      if (valid)
	  cout << "VALID" << endl;
      else
	  cout << "INVALID" << endl;
    }
}

Blocks:

           +----------+
           |          |
           |    d     |
           +----------+
	 +---+     +-----+
         |   |     |  c  |
         |   |     +-----+
         | a |   +--------+
         |   |   |   b    |
         +---+   +--------+

The input will consist of a set of cases. The format for each case is as follows: The first line will contain the name of all the blocks. Block names are always a single character. There will be one space between block names. On the following lines there will be two block names separated by a space. This line indicates that the first block is on top of the second block. A blank line will terminate each case.

The entire input is terminated by the end of file.

For example, the input describing the above picture is

a b c d
d a
d c
c b

If it is possible to remove more than one block, remove the blocks in alphabetical order.

The output for the example would be

d a c b

SAMPLE INPUT
a b c d
d a
d c
c b

a b c d e f
f e
e d
d c
c b

a b c d
a b
b c
c d
d a


SAMPLE OUTPUT
d a c b
a f e d c b
IMPOSSIBLE

Solution

#include 

int n;
char blockname[256];
char on[256][256];
int count[256];
int getblocknum(char);

main()
{
	int found;
	int i,j,k;
	char t;
	char buffer[256];
	char ans[256];

	while(gets(buffer))
	{
		n=0;
		i=0;
		while(buffer[i])
		{
			blockname[n++]=buffer[i];
			++i;
			if (buffer[i]==' ')
				++i;
		}

		for (i=0; i< n; ++i)
		{
			for (j=i+1; j< n; ++j)
			{
				if (blockname[i]>blockname[j])
				{
					t=blockname[i];
					blockname[i]=blockname[j];
					blockname[j]=t;
				}
			}
		}
		for (i=0; i< n; ++i)
		{
			count[i]=0;
			for (j=0; j< n; ++j)
			{
				on[i][j]=0;
			}
		}
		while(1)
		{
			gets(buffer);
			if (!buffer[0])
				break;
			i=getblocknum(buffer[0]);
			j=getblocknum(buffer[2]);
			on[i][j]=1;
			count[j]+=1;
		}	
		for (i=0; i< n; ++i)
		{
			found= -1;
			for (j=0; j< n; ++j)
			{
				if (count[j]==0)
				{
					found=j;
					for (k=0; k< n; ++k)
						if (on[j][k])
							--count[k];
					count[j]=-1;
					break;
				}
			}
			if (found!=-1)
			{
				ans[i]=found;
			}
			else
				break;
		}	
		if (found==-1)
			printf("IMPOSSIBLE\n");
		else
		{
			for (i=0; i< n; ++i)
			{
				if (i!=0)
					printf(" ");
				printf("%c",blockname[ans[i]]);
			}
			printf("\n");
		}
	}	
}

getblocknum(char b)
{
	int i;
	for (i=0; i< n; ++i)
		if (b==blockname[i])
			return i;
	return 0;
}