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

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon Jan 23, 2006 7:13 am

Try the following test case:

Code: Select all

4

HoHoHo

abcabc

HoHoHo

the cat ran out
Correct output is:

Code: Select all

2

3

2

15
But your code gives:

Code: Select all

2

3

2

100
edited: Input format was wrong. Now it's corrected. There are some test cases from past threads.
Last edited by chunyi81 on Mon Jan 23, 2006 8:05 am, edited 2 times in total.

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

Post by Wei-Ming Chen » Mon Jan 23, 2006 7:45 am

But the problem said:
"Two consecutive input will separated by a blank line."

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Mon Jan 23, 2006 8:05 am

Sorry about that. I have corrected the test case. Check the new test case I have posted. Your code gives wrong output.

Test case from a past thread:

Code: Select all

10

abaaababaaab

ooHooH

abaaababaaab

b  aab  aa

ababc

hohoho

ababcababc

asdfgh

rrr rrr zzz rrr rrr zzz

HoHaHo
Correct output is:

Code: Select all

6

3

6

5

5

2

5

6

23

6
But your code prints:

Code: Select all

6

3

6

5

5

2

5

6

23

100

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

Post by Wei-Ming Chen » Mon Jan 23, 2006 8:32 am

I changed my code, so it could said "6" in last ouput
But still got WA.......

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

455 brute force

Post by temper_3243 » Tue Aug 29, 2006 4:23 pm

Hi,
I have a problem. I have got it accepted for 455 with the below algorithm.

for (len=1 ; len < stringlen ;len++)
check(string,len);

check function checks if string has a period of len.

This algorithm has o(n^3) because check has o(n^2) (one for loop and one strcmp inside the for loop), this is really brute force and i don't think i have accomplished anything by solving this problem . I want to do it for strings of length 1000 and if possible 10^6.

How can we find the smallest period of a string in better time. Can someone point to me better algorithm and links.



Thanks
Nik

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Location: Bangladesh
Contact:

Post by DP » Wed Aug 30, 2006 8:05 pm

hmm...
I solved it first time with O(n^3).
After that i solved it with O(n^2). So try to think about this ORDER.

hope this will help you more. ;)

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by algoJo » Sun Jan 21, 2007 6:02 pm

I've checked my program with inputs from this board and it gave the correct outputs but it continue to WA...
can anybody give me some hint...

Code: Select all

Removed
and is it right if
INPUT

Code: Select all

1

aaaaaaaaaaaa
OUTPUT

Code: Select all

1
Last edited by algoJo on Mon Jan 22, 2007 12:09 am, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jan 21, 2007 11:22 pm

Try the following case

Input:

Code: Select all

1

ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ
Output:

Code: Select all

1
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

Post by algoJo » Sun Jan 21, 2007 11:35 pm

Thanks for ur reply Jan :P
finally AC

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Jan 21, 2007 11:41 pm

You should remove the faulty I/O set, too. The output should be 1.
Ami ekhono shopno dekhi...
HomePage

Amin.Abouee
New poster
Posts: 1
Joined: Fri May 18, 2007 11:37 am

455 Why PE

Post by Amin.Abouee » Fri May 18, 2007 11:43 am

My output is correct But my output format is wrong

#include <iostream>
#include <string>
using namespace std;

int main()
{
string sta="";
string temp="";
string test="";
size_t equal=0;
size_t size_temp=0;
size_t size_sta=0;
bool status;
int T;
int pass=0;
cin>>T;
getline(cin,sta);
cout<<endl;
while (getline(cin,sta))
{
if(sta=="")
{
cout<<endl;
pass++;
continue;
}
status =false;
size_sta=sta.length();
for (size_t i=1;i<size_sta && status==false;i++)
{
if (sta==sta[0])
{
temp=sta.substr(0,i);
size_temp=temp.length();
if (size_sta%size_temp!=0)
continue;
else
{
equal=size_sta/size_temp;
for (size_t j=1;j<equal;j++)
{
size_t p=(i*j);
test=sta.substr(p,i);
if (test==temp)
{
status=true;
continue;
}
else
{
status =false;
break;
}
}
}
}
}
if (status==true)
cout<<size_temp;
else
cout<<size_sta;
if (pass!=T)
cout<<endl;
}
return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri May 18, 2007 5:22 pm

Search the board first. Don't open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

yesacm91
New poster
Posts: 1
Joined: Fri Mar 07, 2008 2:09 pm

455 - you can use this kind of IO format (Accepted)

Post by yesacm91 » Fri Mar 07, 2008 9:17 pm

After tring several times in the IO test, I find that we don't have to deal with the following situation

Code: Select all

1

a  ba  b
For those who do not know the IO format, you can try the format below.

Code: Select all

#include<stdio.h>
/*455*/
int main(){
  int n, period;
  char str[200];
  /*write what you want*/

  scanf("%d", &n);

  while(n--){
    scanf("%s", str);
	
    /*write what you want..*/


    printf("%d\n", period);

    if(n > 0) /*<--important*/
        printf("\n");
  }

  return 0;
}
Best Regards,
yesa

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Mar 11, 2008 5:08 pm

Use an existing thread.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: Help with 455

Post by Obaida » Wed Jan 21, 2009 10:01 am

It seems i must have the wA.
I tested all the cases but still WA. please help me. :x :x

Code: Select all

removed
Last edited by Obaida on Thu Jan 22, 2009 11:24 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

Post Reply

Return to “Volume 4 (400-499)”