I think the answer is probablye Yes...

Be sure that(at least for the given interval, [4,2*10^9]) every even number can be shown as sum of two prime numbers.

1. if n is prime, {n}
2. if n is even, {n = p1 + p2}
3. if n is odd   {n = 3 + p1 + p2} ( n-3 is even, so that recall second case.)

For convenience, prime numbers under 10^5 can be initialized.

Edited by author 03.12.2012 03:00

Edited by author 03.12.2012 03:00

Weird.

Edited by author 12.01.2019 12:15

C++ costs 200 kb (Visual C++ and 400 kb other compilers).

When do we go from one-dimensional array to two-dimensional? This will be so rad!

I got an AC with dynamic programming and without a graph and I am frustrated with my memory consumption. I used C++ for this and i've got 0,31s and 16000 KB. I guess my solution consumed so much memory because I've stored 2 matrices, one for grid second for diagonales.

Matrix[i][j] = min (Matrix[i-1][j]+100, Matrix[i][j-1]+100, Matrix[i-1][j-1] + Diag[i][j])
where Diag[i][j] is either 100 * sqrt(2) or Infinity.
I wonder if there is a better solution. I think a simple BFS could give me an answer, Bellman-Ford and Dijkstra's algorithms will give it for sure though. Nevertheless, I've never worked with a graph where every vertex is a 2D point. How should i store it? vector <int> g[maxN][maxN] ? How do I fill it with values efficently?

(yes, somehow I've got wa15)
try this test (it helped me to get AC):
10 3
7 7 7

#include <iostream>
using namespace std;

/// A BST...
struct Node
{
    double data;
    struct Node *left, *right;
};
///function to create new Node in BST
struct Node *newNode(double item)
{
    struct Node *temp = new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
///function to insert a new Node
/// with given key in BST
struct Node* insert(struct Node *node, double key)
{
    ///if tree is empty, return a new node
    if(node==NULL)
        return newNode(key);
    ///otherwise, recur down the tree..
    if(key <node->data)
        node->left = insert(node->left, key);
    else if (key >node->data)
        node->right = insert(node->right, key);

    return node;
};

double counNodes(struct Node *root)
{
    struct Node *current, *pre;

    double count = 0;
    if(root==NULL)
        return count;

    current=root;
    while(current!=NULL)
    {
        if(current->left==NULL)
        {
            count++;
            current=current->right;
        }
        else
        {
            pre = current->left;
            while(pre->right !=NULL &&
                  pre->right !=current)
                    pre = pre->right;
            if(pre->right==NULL)
            {
                pre->right=current;
                current = current->left;
            }
            else
            {
                pre->right = NULL;

                count++;
                current = current->right;
            }
        }
    }

    return count;
}

///Function to find median in o(n) time and O(1) space...
double findMedian(struct Node *root)
{
    if(root == NULL)
        return 0;

    int count = counNodes(root);
    int currCount = 0;
    struct Node *current = root, *pre, *prev;

    while (current!= NULL)
    {
        if(current->left == NULL)
        {
            currCount++;
            ///odd case..
            if(count %2 !=0 && currCount == (count+1)/2)
                return prev->data;
            ///Even case...
            else if(count%2==0 && currCount == (count/2)+1)
                return (prev->data + current->data)/2;

           ///Update prev..for even no. of nodes...
           prev = current;

           current = current->right;
        }
        else
        {
            ///Find inorder predecessor of current...
            pre = current->left;
            while(pre->right!= NULL && pre->right!=current)
                pre = pre->right;
            /// make current as right child of in. pre.dec.
            if(pre->right == NULL)
            {
                pre->right = current;
                current = current->left;
            }
            /// revert the changes.. made in if part
            /// to restore the original tree.. , fix the right chid of predecessor...

            else
            {
                pre->right = NULL;
                prev = pre;

                currCount++;

                if(count%2!=0 && currCount == (count+1)/2)
                    return current->data;
                else if (count%2!=0 && currCount == (count/2)+1)
                    return (prev->data+current->data)/2;
                ///Update...for even case...

                prev = current;
                current = current->right;
            }
        }
    }
}

int main()
{
    struct Node *root = NULL;
    int n;
    double x;
    cin >> n;
    cin >> x;
    root = insert(root, x);
    for(int i=1; i<n; i++)
    {
        cin >> x;
            insert(root, x);
    }
    //cout << findMedian(root);
    //if(n%2==0)
        printf("%.1f", findMedian(root));

}

if your store data in array of pairs begin loop from zero i=0 not from 1!

[deleted]

Edited by author 21.05.2019 23:17

Online tests surely contain several tests in one file, so:

1. Be sure clean your dictionaries before every test.
2. Be sure read ALL lines of current test, even you got correct answer before all input was used.

This two issues were the reason of my WA1. After fixing them I got "Accepted".

Use the following test to validate mentioned above points:

100
5
5 6 odd
7 8 odd
1 6 even
1 4 odd
7 8 even
3
3
1 1 odd
3 3 odd
1 3 odd
5
4
1 2 even
4 5 even
1 5 odd
3 3 even
10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
20
8
1 9 odd
10 17 odd
18 26 odd
4 5 odd
27 40 even
21 40 odd
1 20 odd
10 20 odd
200
8
1 9 odd
10 17 odd
18 26 odd
4 5 odd
27 40 even
21 40 odd
1 20 odd
10 20 odd
-1
Answer:
4
3
3
3
2
6

Спасибо парню из предыдущей ветки,лично мне это реально помогло
Короче смысл в том,что в 7 тесте либо координаты A совпадают с координатами какой-нибудь станции (или тоже самое с B),либо у нескольких станций одинаковые координаты.

Ну и прикол в том,что если вы строите матрицу смежности,то он будет считать что там нет пути, 0 же стоит

the main difficulty here was to understand that you need to use <string>
#include <iostream>
#include <string>
using namespace std;
int main() {
    int n; string arr[4] = { "16", "06", "68", "88" };
    cin >> n;
    if (n <= 4)
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
    else
        cout << "Glupenky Pierre";
}

My Accepted solution 8202681 for problem 1050 gives incorrect answer on my test (test contains command '\endinputany' in the middle of text).
Please add my test to test package.

     TEST:
There is no "q in this sentence. \par
"Talk child," said the unicorn.

\endinputany
She s\"aid, "\thinspace `Enough!', he said."
\endinput

     INCORRECT ANSWER:
There is no q in this sentence. \par
``Talk child,'' said the unicorn.

\endinputany

     CORRECT ANSWER:
There is no q in this sentence. \par
``Talk child,'' said the unicorn.

\endinputany
She s\"aid, ``\thinspace `Enough!', he said.''
\endinput

Judjes tell me after you read my message, I will delete
an AC program.

Here is th 1st program it got WA#3:

[Program was deleted by author, beacuse it got AC =)]
[Thx Vladimir! Judges if you need it, I can post it.]


Here is 2nd program it got AC:

[Program was deleted by author]
[Judges if you need it, I can post that code for a while]

Here is one test:
318 330

Correct answer is 323 (Triviality(323)=0.114551)
AC programs answer for this tests was :
324 (Triviality(324)=1.619195)

It means that AC program gave incorrect answer, but
program which got WA#3 gave correct answer!!!
It's shameful!!!

Edited by author 20.01.2006 20:49

Edited by author 21.01.2006 02:45

Why is triviality(1)=1?

What is the test #11?Give,please......

I am using DP, it works for all TC on discussion. what could be wrong?