10941 - Words adjustment

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

Moderator: Board moderators

Rostislav
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:

10941 - Words adjustment

Post by Rostislav » Sat Oct 15, 2005 9:31 pm

In the input there is some word that's length is more than 1000 (even 1500)!
And I have a question, when I submit a code in C the reply is COMPILE ERROR, but in C++ MEMORY LIMIT or ACCEPTED(WA)
I mean than in C++ the source is being executed while in C it is not, because of memory shortage, why does this happens?

Rostislav

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

Post by Jan » Sun Oct 16, 2005 1:06 am

There are several functions that work in c++ compiler but not in c. I think you are using those types of function.

And there are some library files you cannot include in c. Like vector.h.
Ami ekhono shopno dekhi...
HomePage

Rostislav
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:

Post by Rostislav » Sun Oct 16, 2005 8:39 am

The code is the same and it is written only with C functions.

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

Post by Jan » Sun Oct 16, 2005 9:09 am

Can you show your code. Only the part which makes difference.
Ami ekhono shopno dekhi...
HomePage

Rostislav
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:

Post by Rostislav » Sun Oct 16, 2005 11:33 am

There is no difference, just submiting one and the same code
but once like C and once like C++.

Rostislav

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Oct 16, 2005 8:08 pm

Perhaps you declare variables in the middle of a code block?
E.g. "for (int i = ..."?

Rostislav
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:

Post by Rostislav » Sun Oct 16, 2005 10:27 pm

I apologize, my mistake!
I had used inline function and my compilator doesn't give any error about that when compiling like a C source. (ussualy i know than it gives COMPILE ERROR when using inline functions but I thought it was something different because at the contest i submited a lot of things and probably I misunderstood some of the replies).

Thank you for your replies.

Rostislav

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

10941 - Words adjustment

Post by polone » Wed Oct 19, 2005 12:12 pm

How to determine the adjustment is possible or not?

I have no idea... :cry: :-?

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

Post by polone » Wed Oct 19, 2005 12:50 pm

I just got AC that I assumed the upper bound is 3*k or less :o

but it's not fair... just a good luck :(

I remain wondering why it should pass

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Thu Oct 20, 2005 7:17 pm

Nice example. I think is slightly wrong though. Here is code that generates a very similar example.

Code: Select all

#include <stdio.h>

char buf[4] = "aaa";

int main()
{
    printf( "1\ntestaaa\ntest\n1000\nx\n" );

    for( int i = 0; i < 999; i++ )
    {
        printf( "%s", buf );
        for( int j = 0; j < 1000 - 6; j++ ) putchar( 'x' );

        int carry = 1;
        for( int j = 2; j >= 0; j-- )
        {
            buf[j] += carry;
            if( buf[j] > 'z' ) { buf[j] = 'a'; carry = 1; }
            else carry = 0;
        }

        if( i < 998 ) printf( "%s\n", buf );
        else printf( "xxx\n" );
    }
}
On this input, my accepted solution runs in 9.9 seconds on a 2.4GHz CPU and gives the answer

Code: Select all

994008
If only I had as much free time as I did in college...

Tamagodzi
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi » Thu Oct 20, 2005 8:30 pm

My Solution takes about 40 sec with same answer :-)

User avatar
angga888
Experienced poster
Posts: 143
Joined: Sat Dec 21, 2002 11:41 am
Location: Indonesia

Post by angga888 » Mon Oct 24, 2005 9:03 am

Hi, does anyone know the time limit of this problem during the contest?

:D

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Mon Oct 24, 2005 2:41 pm

Abednego wrote: On this input, my accepted solution runs in 9.9 seconds on a 2.4GHz CPU and gives the answer

Code: Select all

994008
My solution runs only 0.8 seconds on this test case, but I had to increase the number of nodes I allow in my prefix tree (which would give memory limit exceeded at the online judge).
I think that the judge test cases are very poor, and I fear that worst cases exist for every program, such that it will not terminate within 10 seconds.

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

Post by mf » Mon Oct 24, 2005 11:19 pm

Hi! Could someone post tricky test cases for this problem?
My program passes the test case mentioned above and also test cases from the original polish olympiad,
but it is getting WA here, and I really don't know why :(

And I'd like to ask, are there empty lines in the input? I use scanf(" %s",...) to read words, could this be a problem?

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Tue Oct 25, 2005 3:02 am

I think empty line is possible, although I don't know how to solve the problem yet.

Post Reply

Return to “Volume 109 (10900-10999)”