What does it mean? Runtime error (access violation)
This is my code on c++
#include <iostream>
using namespace std;
int n,ans;
string s;
int main()
{
    cin>>n;
    ans=n+2;
    for(int i=0; i<n; i++)
    {
        cin>>s;
        for(int j=0; j<s.size()-3; j++)
        {
            if(s[j]=='+' && s[j+1]=='o' && s[j+2]=='n' && s[j+3]=='e')
            {
                ans++;
                break;
            }
        }
    }
    if(ans==13) ans++;
    cout<<100*ans;
    return 0;
}

Edited by author 31.05.2017 21:40

I used the same code

The answer is either one or zero.
The answer is one when all the children tastes are lying on the same straight line. And the best friends are two children with maximal possible distance between their tastes.

You can just brute force all possible points on the grid.  For every point check whether that point is under attack. So,  your grid is just a SZ*SZ square matrix.  SZ=200 is accurate enough,  and even somewhat smaller values are OK.

You can solve it using :
(1) canonical straight line formula for perpendicular length ;
(2) cosine theorem to know whether your perpendicular length is the answer to the first question or not;
(3) Just formula for Euclidian distance and maximum function to answer the second question.

For those who couldn't do straightforward O(n^2) with tricks.
Think of < as 0 and > as 1.
Every time you see >< (10) you replace (swap) it with <> (01).
Which means, you stop as soon as you get sorted stuff, 0*1*.
Doesn't it look like count of swaps in bubblesort? :)

I originally read the problem statement as stating that the radius could only be up to 1000 in length. Hence, I was really confused when everyone was saying the problem was really easy. But that nightmare is behind me now.

I never figured out how to do it with that kind of restriction of the radius in under 1 second. What would be the optimal algorithm to use for that case?

Мне кажется, что моя формула верна.
Пусть f(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём любые два соседние числа различны; g(n)=кол-во последовательностей длины 2*n,содержащие числа 1,1,2,2,...,n,n, причём существует только одна пара соседних равных чисел.
Тогда f(n)=n*(2*n-2)*f(n-1)+n*g(n-1), g(n)=n*(2*n-1)*f(n-1)+n*g(n-1) => f(n)=g(n)-n*f(n-1) => g(n-1)=f(n-1)+(n-1)*f(n-2) => f(n)=n*((2*n-1)*f(n-1)+n*(n-1)*f(n-2)).
f(1)=0, f(2)=2 (mod p).
Ответ на задачу f(n-1) mod p.

Хотелось бы увидеть ответы на следующие тесты:
5 10000000
6 10000000
7 10000000

Edited by author 29.05.2017 13:01

И все же...
Что там за набор такой?

Edited by author 12.06.2017 20:33

solved. thanks

Edited by author 26.12.2013 09:01

I used scanline to solve this problem. This method is shown
here: http://e-maxx.ru/algo/length_of_segments_union. All the given points are put in array with 2n+m elements, each point having one of 3 types: start of a segment(0), end of a segment(2), a point for which the answer is needed (1). Then the array is sorted, and we go througth its elements: if the element has type 0, then we insert according segment into the set, if the element has type 2, then we delete according segment from the set, if the element has type 1 then we take the segment of minimum length from set in O(1), and output its id. The complexity is O((2n+m)log(2n+m)) (quicksort).

Edited by author 09.02.2016 14:53

Hi! I use greedy algorithms and can't get past first test. Could someone please provide me with some tests? I tried these tests with following results:
1
-1 0
-5 -3
2 5
0 0
-----------
No solution

1
-1 0
0 1
0 0
-----------
0 1

10
-5 1
1 14
-5 2
2 3
3 19
0 0
---------
-5 2
1 14

5
-5 0
0 1
1 2
2 3
4 5
3 4
10 49000
0 0
---------
0 1
1 2
2 3
3 4
4 5

4
0 4
-5 0
3 4
-4 4
0 0
-------
-4 4

6
0 5
7 8
0 0
-------
No solution

10
0 9
0 0
-------
No solution

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


public class Main {

    private static final BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static final PrintWriter out = new PrintWriter(System.out);
    private static final StreamTokenizer tok = new StreamTokenizer(in);

    public static void main(String[] args) throws IOException
    {
        int windowSize = nextInt();
        Queue<Integer> q = new LinkedList<Integer>();
        Deque<Integer> maxQ = new LinkedList<Integer>();
        while(true)
        {
            Integer n = nextInt();
            if(n == -1)
                break;
            q.add(n);
            while((maxQ.isEmpty() == false) && (maxQ.peekLast() < n))
                maxQ.removeLast();
            maxQ.add(n);
            if(q.size() == windowSize)
            {
                Integer elemToRemove = q.remove();
                Integer maxElement = maxQ.peek();
                out.println(maxElement);
                if(maxElement == elemToRemove)
                    maxQ.remove();
            }
        }
        out.flush();
    }

    private static int nextInt() throws IOException
    {
        if(tok.nextToken() != StreamTokenizer.TT_NUMBER)
            throw new IOException();
        return (int)tok.nval;
    }

}

//note, though there's while loop to remove elements from maxQ,
//amortized comlexity is still O(n)

So at first I got AC in 68 ms using scanf("%c", *char)  and then I replaced scanf with_getchar_nolock()  and got AC in 46 ms...

If you got Median on the Plane AC you can get Akhbardin roads AC with the same code (with minimal changes).

Maybe you are using expressions like (n-j) for j=0...n-i-1 and 0-indexing when checking diagonals.  So,  (n-j)  results in WA #8. Correct expression is (n-1-j)

Since n^m can be very large (n,m <= 50), does one need BigInteger? I would not want to do it, since I've already started coding the whole thing in C++...

Use Manacher's algo for comprehensive list of palindroms and try to calc 2 arrays:
beg[i] - number of palindroms begins at position i,
end[i] - number of palindroms ends at position i.
after that ans = beg[i + 1] * end[i] for every i.

To calc arrays you can use either O(n) offline (+=cnt at beg -= cnt after end; then sum) or efficient data structures.

Edited by author 22.05.2017 20:40

Пролистал кучу форумов, нахожу везде очень сложные формулы, может я слишком загоняюсь и есть какой то простой алгоритм решения? Кто нибудь может помочь?