import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        Map<Integer, Integer> m = new TreeMap<Integer, Integer>();

        in.nextToken();
        int nv = 0;
        int count = (int)in.nval;

        for(int i=0; i<count; i++)
        {
            in.nextToken();
            nv = (int)in.nval;
            if(m.containsKey(nv)) m.put(nv,(int)(m.get(nv)+1));
            else m.put(nv, 1);
        }

        for(int i : m.keySet())
        {
            out.print(m.get(i));
            out.print(' ');
            out.print(i);
            out.print(' ');
        }

        out.flush();
    }
}

what is test #6

import java.io.*;
import java.util.*;
//import java.math.*;

public class Main
{
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        //String[] name = new String[6];
        String[] device = new String[6];
        int[] price = new int[6];
        Map<String,Integer> result = new TreeMap<String,Integer>();
        Map<String,Integer> rprice = new TreeMap<String,Integer>();

        for(int i=0; i<6; i++) {
            in.readLine();
            device[i] = in.readLine();
            price[i] = Integer.parseInt(in.readLine());

            if(!result.containsKey(device[i])) {
                result.put(device[i],1);
                rprice.put(device[i],price[i]);
            }
            else {
                result.put(device[i],result.get(device[i])+1);
                if(price[i]<rprice.get(device[i])) rprice.put(device[i],price[i]);
            }
        }

        int rep = 1, max = 1;
        for(int i : new ArrayList<Integer>(result.values())) {
            if(max==i) rep++;
            if(max<i) { rep = 1; max = i; }
        }

        if(rep==1) {
            for(String i : result.keySet())
                if(max==result.get(i)) out.print(i);
        }
        else {
            int min=0;
            for(String i : rprice.keySet()) {
                if(max==result.get(i)) {
                    if(min==0) min=rprice.get(i);
                    else if(min>=rprice.get(i)) min=rprice.get(i);
                }
            }
            for(String i : rprice.keySet()) {
                if(min==rprice.get(i)) out.print(i);
            }
        }
        out.flush();
    }
}

I accepted 0.39(5kb). I use template veckor class(C++) to store list of employees. But I don't know how make my program faster :(

Edited by author 30.09.2008 14:40

Someone have interesting tests? :)

Can k be gretter than n if possible what should we do in this case?

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

public class _1068 {


    PrintStream         out     ;
    Scanner             sc;
    public _1068()
    {
        try {
            sc       = new Scanner(System.in);
            out     = System.out;
        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
    }

    protected void run() throws Exception {
        int n = sc.nextInt();
        int nb = Math.abs(n);
        if(n<0)
        nb+=2;
        out.println(((nb)*(n+1))/2);

        sc.close();
        out.close();
    }

    public static void main(String args[]) throws Exception {
        new _1068().run();
    }

}

My code below is failing at test 5. Please help me.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Cryptography1086
{
    public static void main( String[] args ) throws Exception
    {
        BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );

        StringTokenizer st = new StringTokenizer( br.readLine() );

        int numberOfNails = Integer.parseInt( st.nextToken() );

        double radiusOfNails = Double.parseDouble( st.nextToken() );

        double lengthOfRope = 2 * Math.PI * radiusOfNails;

        st = new StringTokenizer( br.readLine() );
        double x0 = Double.parseDouble( st.nextToken() );
        double y0 = Double.parseDouble( st.nextToken() );

        if( numberOfNails == 1 )
        {
            DecimalFormat df = new DecimalFormat( "#.00" );

            System.out.println( df.format( lengthOfRope ) );
            return;
        }

        double xStore = x0;
        double yStore = y0;

        double xK = 0;
        double yK = 0;

        for( int inx = 1 ; inx < numberOfNails; ++inx )
        {
            st = new StringTokenizer( br.readLine() );

            xK = Double.parseDouble( st.nextToken() );
            yK = Double.parseDouble( st.nextToken() );

            double dx = Math.pow( (xK - x0), 2 );
            double dy = Math.pow( (yK - y0), 2 );

            double dxy = Math.sqrt( dx + dy );

            lengthOfRope += dxy;

            x0 = xK;
            y0 = yK;
        }

        double d1 = Math.pow( (xK - xStore), 2 );
        double d2 = Math.pow( (yK - yStore), 2 );
        lengthOfRope += Math.sqrt( d1 + d2 );


        DecimalFormat df = new DecimalFormat( "#.00" );

        System.out.println( df.format( lengthOfRope ) );
    }
}

#include <iostream>

int main()
{
    int data[150000][2],i,j,n,step,temp;


    std::cin >> n;
    std::cin.ignore(255, '\n');
    for(i=0;i<n;++i)
    {

    for (j = 0; j < 2; ++j)

        std::cin>> data[i][j];
        std::cin.ignore(255, '\n');
    }
    j = 1;
    bool is_sorted;
    for(step=0;step<n-1;++step){
        is_sorted = true;
        for(i=0;i<n-step-1;++i)
        {

            if(data[i][j]<data[i+1][j])
            {
            temp=data[i][j];
            data[i][j]=data[i+1][j];
            data[i+1][j]=temp;

            temp = data[i][0];
            data[i][0]=data[i+1][0];
            data[i+1][0] = temp;

            is_sorted = false;
            }

        }
        if(is_sorted) break;
    }
    for(i=0;i<n;++i){
       for (j =0 ; j < 2; ++j){
        std::cout<<data[i][j]<<' ';
       }
       std::cout<<'\n';
    }

    return 0;
}

use simple algorithm:
 - checks only initial.
 - keep state of previous
 - initial state of previous is 1, since postman is in leftmost case

useful test cases:

----
1
Bambi

1 (not 0, because he moves to second case with one step)
----
1
Alice

0
----
1 Dumbo

2
---

Why that? Who can give me the test case that will fail like this?

Use scanf and printf instead of cin,cout.
I had a really hard time to figure it out))

#include<iostream>
#include<cmath>
#include<iomanip>
#include<vector>
using namespace std;
struct p
{
      double rec1;
     double rec2;
};
int main()
{
    vector<int> v;
    int n;
    cin>>n;
    if(1<=n&&n<=100)
    {
        int *ptr=new int[n*2];
        for(int i=0;i<(n*2);i++)
            cin>>ptr[i];
        if(n==1)
        {
            if(ptr[0]==0)
                cout<<ptr[0]+1<<" "<<ptr[1]<<" "<<1;
            else
            cout<<ptr[0]-1<<" "<<ptr[1]<<" "<<1;
        system("pause");
            return 0;
        }
            int lessx=0,highx=0,lessy=1,highy=1;
        for(int i=2;i<(n*2);i+=2)
        {
            if(ptr[i]<ptr[lessx])
                lessx=i;
            if(ptr[i]>ptr[highx])
            highx=i;
            if(ptr[i+1]<ptr[lessy])
                lessy=i+1;
            if(ptr[i+1]>ptr[highy])
            {

                v.clear();
                highy=i+1;
                v.push_back(i+1);
            }
            else if(ptr[i+1]==ptr[highy])
                v.push_back(i+1);



            }

        int point[2];
        point[0]=(ptr[lessx]+ptr[highx])/2.0;
        point[1]=(ptr[lessy]+ptr[highy])/2.0;
        for(int i=0;i<(n*2);i=i+2)
        {
            if(ptr[i]==point[0])
            {
                if(ptr[i+1]==point[1])
                {
                point[1]++;

                }
            }
        }

        cout<<point[0]<<" "<<point[1]<<" ";
        int p1,p2,max,min;
        if(v.size()>=2)
        {
         p1=highy;max=v[0]-1;p2=highy;min=v[0]-1;
        for(int i=1;i<v.size();i++)
        {
            if(ptr[v[i]-1]>point[0])
            {
                if(ptr[v[i]-1]>ptr[max])
                    p1=v[i];
            }
            else if(ptr[v[i]-1]<ptr[min])
                p2=v[i];
        }
        }
        int highp_y[2];
        if(v.size()>=2)
   {
        if((ptr[p1-1]-point[0])>(point[0]-ptr[p2-1]))
        {
            highp_y[0]=ptr[p1-1];
            highp_y[1]=ptr[p1];
        }
        else
        {
            highp_y[0]=ptr[p2-1];
            highp_y[1]=ptr[p2];
        }
    }
        else
        {
            highp_y[0]=ptr[highy-1];
            highp_y[1]=ptr[highy];
        }



        int lessp_x[2];
        lessp_x[0]=ptr[lessx];
        lessp_x[1]=ptr[lessx+1];
    double longr[2];
        p s;
        for(int i=1;i<=2;i++)
        {
            if(i==1)
            {
                s.rec2=point[0]-lessp_x[0];
            if(lessp_x[1]>point[1])
                s.rec1=lessp_x[1]-point[1];
            else
                s.rec1=point[1]-lessp_x[1];

                longr[0]=sqrt((s.rec1*s.rec1)+(s.rec2*s.rec2));

            }
            else
            {
                s.rec1=highp_y[1]-point[1];
                if(point[0]==highp_y[0])
                {
                    longr[1]=s.rec1;
                    break;
                }
                else
                {
                    if(point[0]>highp_y[0])
                        s.rec2=point[0]-highp_y[0];
                    else
                        s.rec2=highp_y[0]-point[0];
                    longr[1]=sqrt((s.rec1*s.rec1)+(s.rec2*s.rec2));
                }
            }
        }
        cout<<fixed<<setprecision(9);
        if(longr[0]>longr[1])
            cout<<longr[0];
        else
            cout<<longr[1];

        system("pause");
return 0;

    }
    system("pause");
return 0;

    }

O(n) solution got TLE on test 9 !

What is the test 7?

What is test 2?

New tests have been added, 24 authors have lost AC.

            var min1 = n;
            var min2 = n;

            for (var i = 0; i < k; i++)
            {
                var a = vals[i];
                if (a < min1)
                {
                    min2 = min1;
                    min1 = a;
                }
                else if (a < min2)
                    min2 = a;
            }

            Console.WriteLine(Math.Max(min1 + min2 - n, 0));