632 - Compression (II)

[anupam]

Code: Select all

#include<stdio.h>
#include<string.h>
#define N 5000
main()
{
	char a[N],b[N][N],tmp[N],q[N];
	int cas,i,j,z,n,m;
	scanf("%d",&cas);
	for(z=0;z<cas;z++)
	{
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%c",&a[i]);
			if(a[i]=='\n') i--;
		}
		a[n]=m=0;
		strcpy(b[m++],a);
		for(i=0;i<n-1;i++)
		{
			for(j=0;j<n-1;j++)
				b[m][j]=b[m-1][j+1];
			b[m][n-1]=b[m-1][0];
			b[m][n]=0;
			if(m==1) strcpy(q,b[m]);
			m++;
		}
		for(i=0;i<n-1;i++)
		{
			m=i;
			for(j=i+1;j<n;j++)
				if(strcmp(b[j],b[m])<1)
					m=j;
			if(m!=i)
			{
				strcpy(tmp,b[m]);
				strcpy(b[m],b[i]);
				strcpy(b[i],tmp);
			}
		}
		for(i=0;i<n;i++)
			if(!strcmp(q,b[i])) break;
		printf("%d\n",i);
		for(i=0;i<n;i++)
			printf("%c",b[i][n-1]);
		printf("\n");
		if(z!=(cas-1)) printf("\n");
	}
	return 0;
}

this is the prob. i have faced wa sev. times.
any 1 help me?

thanks[/b]

[the LA-Z-BOy]

i haven't watched your code totally but what i got is that you haven't read the whole problem statement yet! anyway read it again, you're not handling the input and not giving output as desired.

ps. was it proper place to post this?

[anupam]

Sorry Bos,
Ext. sorry to post it here.
actually, i can't understand sometime how to post in the perfect place in board.
actually internet is very expensive in our country. that is why we all get little time to view or post a post.
please don't mind.

[Ryan Pai]

The string can have spaces. That irked me. Don't let it irk you.

[harlock]

Hi, I don't undestand cause I get WA in this problem. Can I use the function strcmp to solve this problem or should i make my own comparation function ?

if i need make mi own comparation function, is the space before any letter o digit like in ASCII ?

here is my code:

Code: Select all

Cut after AC

I don't print the output like the problem say (each line should contain exactly 50 characters, except last), but if mi program is ok then i must get presentation error.

Thanks,

(Sorry for my bad english)

[LPH]

can someone who had got AC on this problem give the answer to the following test data?

Code: Select all

2

5
aaaaa
12
abcabcabcabc

mine got:

Code: Select all

1
aaaaa
4
ccccaaaabbbb

is that right?

[mf]

My output for LPH's input:

Code: Select all

1
aaaaa

4
ccccaaaabbbb

Hi, I don't undestand cause I get WA in this problem. Can I use the function strcmp to solve this problem or should i make my own comparation function ?

if i need make mi own comparation function, is the space before any letter o digit like in ASCII ?

You should compare by the ASCII values, and you may use standard functions like strcmp() or memcmp().

I don't print the output like the problem say (each line should contain exactly 50 characters, except last), but if mi program is ok then i must get presentation error.

Don't do that. The judge is pretty sensitive to where you break the lines, and you are more likely to get WA, than PE.

[harlock]

Thanks, you're rigth,

The judge is pretty sensitive to where you break the lines, and you are more likely to get WA, than PE.

i got AC when I make my output like the problem say.

[LPH]

OK, now i see the sort should be a stable one.

Well, originally i think the bug is at the case that has the length 1, but after i tried some data, i found out that it's fgets() that gives bug to my program

i tried this one on my program:

Code: Select all

1

52
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwx
yz

but when i keyed in the first line, my bad program gave the (bad) output immediately. later i found out it's because i provided 50 in fgets() as a maximum reading limit, but it only reads 49 characters. even 51 isn't work, maybe it's because there's a newline after those characters. so i change it into gets(), then got AC.

BTW, for my original problem, there's no test datas that has length only one. (besides, it shouldn't present. what is the position of s1 when there's no s1?)

and, for the input above, the output is:

Code: Select all

2
zzaabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxx
yy

[sumankar]

Problem statement says...

Each line (besides the last one) should contain exactly 50 characters.


Does that mean after printing the position of Si we print some blank lines
and then so on for the string iff its length < 50 ?

Regards,
Suman.

[LPH]

Problem statement says...

Each line (besides the last one) should contain exactly 50 characters.


Does that mean after printing the position of Si we print some blank lines
and then so on for the string iff its length < 50 ?

Regards,
Suman.

No. You don't have to fill any blanks or print newlines after the number.
The statement you quoted above is talking about the string, not the number.

[zerg]

Hi! I need help with problem 632 - got WA, and cant understand why. My code:

Code: Select all

import java.io.IOException;
import java.util.StringTokenizer;


class Main {


    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-1));
    }

    public static void main(String args[]) {
        Main myWork = new Main();
        myWork.start();
    }

    void start() {
        StringTokenizer t;
        int dataset_num = -1, str_len = -1;
        String str;
        String s = Main.ReadLn(255);
        //System.out.println(s.length());
        dataset_num = Integer.valueOf(s.trim()).intValue();
        Main.ReadLn(255);
        for (int i = dataset_num; i > 0; i--) {

            str_len = Integer.valueOf(Main.ReadLn(255).trim()).intValue();
            str = getStr(str_len);
            performCalculations(str);
        }
    }

    private void performCalculations(String str) {
        if (str.length()>1) {
            String arr[] = new String[str.length()];
            arr[0] = str;
            String new_str = str;
            for (int i = 1; i < str.length(); i++) {
                new_str = leftShift(new_str);
                arr[i] = new_str;
                //System.out.println(i+" str-"+arr[i]);
            }
            String s1 = arr[1];
            sort(arr);
            int indx = -1;
            String rez_str = getRezStr(arr);
            if (rez_str.equals(s1)) indx = 1;
            else
                indx = find(arr, s1);

            System.out.println(indx);
            specialPrint(rez_str);
            System.out.print("\n\n");
        } else {
            System.out.println("0");
            System.out.println(str);
            System.out.println("");
        }

    }

    private void specialPrint(String rez_str) {
        for (int i = 0; i < rez_str.length(); i++) {
            if (i % 50 == 0 && i != 0) System.out.print("\n");
            System.out.print(rez_str.charAt(i));
        }
    }

    private String getRezStr(String[] arr) {
        String rez = "";
        for (int i = 0; i < arr.length; i++) {
            String s = arr[i];
            rez += s.substring(s.length() - 1);
        }
        return rez;
    }

    private int find(String[] arr, String s1) {
        int rez = -1;
        for (int i = 0; i < arr.length; i++)
            if (arr[i].equals(s1)) {
                rez = i;
                break;
            }
        return rez;
    }

    private void print(String[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);

        }
    }

    private void sort(String[] arr) {
        for (int i = arr.length; i > 0; i--)
            for (int j = 0; j < i - 1; j++)
                if (arr[j].compareTo(arr[j + 1]) > 0) {
                    String tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
    }

    private String leftShift(String str) {
        return str.substring(1, str.length()) + str.substring(0, 1);
    }

    private String getStr(int length) {
        String rez = "";
        String input;
        int len = 0;
        while ((input = Main.ReadLn(255)) != null) {
           String s = input.substring(0, input.length());
            rez+=s;
            len += s.length();
            if (len >= length) break;
        }
        return rez.substring(0, length);
    }

}

Input example:

Code: Select all

4

1
a
5
aaaaa
12
abcabcabcabc
55
12345678901234567890123456789012345678901234567890
12345

Corresponding output:

Code: Select all

0
a

1
aaaaa

4
ccccaaaabbbb

16
99999000005111111222222333333444444555556666677777
88888

Could anyone help me? What is wrong in my solution? Thanks.

[sclo]

I'm too lazy to go through java codes.
Also your inputs are not valid since there must be a blank line between each case.
Anyway, here's the correct output.

Code: Select all

1
a

4
aaaaa

7
ccccaaaabbbb

16
99999000005111111222222333333444444555556666677777
88888

[shakil]

Why TLE??? I do not understand.....
Please help........

Code: Select all

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


struct T
{
	char si[2000];
	long in;
};

int cmp( const void *a, const void *b )
{
	T *p = (T *)a;
	T *q = (T *)b;
    if(strcmp(p->si,q->si)>0)
	return 1;
	return 0;
}


void main()
{
long cas,cas1,M,m,i,j;
char sa[2000],temp[2000],ch;
T a[2000];
scanf("%ld",&cas);

for(cas1=1;cas1<=cas;cas1++)
{
if(cas1!=1)
printf("\n");
scanf("%ld",&m);
scanf("%s",sa);
M=strlen(sa);
while(M!=m)
{
scanf("%s",&temp);
strcat(sa,temp);
M=strlen(sa);
}

strcpy(a[0].si,sa);
a[0].in=0;

for(i=1;i<m;i++)
{
ch =a[i-1].si[0];
for(j=0;j<m-1;j++)
a[i].si[j]=a[i-1].si[j+1];
a[i].si[m-1]=ch;
a[i].si[m]='\0';
a[i].in=i;
}



qsort(a,m,sizeof(T),cmp);


for(i=0;i<m;i++)
if(a[i].in==1)
{
printf("%ld\n",i);
break;
}
if(m==1)
{
printf("%ld\n",1);
}

j=0;
for(i=0;i<m;i++)
{printf("%c",a[i].si[m-1]);
j++;
if(j==50)
{
printf("\n");
j=0;
}
}
printf("\n");

}
}