455 - Periodic Strings

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

Moderator: Board moderators

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Post by Nick » Mon Mar 24, 2003 5:12 am


nrkt
New poster
Posts: 2
Joined: Sat Jul 19, 2003 2:30 pm
Contact:

Problem 455: WA

Post by nrkt » Sat Jul 19, 2003 2:40 pm

I can't get what's wrong with this code:

[java]
import java.io.*;

class Main {

static String read() {
int maxLg = 255;
byte lin[] = new byte[maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
if (car != 13)
lin [lg++] += car;
}
}
catch (IOException e) {
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

static int smallestPeriod(String input) {
for (int i = 1; i<= input.length(); i++) {
String temp = input.substring(0,i);
String ris = "";
int x = temp.length();
while (ris.length() < input.length()) ris += temp;
if (ris.equals(input)) return x;
}
return 0;
}

static void main(String[] args) {
int multinput = Integer.parseInt(read());
for (int i=0; i<multinput; i++) {
String input = read();
System.out.println(smallestPeriod(input));
}
}
}
[/java]

According to the Online Judge, it does not solve problem 455.
Could anybody help me plz? Thanx a lot

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Sun Jul 27, 2003 11:24 am

shouldn't the main() method be public?
moreover this is a multiple input problem... you're not handling it accordingly. the input is formed something like this..

Code: Select all

3

Hello

HoHoHo

ByeByeByeNot
so you have to track blank lines at each input block...
[java] public static void main(String[] args) {
int multinput = Integer.parseInt(read());
for (int i=0; i<multinput; i++) {
String dummy = read(); // take the blank line
String input = read();
System.out.println(smallestPeriod(input));
}
}[/java]
Greetings :)
Istiaque Ahmed [the LA-Z-BOy]

nrkt
New poster
Posts: 2
Joined: Sat Jul 19, 2003 2:30 pm
Contact:

Post by nrkt » Sun Jul 27, 2003 10:24 pm

thanx a lot LA-Z-BOy, I corrected it the way you suggested and it ran ok

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

455, need some sample input

Post by Bug! » Sun Jan 04, 2004 6:47 am

Hi all :D .
I've read all the previous topic about this one, and i've tried all the given input, n the output is correct. But I still got WA for this problem. I've got WA for about 6 times. :cry: Hope I can get another sample input

input:

Code: Select all

5

HoHoHo
dodoldudulzz
mangomangomangom
dodod

abcabcabcabc

HoHaHo

ooHooH

abaaababaaab
output:

Code: Select all

2
12
16
5

3

6

3

6
Is it correct??

Thanx, regard
Andre

Bug!
New poster
Posts: 24
Joined: Thu Oct 30, 2003 10:19 am

Post by Bug! » Sun Jan 04, 2004 7:01 am

And This is my code

Code: Select all

got ac now

rezwana
New poster
Posts: 3
Joined: Wed Feb 18, 2004 7:30 am

why WA 455

Post by rezwana » Mon Mar 08, 2004 6:55 am

is the way of taking multiple input correct?

But when i run my program it stops execution after one "end of file"
input.

Anyway my code shows correct answers for

abaaababaaab
6
mangomangomangom
16
ababc
5
hohoho
2
ababcababc
5
asdfgh
6


i think the prob is in the way of taking multiple input

plz HELP

my code is here


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

char str[100],temp[100];
int p,pr,prlen,index;
int fstrcmp(){
int j,k;
pr=0;
index=p+strlen(temp);
for(j=0,k=p;temp[j];j++,k++)
if((temp[j]-str[k])!=0)
{ pr=1;
index=k;
break;}
return pr;
}

int main(){
int i,len,flag=0,t,m;
char ch;
scanf("%d",&t);
for(m=0;m<t;){
while(NULL!=gets(str)){
temp[0]='\0';
flag=0;
len=strlen(str);
prlen=len;

ch=str[0];
i=1;
while(str){
if(str==ch)
{ flag=0;
p=i;
strncpy(temp,str,i);
temp='\0';
if(len%p==0)
{
if(fstrcmp()==0)
{
for(p=2*i;p<len;p=p+i)
if(fstrcmp()!=0)
{ flag=1;
break;}
if(flag==0)
{prlen=i;
break;}
else
i=index+1;
}
else
i++;
}
else
i++;
}
else
i++;
}
printf("%d\n",prlen);
}
m++;
}
return 0;
}

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Mon Mar 08, 2004 8:42 am

It seems to me that, you didn't handle multiple input properly. There are blank lines between the cases, and for those strings, your program will produce 0 as output.

rezwana
New poster
Posts: 3
Joined: Wed Feb 18, 2004 7:30 am

WHY wa 455

Post by rezwana » Tue Mar 09, 2004 5:09 am

hi,

i know there is prob in taking multiple input.
i want to know the solution.

CAN ANYONE HELP ME PLZ.

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

455 please help me!!!

Post by oulongbin » Sun Jul 11, 2004 8:36 am

[cpp]
#include <iostream>
using namespace std;
#include <cstring>
int main()
{
int n,l,j,i,count,m;
char a[1000];
cin>>n;
cin.get();
for(int sum=0;sum<n;)
{
cin.getline(a,1000);
if(a[0]=='\0')
{sum++;cout<<endl;}
else
{
l=strlen(a);

if(l%2==0)
{
count=0;
for(i=2;i<=l;i++)
{
if(l%i==0)
{
for(j=0;j<l/i;j++)
{
if(a[j]==a[j+l/i]){}
else break;
}
if(j==l/i)
{
for(m=1;m<i;m++)
{
if(a[0]==a[m*j]){}
else
break;
}
if(m==i)
count=j;
}

}
}
if(count==0)
count=l;
cout<<count<<endl;
}

else
{
count=0;
for(i=1;i<l;i+=2)
{
if(i==1)
count=l;
else
{
if(l%i==0)
{
for(j=0;j<l/i;j++)
{
if(a[j]==a[j+l/i]){}
else
break;
}
if(j==l/i)
count=j;
else
break;
}
}
}
for(i=1;i<strlen(a);i++)
{
if(a==a[0]){}
else break;
}
if(i==strlen(a))
count=1;

cout<<count<<endl;
}
}
}
return 0;
}
[/cpp]

i do not know why i always geo WA.i think its right.
please help me.
thank you !

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Thu Apr 28, 2005 4:03 pm

Hello, I need some sample I/O

Here is some sample Input and the Output from my WA program.

Code: Select all

10 

abaaababaaab

ooHooH

abaaababaaab 

b  aab  aa

ababc 

hohoho 

ababcababc 

asdfgh

rrr rrr zzz rrr rrr zzz

HoHaHo

Output

Code: Select all

6

3

13

5

6

7

11

6

23

6
I tried also not to print blank lines between consecutive OUTPUTs
but that also resulted in WA. Any help will be highly appreciated.

Thanks in advance.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Thu Apr 28, 2005 6:57 pm

The output of my accepted program is quite different from yours:

Code: Select all

6

3

6

5

5

2

5

6

23

6
Maybe you have some problems with reading input, or misunderstood the problem. Shouldn't it be obvious that for "hohoho" the answer is 2? This example modulo case is given in the sample input/output.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Apr 29, 2005 12:49 am

Hi, mf!

Firstly thanks for looking into my problem.

Note that I've had one trailing space on each line of
my sample input. That's why I was getting these
strange results. Sorry for posting them !

Now for the same input ( without any trailing spaces )
I get the following output

Code: Select all

6

3

6

5

5

2

5

6

23

6
As you can see it is absolutely the same as yours. Why do I get WA
then. Currently I have no idea.
Do you have any idea ?

Some tricky input ?

By the way for this problem my program is in Java so I doubt
that I read the input in a wrong way, I've done it a lot
of times.

One question: Can we assume the line which comes from
the stdin has no leading or trailing blanks ( blanks are not
only SPACEs but also TABs for instance ).

I have no idea, can we have such input ?!

Can we also an input in which our input line is just empty.
I mean something like:

Code: Select all

line1
empty line 
empty line 
empty line
line3

And more thing - is 80 really the maximum
length of the input lines ?

If you also have no idea of what is wrong can you just give
me some more test cases. I hope some of them could reveal some
BUG program has.
Last edited by Sedefcho on Fri Apr 29, 2005 1:18 am, edited 1 time in total.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Fri Apr 29, 2005 1:17 am

I've found my BUG. It was very stupid one.

I have a precheck where I test if my string is such that
it's period is 1. So I test if the string contains only one symbol.

But I was forgetting its last symbol ( just a stupid
typing mistake which made my program miss the last
symbol of the string ).

So for inputs like AB, AAB, AAAB my program was giving
an answer of 1 although the correct answer is N where N is the
length of the string ( AB -> 2, AAB -> 3, AAAB -> 4 ).

The reason we did not manage to notice this before, is that there
were no such cases in the test input I've posted above. I mean cases
where all symbols are equal and just the last one is different.

Pretty stupid, I know. To mf : thanks once again.

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

455 WA Please help me

Post by Wei-Ming Chen » Mon Jan 23, 2006 4:30 am

Ac now, thanks everyone's help.
Last edited by Wei-Ming Chen on Mon Jan 30, 2006 7:22 pm, edited 2 times in total.

Post Reply

Return to “Volume 4 (400-499)”