I had a problem with parsing the input. It turns out that my logic is fine but got WA3 because it is the first test where the longtitude has 3 digits degrees value.

I don`t remember Pascal. In C expression 6875/2 means 3437, not 3437.5

I don't know java, but probably it would help you: i think answer in second test is 1 and test is smth like
3
1 2 3
my prog printed 0 in such a case, while right answer is 1, that's why i had wa... maybe there is same problem in your algo?

Can anybody give me test for WA #29???

I understood solution of this problem, but now I have Crash access vialation at test #4. Why???

I've solved this problem without DP. I used recursion. Time is 0.062, memory - 125 KB.

there is more than one way between two spot

There many ways:
1) hash
2) suffix array
3) suffix tree
4) suffix automation

I used DP on trie.

For example, such test:
(*)
Right answer: NO

I have also WA2, but do not know why...
Any new ideas aboubt damn test 2!?
I am going crazy...

#include <cmath>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <set>
#include <algorithm>

#define FOR(i,to) for (int i = 0; i < int(to); ++i)
#define SZ(a) a.size()

using namespace std;

string text;
bool coment = false;
bool formula = false;
bool good = true;
int open = 0;
int main ()
{
    while (feof(stdin))
    {
        char buf[10000];
        gets(buf);
        text += string(buf);
    }
    FOR(i,SZ(text))
    {
        if (coment)
        {
            if (text[i] == '*' && text[i+1] == ')')
            {
                i++;    coment = false;
            }
            continue;
        }
        if (formula)
        {
            if (text[i] == '(' && text[i+1] == '*')
            {
                i++;    coment = true; continue;
            }
            if (text[i] == '(')
            {
                open++; continue;
            }
            if (text[i] == ')')
            {
                open--;
                if (open==0)
                    formula = false;
                continue;
            }
            if (strchr("=+-*/0123456789", text[i]) == NULL)
            {
                good = false; break;
            }
            continue;
        }
        if (text[i] == '(')
        {
            if (text[i+1] == '*')
            {
                i++;
                coment = true;
                continue;
            }else{
                open++;
                formula = true;
                continue;
            }
        }
        if (text[i] == ')')
        {
            good = false;
            break;
        }
    }
    if (good && !coment && !formula)
        printf("YES\n");
    else
        printf("NO\n");

    return 0;
}

if u have got a problem with test # 2 try this test

'(*' correct answer is NO

I think that this is not valid..

T.T



Edited by author 03.07.2009 03:52

юзай сжатый бор

Since you have only 10000 vertices, you can use short int for children links, and then you will fit into 8 Mb

We added this test, but you are the only author who got WA on it. :)

my WA on test 30 was because, I forgot:
"If the pointer before increment points to the rightmost byte of the array, then after increment it points to the leftmost byte."
and
"If the pointer before decrement points to the leftmost byte of the array, then after increment it points to the rightmost byte."

In the statement it is said, that you may assume to use at most 4 bytes, but it is not said WHICH four bytes.. In the case of test 30, the best four are the rightmost one and the three leftmost.

However, now I'm stuck on 31...