My program will not work if inside <blog> tag will be nested <blog>. It does not happen in tests, but I suggest to add notice to the statement that <blog> tag can be only top level and cannot be nested.

Alternatively test like this may be added:
2
a
<blog>
<blog>
</blog>
b
<blog>
<friend>b</friend>
</blog>
</blog>
b
<blog>
</blog>

finally I solved this using DC3 algorithm (a linear suffix array construction algoritm). it's supposed to run in O(n) time. my java solution runs in ~1.17 but my main language is scala and in scala (the escat same algorithm) is above 2 sec.
is it possible to solve this with KMP faster? i couldn't find a correct solution.

My solution is based on the next idea. When we check the current contestant we should know if there exists such vector x = (x0, x1, x2) that for every i = 1..n - 1 scalr product (v_i,x) > 0. I use simplex-method to solve this problem with such inequalities:
(v_0, x) >= EPS
(v_1, x) >= EPS
...
(v_n-1, x) >= EPS
x0 >= EPS
x1 >= EPS
x2 >= EPS
x0 + x1 + x2 <= 1500

BUT I HAVE TLE on test 21. I couldn't improve my simplex-method implementation.
Any who solved this problem using algebra, please, give me some hints. Thank you.

I'm using inclu-exclu.
Start from B and then add and minus.
But always WA#3.

Any hints?

Thansk,
Ade

Good problem, thanks to author!

4 5 1
196

6 10 1
4656

15 27 4
0

2 4 1
40

2 4 2
24

2 4 3
24

2 4 20
24

2 4 4
30

2 4 5
30

23 24 5
0

1 4 6
385

3 4 50
66

Edited by author 13.06.2014 14:08

What the main of this problem?I can't understand it.Help,help!

#include<bits/stdc++.h>
using namespace std;
int horse[510],i;
long long mem[501][501];
long long count(int index,int left)
{
    if(index==i&&left==0)
    return 0;
    if((index==i&&left>0)||(index<i&&left==0))
    return 1000000;
    if(mem[index][left])
    return mem[index][left];
    int v=0,j=0,k;
    long long mini=1000001;
    for(k=index;k<i;k++)
    {
        if(horse[k])
        v++;
        else
        j++;
        mini=min(mini,v*j+count(k+1,left-1));
    }
    return mem[index][left]=mini;
}
int main()
{
    int j,k,l;
    cin>>i>>j;
    for(k=0;k<i;k++)
    cin>>horse[k];
    cout<<count(0,j)<<endl;
    return 0;
}

You may run it on your own computer.
Then you'll get the all answers.
Then......Got AC!!!

I ran the program for 2.5 hours in all!!!

1. "За один ход можно перевернуть одну фишку и все соседние по горизонтали или вертикали с ней."

Instead of "или" should be used "и". ("vertically and horizontally")


2. "Предписания комбинации на переворачивание фишек, попадающих за пределы поля, игнорируются."

Hard to understand. Most clear will be: "Если ход попадает в клетку на границе поля, переворачиваются только те фишки, которые находятся в его пределах".

if the number of digits is greater than 100,  should print "No solution"

First version give wrong answer on 1. Second version - OK.

Why?

What does 'system of bricks' (or 'система кирпичей' in russian statement) mean?

#include <queue>
#include <iostream>
#include <set>
#include <cstdio>
#include <algorithm>
#include <string>
#include <map>
#include <string>
#include <sstream>
using namespace std;
bool k(long double x)
{
    long double t=floor((sqrt(x)));
    if (t*t==x)
    {
        return true;
    }
    else
        return false;
}
int main()
{
    long double n;

    scanf("%lf",&n);
    long long c=n;
    if(k(n))
    {
        cout<<1;
        return 0;
    }

    for(long int i=1;i<=sqrt(n)/2+2100000;i++)
    {
        long double q=n-i*i;
        if(k(q))
        {
            printf("%d",2);
            return 0;
        }
    }
    for(long int i=sqrt(n);i>=sqrt(n)-2100000;i--)
    {
        long double q=n-i*i;
        if(k(q))
        {
            printf("%d",2);
            return 0;
        }
    }
    long long q = (long long)n;
    for ( int i = 0; i <20; i ++)
    {
        long long d = 1;
        for ( int j = 0; j < i;j++)
        {
            d*=4;
            if ( q > n)
            break;
        }
        if ( d > q)
            break;
        if( (long long)q % d==0)
        {
            long long temp = q/d - 7;
            if ( temp %8==0)
            {
                printf("%d",4);
                return 0;
            }

        }
    }

    printf("%d",3);
    return 0;
}

What is the solution for n = 10?

var
n,r,c,i,k:integer;

begin
readln(k);
write(' ');
read(n);

writeln;
r:=0;
for i:=1 to n do
begin
read(c);
write(' ');
if r<0 then r:=0;
r:=r+c-k;
end;

if r<0 then writeln('0')
else writeln(r);

end.

Do you know what's the test 29?

Edit: got the AC.

Edited by author 03.07.2012 14:20

import java.util.*;

public class Test_1874 {
    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner s = new Scanner(System.in);
        int h, w, n;
        h = s.nextInt();
        w = s.nextInt();
        n = s.nextInt();

        String[] a = new String[n];
        for (int i = 0; i < n; i++) {
            a[i] = s.nextLine();
            if (a[i].isEmpty()) {
                a[i] = s.nextLine();
            }
        }

        if (n == 1) {
            System.out.println("1");
            return;
        }

        int b, c = 0, d = 0, list = 0, page = 0;

        for (int i = 0; i < n; i++) {
            b = (a[i].length() + 1);

            if (i == 0) {
                c = a[i + 1].length();

                if (b + c == w) {
                    list++;

                } else if (b + c < w) {
                    d = b + c;
                    c = a[i + 2].length();
                    if ((d + c) == w) {
                        list++;
                    } else if ((d + c) < w) {

                    } else {
                        list++;
                    }
                } else {
                    list++;
                }
            } else {

                if ((b + d) == w) {
                    list++;

                } else if ((b + d) < w) {
                    d = d + b;
                    c = a[i + 1].length();
                    if ((d + c) == w) {
                        list++;
                    } else if ((d + c) < w) {

                    } else {
                        list++;
                    }
                } else {
                    list++;
                }

            }

            if (list == h) {
                page++;
                list = 0;
            } else if (i == (n - 1)) {
                if(list>=1){
                    page++;
                }

            }

        }
        System.out.println(page);

    }
}

//*********************************************
//FreePascal 2.0.4
var a,b,u:longint;
begin readln(a,b);
for u:=1 to b do inc(a);
writeln(a);
end.

//*********************************************
//Visual C# 2010
using System;
public class Sum
{
    private static void Main()
    {
        string[] tokens = Console.ReadLine().Split(' ');
        Console.WriteLine(int.Parse(tokens[0]) + int.Parse(tokens[1]));
    }
}

//*********************************************
//Java 1.7
import java.util.Scanner;
public class test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(sc.nextInt() + sc.nextInt());
    }
}

import java.util.*;

public class Test_1874 {

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner s = new Scanner(System.in);
        int n, k, m;

        n = s.nextInt();
        k = s.nextInt();

        long[] a = new long[k];
        for (int i = 0; i < k; i++) {
            a[i] = s.nextInt();
        }
        for (int i = 1; i < k; i++) {
            if (a[i] < a[i - 1]) {
                m = (int) a[i];
                a[i] = a[i - 1];
                a[i - 1] = m;
            }
        }
        m = (int) (n - (n - a[0]) - (n - a[1]));
        if (m <= 0) {
            System.out.println("0");
        } else {
            System.out.println(m);
        }
    }
}