Try this test(Sorry for my poor English):
-2 -1 -4 -3
2 -1 1

correct output data:
3.00
5.32

#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
#define maxn 2000010

int wa[maxn],wb[maxn],wv[maxn],wss[maxn];
int rank[maxn],height[maxn];
int sa[maxn],r[maxn];
char str[maxn];
char temp[maxn];

int cmp(int *r,int a,int b,int l)
{
    return r[a]==r[b]&&r[a+l]==r[b+l];
}

void da(int *r,int *sa,int n,int m)
{
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0; i<m; i++) wss[i]=0;
    for(i=0; i<n; i++) wss[x[i]=r[i]]++;
    for(i=1; i<m; i++) wss[i]+=wss[i-1];
    for(i=n-1; i>=0; i--) sa[--wss[x[i]]]=i;
    for(p=1,j=1; p<n; j*=2,m=p)
    {
        for(p=0,i=n-j; i<n; i++) y[p++]=i;
        for(i=0; i<n; i++) if(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0; i<n; i++) wv[i]=x[y[i]];
        for(i=0; i<m; i++) wss[i]=0;
        for(i=0; i<n; i++) wss[wv[i]]++;
        for(i=1; i<m; i++) wss[i]+=wss[i-1];
        for(i=n-1; i>=0; i--)
            sa[--wss[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1; i<n; i++ )
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
}

void calheight(int *r,int *sa,int n)
{
    int i,j,k=0;
    for(i=1; i<=n; i++)
        rank[sa[i]]=i;
    for(i=0; i<n; height[rank[i++]]=k)
        for(k?k--:0,j=sa[rank[i]-1]; r[i+k]==r[j+k]; k++);
}

int main()
{
    while(scanf("%s",str)!=EOF)
    {
        int i;
        int len1=strlen(str);
        strcpy(temp,str);
        reverse(temp,temp+len1);
        //printf("%s\n",temp);
        memset(sa,0,sizeof(sa));
        memset(r,0,sizeof(r));
        memset(rank,0,sizeof(rank));
        memset(height,0,sizeof(height));
        str[len1]='#';
        for(i=len1+1;i<1+len1*2;i++) str[i]=temp[i-len1-1];
        str[i]='\0';
        for(i=0;str[i]!='\0';i++) r[i]=str[i];
        da(r,sa,i+1,256);
        calheight(r,sa,i);
        int k=0,n=i,max=-1;
        for(i = 2; i <= n; ++ i)
            if((sa[i]<len1)^(sa[i-1]<len1))
                if(k<height[i]){
                    k=height[i];
                    max=i;
                }
                else if(k==height[i]){
                //    printf("i=%d max=%d\n",sa[i],sa[max]);
                    if(sa[max]>sa[i]) max=i;
                }
        i=sa[max];
        for(;i<sa[max]+k;i++)
            printf("%c",str[i]);
        printf("\n");
    }
    return 0;
}

1 4 1 4 1 4

12 4

If we have input:
6
7 8 9 1 1 1
What should be output?
24 3  or  24 2

#include <iostream>
using namespace std;
void main()
{
    int n;
    int a[998];
    cin>>n;
    int i;
    int s=0;
    int smax=0;
    int imid=0;
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    for(i=0;i<n-2;i++)
    {
        s=a[i]+a[i+1]+a[i+2];
        if(s>smax)
        {
            smax=s;
            imid=i+2;
        }
    }
    cout<<smax<<" ";
    cout<<imid;
}

What did i do wrong ?

Edited by author 26.12.2014 13:39

Edited by author 20.09.2022 09:22

Edited by author 20.09.2022 09:22

If you get WA 8 you might not be checking correctly for string equality once the hash goes through (false positive).

I DID IT!!! It's my 200'th problem)) And how I have 666 rank =))))

----------

Preamble.
I've just solved this problem in C# using only Double type (64-bit floating point) and using only operations: +, - and *.
My method also can be used with only integer numbers. But in that way you'll need to code 128-bit signed integer type.

You have 4 points: "the banker’s eye" [name it Eye], "the victim" [name it Victim], "first mirror coordinate" [name it Mirror1], "second mirror coordinate" [name it Mirror2].

At first you should check whether Eye and Victim are in one halfplane relative to the mirror line. If they are not, then answer is INVISIBLE.

And now starting the most interesting part of solution.

My first thought was to build mirrored lines of sight (first: see from Eye, refraction point is Mirror1; and second: see from Eye, refraction point is Mirror2) ans check whether Victim is between that mirrored lines of sight.

But it requires more precision than double can offer.

And then I understand that there's another way to solve that problem!!

Hint1:
Build an equation, that depends of Eye, Victim, Mirror1, Mirror2, and RefractionPoint.
The last parameter is some point on the line formed by Mirror1 and Mirro2 points.
This equation must be true if the angle of incidence (between Eye and mirror) equals to the angle of reflection (between Victim and mirror) in RefractionPoint.
The only operation you need is +, -, * and /. But if you dispose of division and move all to the left side of the equation you'll get a function that equals to 0 when the angle of incidence equals to the angle of reflection in RefractionPoint and not equal to 0 otherwise.

Hint2:
The fact about that function: the sign of its returning value can say you a direction where to find that point.

And the last hint:
The jury do not ask you to find the refraction point =) They only ask you to determine if Victim is seen from Eye (!!!!). In other words "is there exists a RefractionPoint between Mirror1 and Mirror2 that function we've built equals to 0 in that point?"

Well, I think it is enough to solve this problem =))

Edited by author 20.07.2011 03:15

Here are some hints
1)Try to find the number of steps for every number to the final position and put it into a array
2)then try to find the least common multiple off all elements from the resulted array
let's consider an exemple 1 2 3 4 (the input is 4      )
                          4 2 1 3               4 2 1 3
int var = a[1] (in this example a[1] = 4 considering the array start from 1).
while(var != i) (i = 1 the first index of the array)
{
     var = a[var]; ((var)4 = a[4], var = 3, than 3 = var[3], var = 1(found the last position)
     k++; (is the number of steps that take to bring to last position)
}
lets make the array of k
x[i] = k;  than k = 0;
i++;
this array will look like i <- 1,n (3 1 3 3)
than just find the least common multiple for all elements that is 3
input                output
4                    3
4 2 1 3
and now the sample
5
4 1 5 2 3
the count arraw will look like
x[] = (3 3 2 3 2)
and the least common multiple is 6
explenation
a[1] = 4
var = a[1] = 4(k = 1)
var = a[var](4 = a[4])(k = 2) var = 2 after 2 = a[2] = 1(k = 3) (finish)
first k = 3 steps
x[1] = 3
after
i++;
var = a[2] ( var = 1 ) after 1 = a[1] (var = 4) after (4 = a[4] = 2 = i) finish
k = 3
and so on until the last element
I hope this will help (i'm not very good at expanation but i try).

I tried all the samples from the discussion and I tried some exception conditions. The program works for all these samples.
Do you have any idea what can be wrong? I can share my C++ code.

#include <iostream>
using namespace std;

#include <list>
#include <vector>
#include <cmath>

namespace grid {
    struct Graph {

        void SafeFree();

        void SetVertexCount(int count);

        int GetVertexCount() const {
            return m_vertexCount;
        }

        Graph();

        ~Graph() {
            SafeFree();
        }

        void SetWeight(short weight, int i, int j);

        short GetWeight(int i, int j) const;


        void TopologicalSortingVariantOne(std::vector<int> &out) const;

        void GetMaximumWeightedPath(std::vector<int> &out);

    private:
        int m_vertexCount;
        std::list<int> *edgelists;
        short **adj;
        short *in;
        short *out;
        int steps;
        bool invalid_edge_lists;

    };



    struct Point2D {
        Point2D ();
        Point2D (double x, double y);
        Point2D operator - (const Point2D &other) const;

        bool operator != (const Point2D &other) const {
            return fabs(other.x - x) > 1e-9 || fabs(other.y - y) > 1e-9;
        }

        double x, y;
    };

    struct Polygon {
        std::vector<Point2D> polyline;

        bool IsDisconnected() {
            return polyline[polyline.size() - 1] != polyline[0];
        }

        void SetSize(int size) {
            polyline.resize(size);
        }

        unsigned GetSize() const {
            return polyline.size();
        }

        void SetPoint(int index, const Point2D &point) {
            polyline[index] = point;
        }

        void PushPoint(Point2D &point) {
            polyline.push_back(point);
        }

        Point2D GetPoint(int index) const {
            return polyline[index];
        }
    };

    struct Line2D {
        Line2D (const Point2D &A, const Point2D &B);
        Point2D A, B;
    };


    struct Vector {
        int xdir;
        int ydir;

        int xSource, ySource;
    };

    typedef std::list<Vector> BoundVectorList;
    typedef BoundVectorList* BoundVectorListPtr;

    struct GridVectorField {
        int lines, columns;

        GridVectorField(int lines, int columns);

        GridVectorField () {
            grid = 0;
            Reset(0, 0);
        }

        void Reset(int lines, int columns) {
            Clear();
            this->lines = lines;
            this->columns = columns;
            grid = new BoundVectorListPtr[lines * columns];
            memset(grid, 0x0, lines * columns * sizeof(BoundVectorListPtr));
        }

        void ClearSparseLists() {
        }

        ~GridVectorField () {
            Clear();
        }

        void AddVector(int i, int j, Vector &vector);
        void ClearVector( int i, int j );

        BoundVectorListPtr GetVectorList(int i, int j) const;

        void Clear();


    private:
        std::list<BoundVectorListPtr> sparseLists;
        BoundVectorListPtr *grid;
    };


    class GridVectorization
    {
    public:


    private:
        double distance2(const Point2D &P,const  Line2D &line) const ;

        double length_squared(const Point2D &A,const  Point2D &B);

        double distance1(const Point2D &A,const  Point2D &B);

        double dot(const Point2D &A,const  Point2D &B);

        double minimum_distance(const Point2D &v,const  Point2D &w,const Point2D &p);

        double cross(const Point2D &  p1, const Point2D &  p2, const Point2D &  p3);

        void BuildGraph(Polygon &inPoly, Graph &outGraph, double const innerTolerance, double const outerTolerance );

    public:
        GridVectorization(void);
        ~GridVectorization(void);

        void AproximatePolygon(Polygon &inPoly, double const innerTolerance, double const outerTolerance, Polygon &outPoly);

        void AproximatePolygonList(std::list<Polygon *> &listIn, double const innerTolerance, double const outerTolerance, std::list<Polygon *> &listOut);

        void VectorizeGrid( char *grid, int const Lines, int const Columns, int const aabbWidth, int const aabbHeight, std::list<Polygon *> &polylistOut );

        void Fill(char *grid, int const i, int const j, int const aabbWidth, int const aabbHeight, int const Lines, int const Columns, int searchValue, int fillValue);

    private:
        char GetCell(int i, int j, char *grid, int Lines, int Columns);

        void SetCell(int i, int j, char *grid, int Lines, int Columns, char cell);

        void DetectPolygon (char *grid, int const i, int const j, int const Lines, int const Columns, GridVectorField &field, Polygon &outPoly);

        void BuildCwVectorField(char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut);

        void BuildCcwVectorField(char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut);

        void FillAndBuildVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut);

        void FillAndClearVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut);

        bool IsReachable(char *grid, int const Lines, int const Columns, int sourceX, int sourceY, int destX, int destY);


    };
}


#include <iostream>
using namespace std;
using namespace grid;

int main ()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    char *grid;
    grid::GridVectorization vectorization;
    int n, m;
    char c;

    scanf("%d%d", &m, &n);
    grid = new char[ n * m ];


    scanf("%c", &c);

    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<m; ++j)
        {
            scanf("%c", &c);
            grid[ m * i + j ] = c - '0';

            //printf("%c", c);
        }
        scanf("%c", &c);
        //printf("\n");
    }


    std::list<Polygon *> poly, poly2;
    vectorization.VectorizeGrid(grid, n, m, 2000, 2000, poly);
    vectorization.AproximatePolygonList(poly, 2, 0.96, poly2);


    Polygon *p = poly2.front();

    switch(p->GetSize())
    {
    case 5:
        printf("square\n");
        break;
    case 4:
        printf("triangle\n");
        break;
    default:
        printf("circle\n");
    }
    return 0;
}

#include <cmath>



namespace grid {

    int dirX[] = {0, 1, 0, -1};
    int dirY[] = {-1, 0, 1, 0};

    char specialGridFlag = char(-1);

    int dirX2[] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dirY2[] = {-1, 0, 1, 0, -1, 1, -1, 1};

    GridVectorization::GridVectorization(void)
    {
    }

    GridVectorization::~GridVectorization(void)
    {
    }

    double GridVectorization::distance2( const Point2D &P, const Line2D &line ) const
    {
        return abs( (line.B.x - line.A.x) * (line.A.y - P.y) - ( line.A.x - P.x ) * (line.B.y - line.A.y) ) /
            sqrt(double((line.B.x - line.A.x) * (line.B.x - line.A.x) + (line.B.y - line.A.y) * (line.B.y - line.A.y)));
    }

    double GridVectorization::length_squared( const Point2D &A, const Point2D &B )
    {
        return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
    }

    double GridVectorization::distance1( const Point2D &A, const Point2D &B )
    {
        return sqrt(length_squared(A, B));
    }

    double GridVectorization::dot( const Point2D &A, const Point2D &B )
    {
        return A.x * B.x + A.y * B.y;
    }

    double GridVectorization::minimum_distance( const Point2D &v, const Point2D &w, const Point2D &p )
    {
        // Return minimum distance between line segment v w and point p
        double l2 = length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
        if (l2 == 0.0) return distance1(p, v);   // v == w case
        // Consider the line extending the segment, parameterized as v + t (w - v).
        // We find projection of point p onto the line.
        // It falls where t = [(p-v) . (w-v)] / |w-v|^2
        double t = dot(p - v, w - v) / l2;
        if (t < 0.0) return distance1(p, v);       // Beyond the 'v' end of the segment
        else if (t > 1.0) return distance1(p, w);  // Beyond the 'w' end of the segment
        Line2D const &ref = Line2D(w, v);
        return distance2(p, ref);
    }

    double GridVectorization::cross( const Point2D & p1, const Point2D & p2, const Point2D & p3 )
    {
        return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
    }

    void GridVectorization::BuildGraph( Polygon &inPoly, Graph &outGraph, double const innerTolerance, double const outerTolerance )
    {
        outGraph.SetVertexCount(inPoly.GetSize());

        if(!inPoly.GetSize())
            return;

        for(unsigned i=0; i < inPoly.GetSize() - 1; ++i)
            for(unsigned j=1; j < inPoly.GetSize(); ++j) {
                bool ok = true;
                for(unsigned k = i + 1; ok && k < j; ++k) {
                    double min_distance = minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k));
                    double cross_prod = cross(inPoly.GetPoint(j), inPoly.GetPoint(k), inPoly.GetPoint(i));

                    if(min_distance >= innerTolerance && cross_prod <= 0.0) {
                        //cout << "Inner: (" << i << ", " << j << ") - " << k << " distance: " << minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k)) << "\n";
                        ok = false;
                    }
                    if(min_distance >= outerTolerance && cross_prod > 0.0) {
                        //cout << "Outer: (" << i << ", " << j << ") - " << k << " distance: " << minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k)) << "\n";
                        ok = false;
                    }
                }
                if(ok) {
                    outGraph.SetWeight( j - i - 1, i, j );
                }
            }
    }

    void GridVectorization::AproximatePolygon( Polygon &inPoly, double const innerTolerance, double const outerTolerance, Polygon &outPoly )
    {
        Graph polylineGraph;
        BuildGraph(inPoly, polylineGraph, innerTolerance, outerTolerance);
        std::vector <int> optimized;
        polylineGraph.GetMaximumWeightedPath(optimized);

        outPoly.SetSize(optimized.size());

        int last = optimized.size() - 1;

        for(int i = last; i >= 0; --i) {
            outPoly.SetPoint(last - i, inPoly.GetPoint(optimized[i]));
        }
    }

    char GridVectorization::GetCell( int i, int j, char *grid, int Lines, int Columns )
    {
        if(    i < Lines && j < Columns &&
            i >= 0 && j >= 0 &&
            Lines >= 0 && Columns >= 0) {
                return grid[i * Columns + j];
        }
        return 0;
    }

    void GridVectorization::SetCell( int i, int j, char *grid, int Lines, int Columns, char cell )
    {
        if(    i < Lines && j < Columns &&
            i >= 0 && j >= 0 &&
            Lines >= 0 && Columns >= 0) {
                grid[i * Columns + j] = cell;
        }
        //no effect
    }

    void GridVectorization::VectorizeGrid( char *grid, int const Lines, int const Columns, int const aabbWidth, int const aabbHeight, std::list<Polygon *> &polylistOut )
    {
        //detect shapes
        GridVectorField field;

        BuildCwVectorField(grid, Lines, Columns, 1, field);

        int startX = -1, startY = -1;
        for(int i=0; i<Lines; ++i) {
            for(int j=0; j<Columns; ++j) {
                if(grid[i * Columns + j] == 1) {

                    Fill(grid, i, j, aabbWidth, aabbHeight, Lines, Columns, 1, 2);

                    Polygon *newPoly = new Polygon();

                    DetectPolygon(grid, i, j, Lines, Columns, field, *newPoly);
                    //push the polygon
                    polylistOut.push_back(newPoly);

                    //erase the polygon
                    Fill(grid, i, j, Columns, Lines, Lines, Columns, 2, 0);
                }
            }
        }
    }

    void GridVectorization::AproximatePolygonList( std::list<Polygon *> &listIn, double const innerTolerance, double const outerTolerance, std::list<Polygon *> &listOut )
    {
        for(std::list<Polygon *>::iterator it = listIn.begin(); it != listIn.end(); ++it) {
            Polygon *poly = *it;
            if(poly != 0) {
                Polygon *out = new Polygon();
                AproximatePolygon(*poly, innerTolerance, outerTolerance, *out);
                listOut.push_back(out);
            }
        }
    }

    void GridVectorization::DetectPolygon( char *grid, int const i, int const j, int const Lines, int const Columns, GridVectorField &field, Polygon &outPoly )
    {
        ///////////////////calculating the contour of the shape (based on the vector field)////////////////////////////
        BoundVectorListPtr lst = field.GetVectorList(i, j);
        BoundVectorList::iterator it;

        Vector startPos;
        Vector currentPos;

        currentPos.xdir = startPos.xdir = i;
        currentPos.ydir = startPos.ydir = j;

        Vector lastDir;
        lastDir.xdir = -2;
        lastDir.ydir = -2;
        lastDir.xSource = i;
        lastDir.ySource = j;

        Vector currentDir;
        currentDir.xdir = -3;
        currentDir.ydir = -3;

        currentDir.xSource = i;
        currentDir.ySource = j;

        std::list<Point2D> polygon;

        bool error = false;

        int cellValue = GetCell(i, j, grid, Lines, Columns);

        do {

            int ii = (int)currentPos.xdir;
            int jj = (int)currentPos.ydir;

            BoundVectorListPtr lst = field.GetVectorList(ii, jj);
            BoundVectorList::iterator it;

            if(!lst || polygon.size() > (unsigned)((Lines + 1) * (Columns + 1) * 4)) {
                printf("What?\n");
                //fuck
                error = true;
            }

            //first getting the first vector on the contour

            for(it = lst->begin(); it != lst->end(); ++it) {

                if(!IsReachable(grid, Lines, Columns, currentDir.xSource, currentDir.ySource, it->xSource, it->ySource)) continue;

                if(it->xdir == 1 && it->ydir == 0 && GetCell(ii, jj, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == 0 && it->ydir == -1 && GetCell(ii, jj-1, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == -1 && it->ydir == 0 && GetCell(ii-1, jj-1, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == 0 && it->ydir == 1 && GetCell(ii-1, jj, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }
            }

            //push a vertex only when the direction has changed
            if(lastDir.xdir != currentDir.xdir || lastDir.ydir != currentDir.ydir) {
                polygon.push_back(Point2D(currentPos.xdir, currentPos.ydir));
            }

            lastDir = currentDir;
            currentPos.xdir += currentDir.xdir;
            currentPos.ydir += currentDir.ydir;

        } while ( (startPos.xdir != currentPos.xdir || startPos.ydir != currentPos.ydir) && !error);

        if(error) {
            polygon.clear();
        }
        Polygon *newPoly = &outPoly;
        int k = 0;
        for(std::list<Point2D>::iterator it = polygon.begin(); it != polygon.end(); ++it) {
            newPoly->PushPoint(*it);
            ++k;
        }

        //add the last vertex to the polygon
        newPoly->PushPoint(*polygon.begin());
    }

    void GridVectorization::FillAndBuildVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut)
    {
        Vector vect;
        std::list<std::pair<int, int> > queue;
        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;
                grid[ cX * Columns + cY ] = fillValue;
                ///////////////////////////////////////////////////////////

                bool isEdge = false;
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines) {
                        if(aj >= 0 && aj < Columns) {
                            if( grid[ ai * Columns + aj ] != searchValue && grid[ ai * Columns + aj ] != fillValue)
                                isEdge = true;
                        }
                        else
                            isEdge = true;
                    }
                    else
                        isEdge = true;
                }

                if(isEdge) {

                    vect.xSource = cX;
                    vect.ySource = cY;

                    vect.xdir = 0;
                    vect.ydir = 1;
                    fieldOut.AddVector(cX, cY, vect);

                    vect.xdir = 1;
                    vect.ydir = 0;
                    //safe to do because the vector field has its own validation methods
                    fieldOut.AddVector(cX, cY + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = 0;
                    vect.ydir = -1;
                    fieldOut.AddVector(cX + 1, cY + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = -1;
                    vect.ydir = 0;
                    fieldOut.AddVector(cX + 1, cY, vect);

                }

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines)
                        if(aj >= 0 && aj < Columns)
                            if( grid[ ai * Columns + aj ] == searchValue ) {
                                grid[ ai * Columns + aj ] = fillValue;
                                queue.push_back(std::pair<int, int>(ai, aj));
                            }
                }
                queue.pop_front();
            }
        }
    }

    void GridVectorization::FillAndClearVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut)
    {
        std::list<std::pair<int, int> > queue;
        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;

                grid[ cX * Columns + cY ] = fillValue;
                ///////////////////////////////////////////////////////////

                fieldOut.ClearVector(cX, cY);
                fieldOut.ClearVector(cX, cY + 1);
                fieldOut.ClearVector(cX + 1, cY + 1);
                fieldOut.ClearVector(cX + 1, cY);

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines)
                        if(aj >= 0 && aj < Columns)
                            if( grid[ ai * Columns + aj ] == searchValue ) {
                                queue.push_back(std::pair<int, int>(ai, aj));
                                grid[ ai * Columns + aj ] = fillValue;
                            }
                }
                queue.pop_front();
            }
        }
    }

    void GridVectorization::Fill( char *grid, int const i, int const j, int const aabbWidth, int const aabbHeight, int const Lines, int const Columns, int searchValue, int fillValue )
    {
        std::list<std::pair<int, int> > queue;
        int minLines, maxLines;
        int minColumns, maxColumns;

        if(searchValue == specialGridFlag) {
            //reserved
            printf("Search value is reserved!\n");
            grid[ i * Columns + j ] = fillValue;
            return;
        }

        minLines = maxLines = i;
        minColumns = maxColumns = j;

        bool stopColumns = false, stopLines = false;

        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;

                ///////////////////////////////////////////////////////////

                if(!stopLines) {
                    if(cX < minLines)
                        minLines = cX;

                    if(cX > maxLines)
                        maxLines = cX;
                }

                if(!stopColumns) {

                    if(cY < minColumns)
                        minColumns = cY;

                    if(cY > maxColumns)
                        maxColumns = cY;
                }

                if(maxColumns - minColumns + 1 >= aabbWidth)
                    stopColumns = true;

                if(maxLines - minLines + 1 >= aabbHeight)
                    stopLines = true;

                grid[ cX * Columns + cY ] = fillValue;

                if(stopColumns || stopLines) {
                    if(cX < minLines || cX > maxLines)
                        grid[ cX * Columns + cY ] = searchValue;

                    if(cY < minColumns || cY > maxColumns)
                        grid[ cX * Columns + cY ] = searchValue;
                }

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(stopLines) {
                        if(ai >= minLines && ai <= maxLines)
                            if(stopColumns) {
                                if(aj >= minColumns && aj <= maxColumns && grid[ ai * Columns + aj ] == searchValue ) {
                                    queue.push_back(std::pair<int, int>(ai, aj));
                                    grid[ ai * Columns + aj ] = specialGridFlag;
                                }
                            }
                            else {
                                if(aj >= 0 && aj < Columns)
                                    if( grid[ ai * Columns + aj ] == searchValue ) {
                                        queue.push_back(std::pair<int, int>(ai, aj));
                                        grid[ ai * Columns + aj ] = specialGridFlag;
                                    }
                            }
                    }
                    else {
                        if(ai >= 0 && ai < Lines)
                            if(stopColumns) {
                                if(aj >= minColumns && aj <= maxColumns && grid[ ai * Columns + aj ]  ==  searchValue ) {
                                    queue.push_back(std::pair<int, int>(ai, aj));
                                    grid[ ai * Columns + aj ] = specialGridFlag;
                                }
                            }
                            else {
                                if(aj >= 0 && aj < Columns)
                                    if(grid[ ai * Columns + aj ]  ==  searchValue ) {
                                        queue.push_back(std::pair<int, int>(ai, aj));
                                        grid[ ai * Columns + aj ] = specialGridFlag;
                                    }
                            }
                    }
                }
                queue.pop_front();
            }
        }
    }

    bool GridVectorization::IsReachable( char *grid, int const Lines, int const Columns, int sourceX, int sourceY, int destX, int destY )
    {
        bool passable = false;

        if(sourceX < Lines && sourceX >= 0 && sourceY < Columns && sourceY >= 0)
            if(destX < Lines && destX >= 0 && destY < Columns && destY >= 0)
                passable = true;


        if(!passable) {
            return false;
        }

        char searchValue =  grid[ sourceX * Columns + sourceY ];
        char destValue = grid[ destX * Columns + destY ];


        if(destValue != searchValue) {
            return false;
        }

        else {

            bool validDir = false;

            // backslash orientation
            if( (destX == sourceX + 1 && destY == sourceY + 1) || (sourceX == destX + 1 && sourceY == destY + 1) ) {
                char upRight = grid[ sourceX * Columns + destY ];
                char downLeft = grid[ destX * Columns + sourceY ];

                if(upRight == searchValue || downLeft == searchValue)
                    validDir = true;
            }

            //slash orientation
            if ((destX == sourceX - 1 && destY == sourceY + 1) || (sourceX == destX - 1 && sourceY == destY + 1)) {

                char upLeft = grid[ destX * Columns + sourceY ];
                char downRight = grid[ sourceX * Columns + destY ];

                if(downRight == searchValue || upLeft == searchValue)
                    validDir = true;
            }

            if(sourceX == destX || sourceY == destY)
                validDir = true;

            if(sourceX == destX &&
                sourceY == destY)
                validDir = true;

            return validDir;
        }
    }

    void GridVectorization::BuildCwVectorField( char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut )
    {
        fieldOut.Reset(Lines + 1, Columns + 1);
        for(int i=0; i<Lines; ++i)
            for(int j=0; j<Columns; ++j) {
                if(grid[i * Columns + j] == searchValue) {

                    Vector vect;
                    vect.xSource = i;
                    vect.ySource = j;

                    vect.xdir = 0;
                    vect.ydir = 1;
                    fieldOut.AddVector(i, j, vect);

                    vect.xdir = 1;
                    vect.ydir = 0;
                    //safe to do because the vector field has its own validation methods
                    fieldOut.AddVector(i, j + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = 0;
                    vect.ydir = -1;
                    fieldOut.AddVector(i + 1, j + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = -1;
                    vect.ydir = 0;
                    fieldOut.AddVector(i + 1, j, vect);
                }
            }
    }

    void GridVectorization::BuildCcwVectorField( char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut )
    {
        //counter clockwise vector field
    }

    void Graph::SafeFree()
    {
        steps = 0;
        if(adj) {

            for(int i=0; i<GetVertexCount(); ++i)
                if(adj[i])
                    free(adj[i]);
            delete []adj;
            adj = 0;
        }

        if(edgelists) {
            invalid_edge_lists = false;
            delete []edgelists;
            edgelists = 0;
        }

        if(in) {
            delete []in;
            in = 0;
        }

        if(out) {
            delete []out;
            out = 0;
        }
    }

    void Graph::SetVertexCount( int count )
    {
        SafeFree();

        if(count <= 0) {
            m_vertexCount = 0;
            return;
        }

        adj = new short*[count];
        edgelists = new list<int>[count];
        in = new short[count];
        memset(in, 0x0, count * sizeof(short));
        out = new short[count];
        memset(out, 0x0, count * sizeof(short));


        for (int i=0; i<count; ++i) {
            adj[i] = (short *)malloc(count * sizeof(short));
            if(!adj[i]) {
                printf("Couldn't allocate memory for the graph!\n");
                exit(1);
                break;
            }
        }

        m_vertexCount = count;

        for(int i=0; i<m_vertexCount; ++i) {
            memset(adj[i], -1, m_vertexCount * sizeof(short));
        }
    }

    Graph::Graph()
    {
        adj = 0;
        in = 0;
        out = 0;
        edgelists = 0;
        steps = 0;
        SetVertexCount(0);
    }

    void Graph::SetWeight( short weight, int i, int j )
    {
        if(i >= m_vertexCount || j >= m_vertexCount || i < 0 || j < 0) {
            return;
        }

        if(weight >= 0 && *(adj[i] + j) < 0) {
            in[j] ++;
            out[i] ++;
            edgelists[i].push_back(j);
            //add edge
        }
        else if(weight < 0 && *(adj[i] + j) >= 0) {
            in[j] --;
            out[i] --;
            //remove edge
        }
        *(adj[i] + j) = weight;
    }

    short Graph::GetWeight( int i, int j ) const
    {
        if(i >= m_vertexCount || j >= m_vertexCount || i < 0 || j < 0) {
            return -1;
        }
        return *(adj[i] + j);
    }

    void Graph::TopologicalSortingVariantOne( std::vector<int> &out ) const
    {
        //O(m + n) steps
        if(GetVertexCount() == 0)
            return;

        Graph const &g = *this;
        std::vector<int> removed;

        int n = g.GetVertexCount();
        int count = n;

        for(int i=0; i<n; ++i) {
            removed.push_back(0);
        }

        short *in = new short[n];

        memcpy(in, g.in, n * sizeof(short));

        int steps = 0;
        while(count) {
            for(int i=0; i<n; ++i)
                if(!removed[i] && !in[i]) {
                    for(list<int>::const_iterator it = g.edgelists[i].begin(); it != g.edgelists[i].end(); ++it) {
                        in[*it]--;
                        steps++;
                    }
                    count--;
                    out.push_back(i);
                    removed[i] = 1;
                }
        }
        delete []in;
    }

    void Graph::GetMaximumWeightedPath( std::vector<int> &out )
    {
        // O(m + n)

        if(GetVertexCount() == 0)
            return;

        Graph const &g = *this;

        std::vector<int> sorted;
        std::vector<int> costs, prev;
        int last = -1;

        for(int i=0; i<g.GetVertexCount(); ++i) {
            costs.push_back(-1);
            prev.push_back(-1);
        }


        g.TopologicalSortingVariantOne(sorted);
        costs[sorted[0]] = 0;

        for(unsigned i=0; i<sorted.size(); ++i) {
            int element = sorted[i];
            for(list<int>::const_iterator it = g.edgelists[element].begin(); it != g.edgelists[element].end(); ++it) {
                if(costs[*it] < g.GetWeight(element, *it) + costs[element]) {
                    costs[*it] = g.GetWeight(element, *it) + costs[element];
                    prev[*it] = element;
                    last = *it;
                    ++steps;
                }
            }
        }

        last = g.GetVertexCount() - 1;

        for(int i = last; i != -1; i = prev[i]) {
            out.push_back(i);
        }
    }

    Point2D::Point2D()
    {
        x = 0.0;
        y = 0.0;
    }

    Point2D::Point2D( double x, double y )
    {
        this->x = x;
        this->y = y;
    }

    Point2D Point2D::operator-( const Point2D &other ) const
    {
        Point2D result;
        result.x = x - other.x;
        result.y = y - other.y;
        return result;
    }

    Line2D::Line2D( const Point2D &A, const Point2D &B )
    {
        this->A = A;
        this->B = B;
    }

    GridVectorField::GridVectorField( int lines, int columns )
    {
        grid = 0;
        Reset(lines, columns);
    }

    void GridVectorField::AddVector( int i, int j, Vector &vector )
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            BoundVectorListPtr list = grid[i * columns + j];
            if(!list) {
                list = new BoundVectorList();
                sparseLists.push_back(list);
                grid[i * columns + j] = list;
            }
            list->push_back(vector);
        }
    }

    BoundVectorListPtr GridVectorField::GetVectorList( int i, int j ) const
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            BoundVectorListPtr list = grid[i * columns + j];
            return list;
        }
        return 0;
    }

    void GridVectorField::Clear()
    {
        if(grid) {
            delete []grid;
            for(std::list<BoundVectorListPtr>::iterator it = sparseLists.begin(); it != sparseLists.end(); ++it) {
                delete (*it);
            }
            sparseLists.clear();
        }
    }

    void GridVectorField::ClearVector( int i, int j )
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            if(grid[i * columns + j])
                grid[i * columns + j]->clear();
        }
    }
}

#include <iostream>
using namespace std;
int main()
{
int a,b ;
cin>>a>>b ;
int c=b-a+(a%2)+(b%2) ;
cout<<c/2 ;
}

Change "left" to "remaining" since it would otherwise indicate "the opposite of right" which is confusing

I had a small bug in my code. I found it using my test sample. I would like to share it with you. I have used some extra white space in the boolean expression. I am not sure if it is necessary, you can remove them.

Input:

(NOT  ( (NOT  NOT TRUE ) AND  A) OR (B AND C AND D))    OR E
 3 10 14
 -3 -3
 -3 -1
 -3 3
 -1 1
 0 -2
 2 -1
 2 3
 3 -3
 3 0
 3 2
 -3 -2 A
 -2 -3 A
 -2 -1 A
 -1 -3 D
 -1 -1 Z
 0 -3 C
 0 -1 C
 1 -3 E
 1 0 A
 2 -3 B
 2 0 A
 2 1 E
 3 -1 E
 3 3 B
 0 0
 1 0
 2 0
 3 0
 3 1
 3 2
 2 2
 1 2
 0 2
 -1 2
 -2 2
 -3 2


Output:
0 0
1 0
2 0
3 0
3 -1
3 -2
3 -3
2 -3
1 -3
0 -3
-1 -3
-2 -3
-3 -3
-3 -2
-3 -1
-2 -1
-1 -1
0 -1
1 -1
2 -1
2 0
2 1
2 2
2 3
3 3

This is how the table looks like: (1 means there is a Fork and * means empty cell)
1 A 1 * * * 1
A * A * * * *
D * Z * 1 * *
C 1 C * * * *
E * * A * * *
B * 1 A E * 1
1 * E 1 * 1 B

What is 62th testcase?

del

Edited by author 06.01.2015 21:37