10602 - Editor Nottoobad

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

Moderator: Board moderators

DreamLinuxer
New poster
Posts: 8
Joined: Tue Oct 01, 2002 3:22 pm

10602 - Editor Nottoobad

Post by DreamLinuxer » Thu Jan 29, 2004 9:53 am

Can anybody give me some hint
thx.

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

Post by Dmytro Chernysh » Thu Jan 29, 2004 2:38 pm

Sorting...

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Thu Jan 29, 2004 3:31 pm

Dmytro Chernysh wrote:Sorting...
Could you give more hints?

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

Post by titid_gede » Thu Jan 29, 2004 3:48 pm

greedy :D
Kalo mau kaya, buat apa sekolah?

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

Post by Dmytro Chernysh » Thu Jan 29, 2004 3:53 pm

Who or what? Me or the algorithm? :D

DreamLinuxer
New poster
Posts: 8
Joined: Tue Oct 01, 2002 3:22 pm

Post by DreamLinuxer » Thu Jan 29, 2004 5:40 pm

Dmytro Chernysh wrote:Who or what? Me or the algorithm? :D
algorithm :)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Thu Jan 29, 2004 6:15 pm

titid_gede wrote:greedy :D
I also use greedy and get wrong answer.
what is your greedy algorithm?

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Thu Jan 29, 2004 6:23 pm

Cost is the number of keys should need to type, so better not to delete any letter you'll need later. You want to group the words that have common letters at the start. Sort by # of common letters with the first word and then lexicographically (sp?)

Saludos,
HoraPe

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Thu Jan 29, 2004 7:07 pm

horape wrote:Cost is the number of keys should need to type, so better not to delete any letter you'll need later. You want to group the words that have common letters at the start. Sort by # of common letters with the first word and then lexicographically (sp?)

Saludos,
HoraPe
I don't understand your meaning clearly, could you talk more detail ?

User avatar
horape
New poster
Posts: 49
Joined: Sat Sep 13, 2003 3:18 pm
Location: Buenos Aires

Post by horape » Thu Jan 29, 2004 7:15 pm

windows2k wrote:
horape wrote:Cost is the number of keys should need to type, so better not to delete any letter you'll need later. You want to group the words that have common letters at the start. Sort by # of common letters with the first word and then lexicographically (sp?)

Saludos,
HoraPe
I don't understand your meaning clearly, could you talk more detail ?
Let's see if an example makes it clearer:

Code: Select all

abcdef
aasda   1
aafgh   1
abcjkl  3
ghy     0
aafyy   1
abcghj  3
uiop    0
abcdef is the first word, order by number or common letters with it (the number at the right of the words) and break ties lexicographycally.

Code: Select all

abcdef
abcjkl     3
abcghj     3
aafgh      1
aafyy      1
aasda      1
ghy        0
uiop       0
Is it clearer now?

Saludos,
HoraPe

User avatar
_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

Good idea.

Post by _.B._ » Sat Mar 20, 2004 9:15 pm

Good idea HoraPe!.
I think it'll make things work faster.
Will work on it now.

_.B._
http://online-judge.uva.es/cgi-bin/Onli ... Info:42085

rasel04
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

Always WA

Post by rasel04 » Sat Apr 17, 2004 2:08 am

Why I got WA.Please check my code.

Code: Select all

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

struct T
{
	char str[105];
	int value;
}s[105];

int sfunc(void const *a,void const *b)
{
	T p,q;
	int l1,l2;
	p=*(T *)a;
	q=*(T *)b;
	
	l1=strlen(p.str);
	l2=strlen(q.str);
	if(p.value==q.value)
	{
		if(l1==l2) return (strcmp(q.str,p.str));
		return (l2-l1);
	}
	
	return (q.value-p.value);
}

void main()
{
	
	int testcase,N,i,l,l1,l2,k1,k2,c,count;
	char str[105];
	//freopen("10602.in","r",stdin);
	scanf("%d",&testcase);
	while(testcase--)
	{
		scanf("%d",&N);
		scanf("%s",str);
		l=strlen(str);
		strcpy(s[0].str,str);
		s[0].value=l;

		for(i=1;i<N;i++)
		{
			scanf("%s",str);
			strcpy(s[i].str,str);
			l1=strlen(str);

			k1=k2=count=0;
			while((s[0].str[k1]==s[i].str[k2]) && k1<l && k2<l1)
			{
				count++;
				k1++;
				k2++;
			}

			s[i].value=count;		
		}

		qsort(s,N,sizeof(s[0]),sfunc);

		count=s[0].value;
		for(i=1;i<N;i++)
		{
			l1=strlen(s[i-1].str);
			l2=strlen(s[i].str);

			k1=k2=c=0;
			while((s[i-1].str[k1]==s[i].str[k2]) && k1<l1 && k2<l2)
			{
				k1++;
				k2++;
				c++;
			}
			count+=(l2-c);		
		}

		printf("%d\n",count);
		for(i=0;i<N;i++) printf("%s\n",s[i].str);
	}
}

bmouse001
New poster
Posts: 3
Joined: Mon Jun 14, 2004 2:41 pm

10602 Editor Nottobad, Any Critical I/O ?

Post by bmouse001 » Thu Jun 17, 2004 8:34 pm

I always got W.A. Is there any critical I/O ?
Here's my code:

[AC, code deleted]

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Mon Jul 19, 2004 9:37 pm

I am repeatedly getting WA in this problem but finally failed to figure out the reason. My code is as follows -
[cpp]

//AC. Code deleted
[/cpp]

Can anyone give me some tricky I/O please ?
You should never take more than you give in the circle of life.

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Tue Oct 12, 2004 11:12 pm

check for this input and output:
input:
1
2
ab
abc
output:
  • 3
    ab
    abc
__nOi.m....

Post Reply

Return to “Volume 106 (10600-10699)”