11151 - Longest Palindrome
Moderator: Board moderators
I'm not a C programmer, but I would imagine that mixing scanf() and gets() in the same code can just lead to a trouble. In Java I have two different routines for reading input - one reads it line by line (and I have to parse a line if I want a number of test cases, for example) and the other one behaves like scanf. I never use both at the same time.
But, I agree that the first case should not be an empty string, I think that it is a plus to know what scanf() does exactly, but it shouldn't be a part of the problem. Especially because judge uses an outdated compiler.
But, I agree that the first case should not be an empty string, I think that it is a plus to know what scanf() does exactly, but it shouldn't be a part of the problem. Especially because judge uses an outdated compiler.
Handling empty strings
Here's how I took care of input (in C++).
I originally got a wrong answer with cin>>S, but all problems disappeared after I recoded it using cin.getline. Hope this helps.
Code: Select all
int T;
cin>>T
cin.getline(S,MAX,'\n');
//This is just to get the rest of the line after T
while(T--)
{
cin.getline(S, MAX, '\n');
.......
}
aha
I usually avoid scanf or cin altogether for these cases.
This is how I do it.
Code: Select all
char str[10000];
gets(str);
sscanf(str, "%d", &n);
while(n--) {
gets(str);
process()
}
asd
hi,i'm still got WA...this is what i used at my code :
LCDlength -> Longest Common Sequence procedure..
thanks.
LCDlength -> Longest Common Sequence procedure..
Code: Select all
#include <stdio.h>
#include <string.h>
#define MAX 1001
char X[MAX],Y[MAX];
int i,j,m,n,c[MAX][MAX],b[MAX][MAX];
void main() {
freopen("lp.in","r",stdin);
freopen("lp.out","w",stdout);
int n;
scanf("%d\n",&n);
int i=0;
while(i<n){
gets(X);
int j =0;
int byk = strlen(X);
int awal = byk-1;
while(awal>=0){
Y[j] = X[awal];
j++;awal--;
}
Y[j]='\0';
printf("%d\n",LCSlength());
i++;
}
}
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Re: asd
Read previous posts, and take input carefully.darkos32 wrote:hi,i'm still got WA...this is what i used at my code :
LCDlength -> Longest Common Sequence procedure..
thanks.Code: Select all
Last edited by emotional blind on Fri Jan 05, 2007 7:09 am, edited 1 time in total.
asd
thanks...i got accepted...
-
- A great helper
- Posts: 383
- Joined: Mon Oct 18, 2004 8:25 am
- Location: Bangladesh
- Contact:
Re: asd
Now remove your code please.darkos32 wrote:thanks...i got accepted...
-
- Learning poster
- Posts: 63
- Joined: Tue Mar 07, 2006 6:51 pm
- Location: india
hi everybody i m trying to solve this problem but getting WA many times ...i m really frustrated ..plz help me..
my algorithm is i m trying to enumarate all the n*(n+1)/2 substrings ,where n is string size
and checking which one is palindrome ....in another post of this problem the output of string qweqweqwedadqweqweqwe is given 13 but my program gives 3 and substring is dad ...can some one explain me how is it 13 .....plz tell me my algorithm is correct or not
here is my code
my algorithm is i m trying to enumarate all the n*(n+1)/2 substrings ,where n is string size
and checking which one is palindrome ....in another post of this problem the output of string qweqweqwedadqweqweqwe is given 13 but my program gives 3 and substring is dad ...can some one explain me how is it 13 .....plz tell me my algorithm is correct or not
here is my code
Code: Select all
#include<stdio.h>
#include<string.h>
int chkpalin(char* a,int k,int n)
{
int w;
for(w=k;w<=n;w++)
if(a[w]!=a[n+k-w])
return(0);
return(1);
}
main()
{
char str[1010],c;
int i,j,k,n,w,v;
scanf("%d",&k);
getchar();
for(v=0;v<k;v++)
{
w=0;
gets(str);
n=strlen(str);
for(i=n-1;i>=0;i--)
{
for(j=0;j+i<n;j++)//enumarate all the n*(n+1)/2 substrings chk wheather a[j] to a[i+j] is palindrome or not
{
w=chkpalin(str,j,i+j);
if(w==1)
break;
}
if(w==1)
break;
}
printf("%d\n",i+1);
/printf("palindrome is \n");
for(int x=j;x<=i+j;x++)
printf("%c",str[x]);
printf("\n");*/
}
}
The answer for "qweqweqwedadqweqweqwe" is "qwqewdadweqwq"mukeshtiwari wrote:my algorithm is i m trying to enumarate all the n*(n+1)/2 substrings ,where n is string size
and checking which one is palindrome ....in another post of this problem the output of string qweqweqwedadqweqweqwe is given 13 but my program gives 3 and substring is dad ...can some one explain me how is it 13 .....plz tell me my algorithm is correct or not
So, the length is 13..
It doesn't need to be a consecutive substring.. so, you can remove letters at any points..
-
- Learning poster
- Posts: 63
- Joined: Tue Mar 07, 2006 6:51 pm
- Location: india
I am getting the same output but uva judge giving me wrong answer ![:lol:](./images/smilies/icon_lol.gif)
![:lol:](./images/smilies/icon_lol.gif)
Code: Select all
/* @JUDGE_ID: 60332ER 11151 Java "Easy algorithm" */
import java.io.*;
import java.util.*;
class Main{
static int[][] result;
static String ReadLn (int maxLg) {
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;
lin [lg++] += car;
}
}
catch (IOException e){
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}
static int max(int i, int j){
return ( (i>=j) ? i:j);
}
static int longest(String s,int i, int j){
if (i == j) return (result[i][j]=1);
else if ( i == j-1 ){
if(s.charAt(i) == s.charAt(j))
return (result[i][j]=2);
else return (result[i][j]=1); /* Main.max(Main.longest(s,i,j-1),Main.longest(s,i+1,j)); */
}
else if(s.charAt(i) == s.charAt(j)){
result[i][j]=2;
return (2+Main.longest(s,i+1,j-1));
}
else{
return Main.max((result[i][j-1]=((result[i][j-1]!=-1)? result[i][j-1] : Main.longest(s,i,j-1))),
(result[i+1][j]=((result[i+1][j]!=-1)? result[i+1][j]: Main.longest(s,i+1,j))));
}
}
public static void main (String args[]){
Main myWork = new Main();
myWork.Begin();
}
void Begin(){
String input;
int t,len,mid,i,j;
input = Main.ReadLn (255);
t=Integer.parseInt(input.trim());
/*System.out.println(); */
while (t!=0){
input = (Main.ReadLn (257)).trim();
len = input.length();
/* System.out.println(input+" "+input.length()); */
if ( len == 0 ){
System.out.print(0);
t--;
}
else if ( len == 1){
System.out.print(1);
t--;
}
else{
result = new int[len][len];
for(int m=0;m<result.length;m++){
for(int n=0;n<result[m].length;n++){
result[m][n] = -1;
}
}
System.out.print(Main.longest(input,0,len - 1));
t--;
}
if(t != 0)
System.out.print("\n");
}
}
}
-
- New poster
- Posts: 1
- Joined: Fri May 11, 2007 6:25 am
handling time limit on judge (I'm newbie)
solving #11151 problem...
I completed source code
found none of any faulty in my view
using only stdin(cin.getline), stdout(cout)...
like this...
while(true) {
- type input - (cin.getline)
- processing input - (algorithm for #11151)
- print output - (cout)
}
online judge system only gives me "Time Limit" msg repeatedly
like... 10.035 secs (I know the limit is 10 secs)
I think this is not a time limit exceed problem.
Maybe I need to modify "while ~ code" for this problem
anyone help me to handle this time limit?...
have a lucky day !
I completed source code
found none of any faulty in my view
using only stdin(cin.getline), stdout(cout)...
like this...
while(true) {
- type input - (cin.getline)
- processing input - (algorithm for #11151)
- print output - (cout)
}
online judge system only gives me "Time Limit" msg repeatedly
like... 10.035 secs (I know the limit is 10 secs)
I think this is not a time limit exceed problem.
Maybe I need to modify "while ~ code" for this problem
anyone help me to handle this time limit?...
have a lucky day !
-
- New poster
- Posts: 14
- Joined: Mon Sep 03, 2007 10:11 am
- Contact: