10146 - Dictionary

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

Moderator: Board moderators

Post Reply
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

10146 - Dictionary

Post by Dominik Michniewski » Mon May 12, 2003 8:19 am

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Mon May 12, 2003 8:49 pm

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue May 13, 2003 7:51 am

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Amir Aavani
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Sun Jul 04, 2004 6:14 am

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

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

Post by jjtse » Sun Oct 23, 2005 8:01 am

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

jjtse
Learning poster
Posts: 80
Joined: Mon Aug 22, 2005 7:32 pm
Location: Nevada, US
Contact:

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

Post by jjtse » Sun Oct 23, 2005 8:22 am

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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Thu Dec 27, 2007 11:26 am

I used brute force and getting TLE ..
how did u people try it ?
can u explain ur strategy here ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

obbY
New poster
Posts: 5
Joined: Sun May 16, 2010 11:41 pm

Re: 10146 - Dictionary

Post by obbY » Thu Jun 10, 2010 8:30 pm

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..

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10146 - Dictionary

Post by brianfry713 » Wed Jan 11, 2012 11:34 pm

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”