6
3 5 1 6 2 4

Hello, everybody!

I tryed to solve this problem for a week. I DO NOT KNOW WHAT TO DO. I can't think out anything :(

Thanks.

Anybody would like to share some ideas? Thanks.

)

Use eps= 1e-9.first i don't use eps and get WA#3.
this test help me:
input:
3
-15000 0
-14999 0
15000 1

output:
Yes
-15000.0000 0.5000
-14999.0000 0.5000
14999.0000 0.5000
15000.0000 0.5000
-15000.0000 -0.5000
-14999.0000 -0.5000
14999.0000 0.5000
15000.0000 0.5000

thank's to AlexF[USTU] about this note.
hope can help you.

I submited one file for 3 times and got 3 different results:
WA 1, WA 8 and WA 16...

Sorry. I think it's my fail. $R+ and $Q+ helped me to get only WA8

No, WA1 with same text again...

PS Sorry for spam...

Edited by author 15.01.2011 17:34

Edited by author 15.01.2011 17:43

My solutions based on the wrong assumption that the view angle has only one maximum on abscissa axis (and with some tricks regarding to range of search or partition method in ternary search) pass all tests. Seems that more tests needed.

my simple test solution consist of only

            int N = int.Parse(Console.ReadLine());
            GC.Collect();

            Console.WriteLine("400");
            Console.WriteLine("200");
            Console.WriteLine("300");

and eats 1156 KB, MLE#1

I made testing on computer and all tests have pass Ok
Please, say me what is 6 test?

In other words, is for input {A, B, C, D} result always equal to result for input {C, D, A, B} ?

try this test too : )

7
4
4 4 3 2

corrent : -1
my WA was : 0

Try test
"this sentence have one mistake"
Answer is 1

Hello, my code gives TLE using a Binary Indexed Tree, and I find the thing quite strange... Here is my solution:

#include <iostream>



using namespace std;



#define MAXX 32001



int tree[ MAXX ];

int l[ 15000 ];





inline void update( int x )

{

    while ( x <= MAXX )

    {

        tree[ x ]++;

        x += ( x & -x );

    }

}





inline int query( int x )
{
    int sum = 0;
    while ( x > 0 )
    {
        sum += tree[ x ];
        x -= ( x & -x );
    }
    return sum;
}





int main()

{

    int n, x, y;

    cin >> n;



    for ( int i = 0;  i < n;  i++ )

    {

        scanf( "%d %d", &x, &y );

        l[ query( x ) ]++;


        update( x );

    }



    for ( int i = 0;  i < n;  i++ )

        printf( "%d\n", l[ i ] );

}

My programm search the greatest angle in x in [x1..x2] and got AC.
But it's wrong. For example in test 0 3 1 1.

PS Maybe i'm wrong

Edited by author 13.01.2011 21:20

program correctly solves all problems, but for some reason the site shows that the program is wrong ... can you explain why?

#include<iostream>
using namespace std;

int main()
{
    double ves_k[20];
    int i,num;
    double t,perv,vtor,res;

    cin>>num;
    if(num<1||num>20) goto vozvrat;
    for(i=0; i<num; i++){
        cin>>ves_k[i];
        if(ves_k[i]<1||ves_k[i]>10000) goto vozvrat;
    }
    if(num!=1){
    for(int a=1; a<i; a++)
        for(int b=i-1; b>=a; b--){
            if(ves_k[b-1]>ves_k[b]) {
                t=ves_k[b-1];
                ves_k[b-1]=ves_k[b];
                ves_k[b]=t;
            }
        }
    perv=ves_k[num-1];
    vtor=ves_k[num-2];
    for(i=num-3; i>=0; i--){
        if(perv>=vtor) vtor+=ves_k[i];
        else perv+=ves_k[i];
    }
    res=perv-vtor;
    if(res<0) res=-res;
    } else res=ves_k[0];

    cout<<res;
vozvrat:
    return 0;
}

Edited by author 13.01.2011 02:22

Good time of day.
I constantly get WA on test #6. Does anybody know why may this happen?
Here's my code, seems to give correct answers for any correct test found in discussions:

#include <stdio.h>
#include <iostream>
#include <map>

using namespace std;

typedef unsigned int uint;

const uint MAX_N = 5000;
const bool COLOR_BLACK = false;
const bool COLOR_WHITE = true;

typedef pair <uint, bool> LinePair;
typedef map<uint, LinePair> TLines;

TLines lines;

void paint(uint c, uint d, const bool clr)
{
    if (c == d)
        return;
    uint a, b;
    bool c2;
    if (lines.empty())
    {
        lines[c] = LinePair(d, clr);
        return;
    }

    TLines::iterator i = lines.begin();
    //пропускаем все отрезки, что левее нашего и не накладываются на него
    while (c > (i->second).first) ++i;
    //работаем с накладывающимися отрезками
    while ((d >= i->first) && (i != lines.end()))
    {
        //для удобства написания
        a = i->first;
        b = (i->second).first;
        c2 = (i->second).second;
        if (a >= c)
        {
            if (d >= b)
            {
                lines.erase(i);
            }
            else if (clr == c2)
            {
                d = b;
                lines.erase(i);
            }
            else
            {
                lines.erase(i);
                lines[d] = LinePair(b, c2);
            }
        }
        else
        {
            if (d >= b)
            {
                if (clr == c2)
                {
                    c = a;
                    lines.erase(i);
                }
                else
                {
                    (i->second).first = c;
                }
            }
            else if (clr == c2)
            {
                c = a;
                d = b;
            }
            else
            {
                (i->second).first = c;
                lines[d] = LinePair(b, c2);
            }
        }
        ++i;
    }
    //собственно добавление заданного отрезка
    lines[c] = LinePair(d, clr);
    return;
}

int main()
{
    uint n, b, e;
    char ch;
    bool clr;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    lines.clear();
    paint(0, 1e+9, COLOR_WHITE);
    cin >> n;
    for (uint i = 0; i < n; i++)
    {
        cin >> b >> e >> ch;
        if (ch == 'b')
            clr = COLOR_BLACK;
        else
            clr = COLOR_WHITE;
        paint(b, e, clr);
    }
    TLines::const_iterator maxLine;
    uint max = 0;
    for (TLines::const_iterator i = lines.begin(); i != lines.end(); ++i)
    {
        if (((i->second).second == COLOR_WHITE) && ((i->second).first - i->first > max))
        {
            max = (i->second).first - i->first;
            maxLine = i;
        }
#ifndef ONLINE_JUDGE
        cout << i->first << '\t' << (i->second).first << '\t' << (i->second).second << endl;
#endif
    }
    cout << maxLine->first << " " << (maxLine->second).first << endl;
    return 0;
}

Edited by author 05.01.2011 03:29

First, very stupied method: used just 2 arrays for A and B values, 0.609s, 673KB.
Second, some hint: used multi-stack and for pointers at next element used unsigned short, 0.031s, 677KB.
Sorry, for bad english:-)

Hello,
I try to solve problem 1209 with allocating memory, but i receive compilation error.

---------------------------------------------------------
e2c33114-a1cd-488e-b50b-9a2950afaee7
e2c33114-a1cd-488e-b50b-9a2950afaee7(8) : error C2143: syntax error : missing ';' before 'type'
e2c33114-a1cd-488e-b50b-9a2950afaee7(19) : error C2065: 'AA' : undeclared identifier
e2c33114-a1cd-488e-b50b-9a2950afaee7(19) : error C2109: subscript requires array or pointer type
e2c33114-a1cd-488e-b50b-9a2950afaee7(24) : error C2065: 'AA' : undeclared identifier
e2c33114-a1cd-488e-b50b-9a2950afaee7(24) : error C2109: subscript requires array or pointer type
e2c33114-a1cd-488e-b50b-9a2950afaee7(30) : error C2065: 'AA' : undeclared identifier
e2c33114-a1cd-488e-b50b-9a2950afaee7(30) : error C2109: subscript requires array or pointer type
e2c33114-a1cd-488e-b50b-9a2950afaee7(32) : error C2065: 'AA' : undeclared identifier
e2c33114-a1cd-488e-b50b-9a2950afaee7(32) : warning C4022: 'free' : pointer mismatch for actual parameter 1
---------------------------------------------------------


Code example:
---------------------------------------------------------
#include <stdio.h>
#include <malloc.h>

int main()
{
        int N;
    scanf("%d", &N);
    int *AA = (int *)malloc(N*sizeof(int));
        ... ... ...
        free(AA);
        return 0;
}
---------------------------------------------------------
What the matter ?

Thank you for answers.

Edited by author 12.01.2011 23:44

You can go from last digit to the first (the leftmost digit to the rightmost digit).

For example : 302

Considering 2 : There are some possibilities: 0 + 2, 1 + 1, 2 + 0, 6 + 6, 5 + 7 ... (first operant is of the larger number, second operant is of the smaller number).

Considering 0 : For each possibilities, you try to find out some possibilities that can be combined to produce 0 : 0 + 0...
You can try any combinations to produce 0 if two operants used to produce 2 is equal, if they are different, you only have an only way, it reduce very much calculations).

Considering 3 : The last digit, you can stop here and consider whether you have achieved a solution.

It helped me to get AC.

Test:
1 +
1 +
1 +
10 . 2
11 . 3
600 +
601 . 1
609 . 2
611 . 3

Right answer:
1
2
3
+
+
4
-
+
-