Page 1 of 1

10146 - Dictionary

Posted: Mon May 12, 2003 8:19 am
by Dominik Michniewski
I tried (I thought that easy ...) problem 10146 (Dictionary). But I don't understand why I got WA ...
Could anyone send me some input, or take a look at my code (It's easy - it have one function to read word and one for output it :) ) ?

Best regards
DM

Posted: Mon May 12, 2003 8:49 pm
by Adil
hi. here are some input/output. the blank spaces are replaced by '.'

Code: Select all

1

abcde
abcd
abcd
abc
abc
ab
a

abcde
.abcd
..abcd
...abc
...abc
..ab
.a
hope this helps. you can also send my your code.

Posted: Tue May 13, 2003 7:51 am
by Dominik Michniewski
Thanks Adil for helpfull IO :D
I should go to vacation ;) I'm starting to do silly mistakes :(
This time I don't consider moment, in which words end, so I got
abcde
.abcd
..abcd
...abc
....abc <- one more space ...
..ab
.a

And this one space causes me WA ...

Thanks
DM

Posted: Sun Jul 04, 2004 6:14 am
by Amir Aavani
hi every one.
could you please tell me what is output for the following input
1

a
ab
abc
abd
abcd

is it
a
.ab
..abc
..abd
..abcd

or

a
.ab
..abc
..abd
...abcd <-

thanks
Amir

Posted: Sun Oct 23, 2005 8:01 am
by jjtse
Dominik Michniewski wrote:Thanks Adil for helpfull IO :D
I should go to vacation ;) I'm starting to do silly mistakes :(
This time I don't consider moment, in which words end, so I got
abcde
.abcd
..abcd
...abc
....abc <- one more space ...
..ab
.a

And this one space causes me WA ...

Thanks
DM

dude, I initially had that problem, and I fixed it. But it still gives me WA. I don' t know what else might be wrong. Do you have more sample inputs?


JT

10146 "dictionary" - problem didn't express its s

Posted: Sun Oct 23, 2005 8:22 am
by jjtse
Hi everyone,

I can't believe this problem is a legitimate ACM problem. It doesn't clearly lay out the specifications of the problem. I just tells you to look at the example to kind of understand what they're asking. yeah, that's true, but the one example they provided us doesn't cover all cases. You know what I mean? What about all the other border line cases? How are we supposed to know what they want without them clearly stating what they want in the problem specifications.

Bottom line is, the programmer cannot understand what the problem wants unless he/she is the one who wrote the problem. My program clearly solves the sample input they provided, and I even made up several input files of my own. Again, I don't know whether the border cases in my sample input are correct or not, because the problem doesn't say. Does anyone have a set of sample inputs and outputs? Thanks


Jia

Posted: Thu Dec 27, 2007 11:26 am
by Kallol
I used brute force and getting TLE ..
how did u people try it ?
can u explain ur strategy here ??

Re: 10146 - Dictionary

Posted: Thu Jun 10, 2010 8:30 pm
by obbY
It doesn't seem a difficult problem, though i keep getting TLE, I don't know any other way except brute force to solve this problem, here's my C code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 15
#define SIZE 100001

int compare_strings(char* s1, char* s2)
{
	int count = 0;
	
	for( ; *s1 == *s2; *s1++, *s2++) count++;
	return count;
}
int main()
{
	char strArr[SIZE][MAX];
	int CASES, i, j, sp, count, y;
	
	scanf("%d\n", &CASES);
	
	i = 0;
	while(CASES--) {
		
		i = 0;
		while(1) {
			fgets(strArr[i], MAX, stdin);
			strArr[i][strlen(strArr[i])-1] = '\0';
			if(strArr[i][0] == '\0') break;
			i++;
		}
		
		/* output */
		count = 0;
		printf("%s\n", strArr[0]);
		for(j=1;j<i;j++) {
			sp = compare_strings(strArr[j], strArr[j-1]);
			if(sp == 0) count = 0;
			else if(sp > count) count++;
			else if(sp < count) count = sp;
			for(y=0;y<count;y++) putchar(32);
			printf("%s\n", strArr[j]);
		}
		if(CASES-1 >= 0) putchar('\n');
	}	
	return 0;
}
Hope anyone will help me..

Re: 10146 - Dictionary

Posted: Wed Jan 11, 2012 11:34 pm
by brianfry713
I used a brute force approach and got AC in 0.06 sec. obbY, I didn't store the output and never called strlen(). I just compared the current word to the previous word up to the current max length of spaces while printing out spaces. I then printed out the current word.