I don't understand how the answer can be 15.

Since the first 2 people got 0 correct predictions and the last person got 1 correct prediction, shouldn't the amount paid only be 5?

dp[i][j] - represents number of staircases with i cubes and with the height of last block j.
Answer is dp[n][1] + dp[n][2] + dp[n][3] ... dp[n][n].

At first check all tests with n<=4. If all of them cheked already then try to check all cells for n=8 (1/1; 1/2; 1/3; 1/4; 2/2; 2/3....)and for n=9. Don't be afraid you'll find your mistake on first tests))

Edited by author 10.07.2016 14:33

can someone give me some tips or tests?

#include <iostream>
#include <math.h>
#include <iomanip>

using namespace std;

int main()
{
    double a[100000];
    int i, n;
    cin >>n;
    for (i=1; i<=n; ++i)
    {
        cin>>a[i];
    }
    for (i=1; i<=n; ++i)
    {
        a[i] = sqrt(a[i]);
    }
    for (i=n; i>=1; --i)
    {
        cout << fixed << setprecision(4) << (a[i]) << endl;
    }
}

What is the criterion of optimality of the partition ?

По условию может быть так(.-пробел):.........aaa.bbb.ссс.
                                    .....xxx.aaa.bbb.ccc.
                                    или
                                    .........aaa.bbb.ссс........
                                    .....xxx.aaa.bbb.ccc........???????
И вообще,как в ЭТОЙ задаче считывать данные(на Паскале)?

Edited by author 08.07.2016 21:27

I tested my prog but I not found mistake

public class AB {
public static void main(String [] args) {
int a = 1;
int b = 5;
System.out.println((a+b));
}
}

var m,n:word; i:word;
begin
  readln(m,n);
  for i:=1 to n do
  begin
    write(i,' ');
  end;
  writeln;
  for i:=1 to m do
  begin
    write(i*n+1,' ');
  end;
end.

What test is wrong with it?

Edited by author 07.07.2016 17:05

import re
fl = re.compile('[+-]?[1234567890]*\.[1234567890]*([Ee][+-]?[1234567890]+)?')
lf = re.compile('[+-]?[1234567890]+([Ee][+-]?[1234567890]+)?')
nums = []
while True:
    first = input()
    if first == '#':
        break
    nums.append((first, int(input())))
for num in nums:
    num0 = num[0]
    if not (re.fullmatch(fl, num0) or re.fullmatch(lf, num0)):
        print('Not a floating point number')
        continue
    try:
        e_pos = num0.index('e')
        exp = int(num0[e_pos + 1:])
        num0 = num0[:e_pos]
    except:
        try:
            e_pos = num0.index('E')
            exp = int(num0[e_pos + 1:])
            num0 = num0[:e_pos]
        except:
            exp = 0
    pm = num0[0]
    if pm in ['+', '-']:
        num0 = num0[1:]
    else:
        pm = '+'
    if pm == '+':
        pm = ''
    if exp > 0:
        num0 += '0' * exp
    elif exp < 0:
        num0 = '0' * (-exp) + num0
    try:
        dot_pos = num0.index('.')
    except:
        dot_pos = len(num)
        num0 += '.'
    new_dot_pos = dot_pos + exp
    num0 = num0[:dot_pos] + num0[dot_pos + 1:]
    num0 = num0[:new_dot_pos] + '.' + num0[new_dot_pos:]
    while num0.startswith('0'):
        num0 = num0[1:]
    if num0.startswith('.'):
        num0 = '0' + num0
    num0 += '0' * num[1]
    num0 = num0[:num0.index('.') + num[1] + 1]
    if num0.endswith('.'):
        num0 = num0[:-1]
    print(num0)

My program (with error, I know where it is, but I will not write about it):
import sys
text = sys.stdin.readlines()
text = ''.join(text)
for symbol in ',;:-\n':
    text = text.replace(symbol, ' ')
text = text.replace('!', '.').replace('?', '.')
import re
text = ' '.join(text.split())
text = text.replace('. ', '.')
text = '.'.join(text.split('.'))
text = text.replace(' .', '.')
count = 0
for sentence in text.split('.'):
    if sentence != '':
        if sentence[0].islower():
            count += 1
        for word in sentence.split():
            for letter in word[1:]:
                if letter.isupper():
                    count += 1
print(count)

Edited by author 06.07.2016 19:17

I wrote 1009 and had AC, then I added long arifmetics, changing nothing and now I have WA#1.
All test from 1009 are simmilar to 1012. What is test 1. Is it possible because of using
   stringstream out;
   out <<  k-1;
   mas[1] = out.str();
?

Edited by author 05.07.2016 21:07

just need examples. I have no idea where is my mistake

Can the knight run back and forward on the segment? Does it count as run up?

Example:

The monster is at (1,3), the knight is at (1,1)

If the knight does
(1,1) -> (1,2) -> (1,1) -> (1,2) -> Strike
the strike force is 4 or 2?

Thanks in advance

If your algo is correct, then maybe the problem is the way you build the tree.

Try this test:

5 2
3 1 1
4 1 10
2 3 20
3 5 20

Hope this test can help you.

GC.Collect();
on each iteration has helped

why my O(N * M) solution works for 2.65 seconds?
I think 9 * 10^6 operstions should be done faster...