10696 - f91

[exceptionAl]

ATTN: Java IO wizards

I got TLE for this problem but can't think of anything that would make my submission any faster.

Code: Select all

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.util.Scanner;

class Main
{
    void begin()
    {
        Scanner input = new Scanner ( new BufferedInputStream ( System.in ) );
        PrintStream output = new PrintStream ( new BufferedOutputStream ( System.out ) );
        int n = 0;

        while ( ( n = input.nextInt() ) != 0 )
        {
            output.format ( "f91(%d) = %d%n", n, n > 100 ? n - 10 : 91 );
        }

        output.flush();
    }

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

Am I using buffered IO correctly?
Feeding it my worst case test file (250000 random integers 1 to 1000000 inclusive) it takes about 10s.
I've tried tinkering with the buffer size but success eludes me. Results so far include:
- OutOfMemoryError (various forms)
- no actual output despite flush (this puzzles me)
- sub 3s runtime but incomplete output (doesn't actually produce all lines of output, only the last 100 or so)

I've tried an ANSI C solution but it appears to run even slower than my Java?!

Code: Select all

#include <stdio.h>

int main ()
{
    unsigned n = 0;

    while ( scanf ( "%u\n", &n ), n != 0 )
    {
        printf ( "f91(%u) = %u\n", n, n > 100 ? n - 10 : 91 );
    }

    return 0;
}

Any assistance with either of my solutions would be greatly appreciated.

Regards,
Alex C.

[brianfry713]

In Java try using BufferedReader and BufferedWriter.

Your C code is AC.

[exceptionAl]

I've tested using BufferedReader and BufferedWriter (with various buffer sizes) instead of BufferedInputStream and BufferedOutputStream but they don't appear any faster (still 10s runtimes on my machine).

[lbv]

ATTN: Java IO wizards
I got TLE for this problem but can't think of anything that would make my submission any faster. (..)

I'm definitely not a "Java IO wizard", but I used to code in Java some years ago for programming competitions, and something that I learned with time is how some of the things one would consider the natural Java counterparts of simple C/C++ I/O methods are usually slower by orders of magnitude.

I don't know the reasons, and I certainly don't know enough about Java's internals to have an opinion on the matter, but you can easily find relevant information searching the web. For example, you may read about java.util.Scanner here, and read about *.format here.

Not long ago for a similar question from a Java coder in these forums I dusted off some old files and manage to recover the following routines, which may be used as a guide to build your own I/O code if you want:
http://pastebin.com/rp6rzUK9

Here's an example of how it looks applied to your program:
http://pastebin.com/U19XNj5v

Hope it helps.

[nandopedrosa]

If you're getting TLE in Java, DO NOT use String concatenation. Try StringBuilder instead.

[prokawsar]

I Submit my code, but doesn't show anything.
My submission code : 15942859

[ashik!!]

Hello
I've got WA, Why?

Here is my solution

Code: Select all

#include <iostream>
#include<bits/stdc++.h>

using namespace std;
int f91(int x)
{
    int a=x;
    int count=0;
    if(a>=101)
    {
        a=a-10;
        return a;
    }
    else
    {
        count++;
        a=f91(f91(a+11));
        if(a==x&&count==0)
            return a;
    }
}

int main()
{
    int n;
    for(int i=0; i<25000; i++)
    {
        scanf("%d",&n);

        if(n==0)
            break;
        int m=f91(n);
        cout<<"f91("<<n<<") = "<<m<<"\n";
    }
    return 0;
}

Code: Select all

AC