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

zakaria
New poster
Posts: 15
Joined: Thu Jun 27, 2002 11:34 pm

455 - Periodic Strings

Post by zakaria » Sat Jun 29, 2002 5:25 am

Pleaes tell me the fault of this code.
Why it is W.A??

#include<iostream.h>
#include<string.h>
int main()
{


char t[100];
int r;
while(cin>>t)
{
int s=strlen(t);
char p[100];
char ch[2]={0};
ch[0]=t[0];

strcpy(p,ch);
int i;
for(i=1,r=1;i<s;i++,r++)
{
int l,k=1,count,max,index=0,b=0;
max=s-r+1;
while(k<=max)
{
l=1;
count=0;
while(l<=r)
{
if(p[l-1]!=t[k+l-1-1])goto a;
else count++;
l++;
}
a: k++;
if(count==r)
{
b++;
index=b;
}
}
if(index*r==s)break;
ch[0]=t;
strcat(p,ch);
}
cout<<r<<"\n";
}
return 0;
}

Picard
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Tue Jul 02, 2002 9:57 pm

this problem has multiple input, first read the number of strings follow.
http://acm.uva.es/problemset/minput.html

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

455 Periodic Strings

Post by hank » Tue Jul 23, 2002 8:24 am

What's wrong in my program?

I got WA.

I cannot find the fault

help me

thanks!

Here is my source.
----------------------------
#include "stdio.h"
#include "string.h"
void main()
{
int i,j,n,t,r,z;

char arr[100],brr[100];
scanf("%d\n",&r);
for(z=1;z<=r;z++)
{
scanf("\n");
gets(arr);
for(i=0;i<strlen(arr);i++)
{
n=i+1;
for( j=0 ;j<=i ; j++ )
brr[j]=arr[j];


for(j=i+1;j<strlen(arr);j++)
{
brr[j]=brr[j%n];
}

brr[j]=0;



if(strcmp(arr,brr)==0)
{
printf("%d\n\n",n);
break;
}
}

}

}

Suman (SUST)
New poster
Posts: 1
Joined: Sun Aug 18, 2002 4:31 am

Why WA?

Post by Suman (SUST) » Sun Aug 18, 2002 4:38 am

My code is :
[c]
#include<stdio.h>
#include<string.h>

void main()
{
char string[81];

int period=0,N,counter,length,index,flag;

scanf("%d",&N);

for(counter = 1; counter <= N; counter++)
{
scanf("%s",&string);

length = strlen(string);

for(index = 0; index < length; index++)
{
period++;

if(string[0] == string [index+1])
{
printf("%d\n",period);
flag = 1;
break;
}
else
flag = 0;
}
if(flag == 0)
{
printf("%d\n",length);
break;
}
if(counter < N)
printf("\n");
period = 0;

}
}[/c]

Can anybody help me?

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post by Maxim » Wed Sep 04, 2002 11:23 pm

Consider this string.

HoHaHo

Your program would output 2, and that's not solution. You have to make strlen(string)/k passes ( for k = 1..strlen(string) ) and ensure that every consecutive part of k characters is equal to the first one of length k.

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

p455 any special input?

Post by the LA-Z-BOy » Sun Oct 06, 2002 1:22 pm

i got p10298(power strings) accepted but i get WA for p455 using the same algo.
can anyone tell me if there is any special input for this prob?
:roll:
thanks in advance :wink:
im the lazy lazy boy

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

Post by Noim » Mon Oct 14, 2002 8:16 am

what is the output of your program for the input...

mangomangomangom

your program will answer 5

But the real answer is 16
:roll:

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

Post by Noim » Fri Oct 18, 2002 5:25 pm

Have you conseder Multiple input for this problem
Besides this , Your source code need to be shown.
:roll:
__nOi.m....

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 » Sat Oct 19, 2002 12:37 pm

i am sure 'bout the fact that my code to get the period is right, because is just said that i got p10298 accepted. :wink:

and i'm also aware that this is a mulinput problem. plz see the part the ways i take the data...

[c]
int main(){
char fstr[101];
long powerS, mulinput;

fgets(fstr, sizeof(fstr), stdin);
sscanf(fstr, "%ld", &mulinput);
fgets(fstr, sizeof(fstr), stdin);

while(mulinput){
fgets(fstr, sizeof(fstr), stdin);
sscanf(fstr, "%s", str); /* str[1005] is global */
fgets(fstr, sizeof(fstr), stdin); /* track the blank line */
powerS = get_power();
printf("%ld\n", powerS);
mulinput--;
}
}
[/c]

and i've also tried with

[c]
int main(){
char fstr[101];
long powerS, mulinput;

fgets(fstr, sizeof(fstr), stdin);
sscanf(fstr, "%ld", &mulinput);
fgets(fstr, sizeof(fstr), stdin);

while(mulinput){
while(fgets(fstr, sizeof(fstr), stdin)!=NULL){
if (!fstr[0] || fstr[0]=='\n')
break;
sscanf(fstr, "%s", str); /* str[1005] is global */
powerS = get_power();
printf("%ld\n", powerS);
}
mulinput--;
}
}
[/c]

so what now? :(

Doodge
New poster
Posts: 4
Joined: Sun Aug 04, 2002 5:24 pm
Location: Poland
Contact:

Post by Doodge » Wed Jan 01, 2003 1:20 pm

I have some problems with this program :cry: it gots WA, but I have no idea why :P Here's my source, maybe You can find the bug, because i have spent a lot of time on searching it, but i haven't found it. Maybe it's a problem with input?


[cpp]// Periodic Strings
#include <iostream.h>
#include <string.h>

char word[100];
int numoftests;

void check()
{
int length=1;
for (int i=1; i<strlen(word); i++)
if (word!=word[i-length])
length=i;
if (strlen(word)%length) length=strlen(word);
cout << length;
}

int main()
{
cin >> numoftests;
for (int i=0; i<numoftests; i++)
{
cin >> word;
if (i) cout << "\n\n";
check();
}
return 0;
}[/cpp]

Thanx[/cpp]
Doodge
-------------------------------------------------------
Things should be as simple as only possible, but no simpler.

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Wed Jan 01, 2003 6:43 pm

Try an input file like:
1

ooHooH
and you output 6, not 3.

Changing
[cpp]
if (word!=word[i-length])
length=i;
[/cpp]
to
[cpp]
if (word!=word[i-length])
length=i + 1;
[/cpp]
fixes this problem.

Doodge
New poster
Posts: 4
Joined: Sun Aug 04, 2002 5:24 pm
Location: Poland
Contact:

Post by Doodge » Wed Jan 01, 2003 9:06 pm

Thx for Your help, but it still gots WA.
Doodge
-------------------------------------------------------
Things should be as simple as only possible, but no simpler.

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Thu Jan 02, 2003 3:55 am

Sorry. I was worried that your method wasn't quite right, but I couldn't think of a case where it gave the wrong answer, so I hoped it would work. :) A bit of thought is needed to find a counterexample:

Input:
1

abaaababaaab
The output should be 6, not 12. Tracing through check(), length goes from 2 -> 4 -> 8 -> 10. But 12 % 10 is 2, so it outputs 12 even though the right answer is 6.

Offhand, I can't think of an easy way to fix this without totally rewriting your check() method. :(

Doodge
New poster
Posts: 4
Joined: Sun Aug 04, 2002 5:24 pm
Location: Poland
Contact:

Post by Doodge » Thu Jan 02, 2003 8:10 pm

thanks. i wasn't sure that the method isn't good, but i couldn't find any inouts giving wrong answers. you found it. i'm really grateful.
Doodge
-------------------------------------------------------
Things should be as simple as only possible, but no simpler.

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

wonder what's wrong here

Post by zsepi » Tue Feb 18, 2003 9:36 am

hello all,
I'm wondering why I got stuck on this problem... Is there some fancy input I don't handle quite right or I don't handle the multiple input well enough?
all comments are appreciated
[c]#include <stdio.h>
#include <string.h>
#define MX 81

int comp(char *what,char *where,int l) {
int i=0;
while(i<l && what==where) i++;
return i==l;
}

main() {
char s[MX],tmp[MX],*p;
int i,j,L,N;

scanf("%d",&N);
while(N>0) {
scanf("%s",&s);
L=strlen(s);
for(i=1,j=1;j && i<L;i++) {
tmp[i-1]=s[i-1];
if(L%i==0) {
j=L/i-1;
p=&s;
while(j>0 && comp(tmp,p,i)) {
j--;
p=&p;
}
}
}
printf("%d\n",(i==L)?L:i-1);
if(--N) printf("\n");
}
}[/c]
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

Post Reply

Return to “Volume 4 (400-499)”