124 - Following Orders

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Prob 124

Post by taj79 » Thu Jun 27, 2002 1:18 pm

In this prob it is said that input will be terminated by End of File
I am not getting how to do this. I have tried like this

Code: Select all

[c]

#include<stdio.h>
#include<stdlib.h>

#define MAX 30
main()
{int j,i = -1;
 char c[MAX];

  do{
    scanf("%c",&c[++i] );

    }while( c[i] != EOF);
    --i;
    printf("i=%d\n",i);
  for(j=0;j<=i;j++)
   printf(" %d",c[j] );
}

[/c]
My input file testcheck is like this
dfgds
asdfg

My prog name is check.c
When i ran the prog it gave
./check < testcheck
i=17
100 102 103 100 115 10 97 115 100 102 103 10 46 -111 20 64 56 -6

I have tried to chenge EOF with '\0'
but it was same.
I don't understand how i became 17 when I am put just 10 chars.

Please help me out

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Thu Jun 27, 2002 1:34 pm

scanf returns -1 if you reached the end of file, so you can try while(scanf("%c",&c[++i])!=-1) or while(scanf("%c",&c[++i])!=EOF)

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

124 - Following Orders

Post by Revenger » Thu Jun 27, 2002 2:32 pm

I tested my program many times, but with no result.
Please, help me!

[pascal]Program p124;

Const MaxN = 20;
MaxR = 50;
MaxA = 300;

Var All : Array[1..MaxN]of char;
Relat : Array[1..MaxN,1..MaxN]of Byte;
Inf : Array[1..MaxN]of record Min,Max : Integer end;
Ans : Array[1..MaxA]of String[MaxN];
Order : Array[1..MaxN]of Integer;
Use : Array[1..MaxN]of Integer;
AnsInt : Integer;
Ch : Char;
N,i,j : Integer;
n1,n2 : Integer;
Tmp : String[MaxN];
FTime : Boolean;

Procedure Rec(Position : Integer);
Var i,j,ok : integer;
begin
if Position=N+1 then begin
AnsInt:=AnsInt+1;
Tmp:='';
for i:=1 to N do
Tmp:=Tmp+All[Order];
Ans[AnsInt]:=Tmp;
end;
for i:=1 to N do
if Use=0 then begin
ok:=1;
for j:=1 to N do
if j<>i then begin
if (Relat[j,i]=1)and(Use[j]=0) then begin ok:=0; break; end;
if (Relat[i,j]=1)and(Use[j]=1) then begin ok:=0; break; end;
end;
if ok=1 then begin
Order[Position]:=i;
Use:=1;
Rec(Position+1);
Use:=0;
end;
end;
end;

begin
FTime:=True;
While Not Eof(InPut) Do begin
if Not(FTime) then Writeln;
FTime:=False;
N:=0;
While Not Eoln(InPut) Do begin
Read(Ch);
if Ch<>' ' then begin
N:=N+1;
All[N]:=Ch;
end;
end;
Readln;
FillChar(Relat,SizeOf(InPut),0);
for i:=1 to N do begin
Inf.Min:=1;
Inf.Max:=N;
end;
n1:=-1;
n2:=-1;
While Not Eoln(InPut) Do begin
Read(Ch);
if Ch<>' ' then begin
j:=-1;
for i:=1 to N do
if All=Ch then begin
j:=i;
Break;
end;
if j<>-1 then
if n1=-1 then n1:=j else begin
n2:=j;
Relat[n1,n2]:=1;
n1:=-1;
n2:=-1;
end;
end;
end;
Readln;
AnsInt:=0;
FillChar(Use,SizeOf(Use),0);
Rec(1);
for i:=1 to AnsInt-1 do
for j:=i+1 to AnsInt do
if Ans>Ans[j] then begin
Tmp:=Ans;
Ans:=Ans[j];
Ans[j]:=Tmp;
end;
for i:=1 to AnsInt do Writeln(Ans[i]);
end;
end.[/pascal]

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Jun 27, 2002 3:05 pm

Hi!

I got your program Accepted after a few changes...
I didn't look exactly i the code but at the beginning I made 2 changes...

1. I have increased Maxn to 50 (I don't know why :)
2. Next I have changed byte into longint..

And I got Accepted...

I think that you have set byte=-1 and this is the reason..

So change these two things and that's all..

Good Luck :wink:

Revenger
Experienced poster
Posts: 132
Joined: Sun Apr 14, 2002 12:27 pm
Location: Russia

Post by Revenger » Thu Jun 27, 2002 3:44 pm

Hmm....

First I changed Byte into Integer and get WA
Then I changed Byte into LongInt and get Accepted

Very strange.... :roll:

And thank you for your help!

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Thu Jun 27, 2002 3:48 pm

Hi!

Yes I had a similar problem in problem 100 ...

When I have changed longint to integer (or integer to longint) I got accepted....

Yes sometimes judge is very strange :wink:

But it is always right :D

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Tue Jul 02, 2002 1:55 pm

i am getting run time error:
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.130 seconds.


Code: Select all

[c]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 21
#define MAX1 51
#define MAX2 301

void comb(int *count,int pos,int n,int t2,char C[],char S[][MAX1],char SO[][MAX]);
int check(char S1[],char S[][MAX1],int t,int t2);
void quicksort(char SO[][MAX],int n,int p,int r);
int p_less_than_r(char Sp[],int n,char Sr[]);
int  partition(char SO[][MAX],int n,int p,int r);

main()
{int t,t1,i,j,end =0,count,k;
 char S[2][MAX1],C[MAX],C1[MAX1],c,SO[MAX2][MAX];

    do{

	t = -1;
	for(;;)
	{  scanf("%c",&c);
	  /* printf("   c=%c  Printing char in 1st loop\n",c);  */
	 if( c == '\n' )
	  break;
         if(c != ' ')
	   C[++t] = c;
	}/* variables have been taken  */
/*	for(i=0;i<=t;i++)
	 printf(" %c",C[i]);
	 printf("\n"); */

       t1=-1;count=-1;
      for(;;)
	{
	 if(scanf("%c",&c) == -1)
	 { end = 1;
           break;
         }
        if( c == '\n' )
	  break;
         if(c != ' ')
	   C1[++t1] = c;
	}/* constraints have been taken  */
      if( end != 1)/* #1 */
      {
       j=-1;
      for(i=0;i<=t1;i++)
      { if(i %2 == 0)
         { ++j;
	    S[0][j] = C1[i];
	 }
	 else
	   S[1][j] = C1[i];
      }/* Now the constraints have been put in a proper way */


   /* printing the variables & the constraints */
/*   for(i=0;i<=t;i++)
   printf(" %c",C[i]);
   printf("\nt1=%d \n The constraint line\n",t1);
    for(i=0;i<=t1;i++)
     printf(" %c",C1[i] );
      printf("\nThe constraints\n");
   for(i=0;i<= (t1-1)/2;i++)
    printf("     %c < %c",S[0][i],S[1][i]);
   */
     comb(&count,0,t+1,(t1 - 1)/2,C,S,SO);
  /*  printf("%d\n",count);  */
    quicksort( SO, t+1, 0, count);
    for(k= 0;k<=count;k++)
     printf("%s\n",SO[k]);

    printf("\n");
   }/* END of if  #1 */
  }while( end != 1);


}
 /*
    t=-1;
    do{
       if(S[++t] == '\0')
       { --t;
        break;
       }
      }while(S[t] != '\0');

    comb(0,t+1,S);
}

*/
void comb(int *count,int pos,int n,int t2,char C[],char S[][MAX1],char SO[][MAX])/* t2 = (t1 -1)/2  */
               {int i,j,q;

               static char S1[MAX];

               if(pos==(n))
                  {
                     S1[pos]=0;
		    /* printf("\n Before calling check()\n");
                      for(i=0;i<n;i++)
		       printf(" %c",S1[i]);
		      printf("\n");  */
		    if( check(S1,S,n,t2)== 1)
		      {++(*count);
		      /* printf("%s\n",S1);  */
		       for(j=0;j<n;j++)
		        SO[*count][j] = S1[j];
	              }
                  }

               else
	         for( i=0;i<n;++i)
                if(C[i])
                        {
                           S1[pos]=C[i];
                           C[i]=0;         /*mark as used  */
                           comb(count,pos+1,n,t2,C,S,SO);
                           C[i]=S1[pos];   /* restore  */
                        }

               }

 int check(char S1[],char S[][MAX1],int n,int t2)
{
 int i,j,low,up;
  for(i=0;i<=t2;i++)
  {
   low = 0;
   up =0;

   for(j=0;j<n;j++)
    if( S[0][i] == S1[j] )
     break;
     low = j;

  for(j=0;j<n;j++)
    if( S[1][i] == S1[j] )
     break;
     up = j;
/*  printf("  low = %d  up = %d ",low,up);  */
   if( low > up)
   return(0);

   }
  return(1);
}


void quicksort(char SO[][MAX],int n,int p,int r)
  {int q;
/*   printf("\n\n Entered quicksort\n\n");
   printf("p = %d    r = %d\n",p,r);  */
   if( p_less_than_r(SO[p],n,SO[r]) == 1){ /*    ++count;
      printf("%d",count);  */
       q = partition(SO,n,p,r);
       quicksort(SO,n,p,q);
       quicksort(SO,n,q+1,r);
       }
       return;
   }

int p_less_than_r(char Sp[],int n,char Sr[])
{int i;
 for(i=0;i<n;i++)
  if(Sp[i] > Sr[i] )
   return(0);
  return(1);
}

int  partition(char SO[][MAX],int n,int p,int r)
   {
     int i,j,k;
     char S[MAX],u[MAX];

     for(k=0;k<n;k++)
      S[k] = SO[p][k];
     /* x = A[p];  */
     i = p-1;
     j = r+1;
     while(1){
            do{--j;
	      }while(p_less_than_r(SO[j],n,S) == 0);
	    do{ ++i;
	      }while(p_less_than_r(SO[i],n,S) == 1);
	    if(i < j)
	    { for(k=0;k<n;k++)
               u[k] = SO[i][k];

              for(k=0;k<n;k++)
               SO[i][k] = SO[j][k];

	      for(k=0;k<n;k++)
                SO[j][k]= u[k];
	    }
	    else
	     return(j);
	     }
   }


[/c]
[/c][/code]

taj79
Learning poster
Posts: 74
Joined: Sun Jun 09, 2002 11:56 am
Location: India
Contact:

Post by taj79 » Thu Jul 04, 2002 7:43 pm


I have solved this problem using the algo which picard gave me for solving prob 195.

But I don't know what's the problem with prog I have put before this message.It's working fine in my computer.

Can anyone help me out?

I had also posted my prog for prob 101 several days ago.
I didn't get any help for that.

Please help me out for that problem also.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

#124 WA

Post by titid_gede » Wed Mar 05, 2003 8:22 am

i've got WA with this (looked easy) problem. Can you give me what's wrong ? are there special cases in this problem?

[c]
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX 30
#define MAXLINE 255

int isok (int mat[MAX][MAX], char result[MAX], int ct, char x) {
int i;
for (i = ct-1; i >= 0; i--)
if (mat[result-'a'][x-'a'] == 1) return 0;
return 1;
}

int trace (int mat[MAX][MAX], char data[MAX], int jumdata, int isused[MAX],
char result[MAX], int ct) {
int i;

if (ct == jumdata) {
for (i = 0; i < jumdata; i++) printf ("%c", result);
printf ("\n");
} else {
for (i = 0; i < jumdata; i++)
if ((isused == 0) && (isok (mat, result, ct, data))) {
isused = 1;
result[ct] = data;
trace(mat, data, jumdata, isused, result, ct+1);
isused = 0;
}

}
return 0;
}

int main () {
char data[MAX], result[MAX], line[MAXLINE], a, b;
int mat[MAX][MAX], ct, len, jumdata, isused[MAX];

while (1) {
if (fgets (line, MAXLINE, stdin) == NULL) break;
len = strlen (line)-1;
jumdata = 0;
for (ct = 0; ct < len; ct++)
if (islower (line[ct]))
data[jumdata++] = line[ct];

memset (mat, 0, sizeof(int)*MAX*MAX);
memset (isused, 0, sizeof(int)*MAX);
fgets (line, MAXLINE, stdin);
len = strlen (line) - 1;
for (ct = 0; ct < len; ct++) {
if (islower (line[ct])) {
a = line[ct];
do {
ct++;
} while (!islower(line[ct]));
b = line[ct];
mat[b-'a'][a-'a'] = 1;
}
}

trace (mat, data, jumdata, isused, result, 0);
printf ("\n");
}
return 0;
}

[/c]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Mar 05, 2003 10:49 am

Hello, uhm, titid_gede (I feel so uncomfortable pronouncing your nickname) ...

Why don't you try this input and tell me what your output is:

Code: Select all

d c a b
a d d b
My guess was your solution didn't sort the output ...

Good luck,

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Mar 06, 2003 2:52 pm

aha! i forgot that. i've fixed it and got AC. thank you very much :D :D :D

amir2099
New poster
Posts: 10
Joined: Sun Jun 01, 2003 7:52 pm
Location: Canada
Contact:

Post by amir2099 » Tue Jun 10, 2003 12:23 am

hmmm... couldn't your teacher possibly stumble upon this board?

anyhow, if it's an assignment, I doubt anyone will help you.
If you have to do any three problems, browse through them and try to find the easiest ones. I mean, you have a month to do this. :roll:

Hell, you might even find some solutions if you search on google hard enough, but you'd only be tricking yourself, and it'll catch up on you later on.

*sorry
-------------------------------------------
"my name is amir"
-amir

Trinity
New poster
Posts: 12
Joined: Tue Jun 10, 2003 3:40 pm

Post by Trinity » Tue Jun 10, 2003 8:31 pm

Sorry, I changed my user, but I'm still here...


Trinity

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

124 - so unclear description...

Post by Dmytro Chernysh » Thu Jun 26, 2003 4:56 pm

Can somebedy explain me the description of this problem?
Besause as I understood this problem, the output "abgf" (from the sample output) is wrong, besause f<g as was told... :-(

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Thu Jun 26, 2003 5:37 pm

A specification consists of two lines: a list of variables on one line followed by a list of contraints on the next line.
the first line is just the variables. the second line is the constraints, so the onl constraints are a<b and b<f

interesting, this is just like the 2003 CCC stage 2 problem day 2 #1.

Post Reply

Return to “Volume 1 (100-199)”