|x|, |y| > 2^32

Я написал рекурсию которая каждый раз делила отрезок на два и брала максимальный среди ответа всех таких отрезков которых поделила.(типо Merge Sort). У меня был memory limit на 3 тесте. Это значить рекурсия берет память?

n,k = map(int,input().split())
if k==1 or n==1:
    print(2*n)
else:
    if 2*n%k==0:
        print(2*n//k)
    else:
        print(2*n//k+1)

N,M  = map(int,input().split())
k = []
for _ in range(M):
    m = int(input())
    k.append(m)
for i in range(1,N+1):
    print(f"{k.count(i)*100/M:.2f}%")
Time limit please help

What does it mean: "reach smth"?
It's a strict condition, but how should i understand it?)
In my opinion, this sample has two right answers:
4
0 0
0 1
0 5
0 8
2 * (1.5 * 1.5) * M_PI or (1 + 3 * 3) * M_PI.

input:
2 8
12 28 40 46
48 54 60 80
2 7
9 24
34 49
54 62
66 77
78 79
80 83
84 84

output:
6

input #1:
3
110

output #1:
YES

input #2:
4
1110

output #2:
NO

Edited by author 24.02.2026 17:26

12
12 5 3 11 2 8 4 9 1 6 10 7

answer: 34650  in example output.

But, following full check test prints 6300.

-----
static bool match(int a[], int n, int b[], int m){
    if (n != m) return false;
    if (n == 0 && m == 0) return true;

    int i = std::max_element(a, a + n) - a;
    int j = std::max_element(b, b + m) - b;

    return i == j && match(a, i, b, j) && match(a + i + 1, n - i - 1, b + j + 1, m - j - 1);
}
int main()
{
        int n = 12;
        int a[] = { 12, 5, 3, 11, 2, 8, 4, 9, 1, 6, 10, 7 };
        int b[] = {  1, 2, 3,  4, 5, 6, 7, 8, 9, 10, 11, 12};
        int ans = 0;
        do{
            if (match(a, n, b, n)) ++ ans;

        } while (std::next_permutation(b, b + 12) );

        printf("ans = %d\n", ans);
        return 0;
}

I solved it using pretty straigtforward DP O(n * m^2), obviously it's just a complexity without any additional factors but it doesn't seem to be fitting time limit. Somehow it did. But I wonder, is there any more intricate idea for a faster solution?

how to know when there are no more inputs

Что за 26 тест? Никак не могу его победить

why wa#17?
help pls

Edited by author 23.11.2018 08:05

New tests have been added. All accepted solutions have been rejudged. 15 out of 20 authors lost the Solved status for this problem.

def word_to_num(word):
    d=
{'a':'2','b':'2','c':'2','d':'3','e':'3','f':'3','g':'4','h':'4','i':'1','j':'1','k':'5','l':'5','m':'6','n':'6','o':'0','p':'7','q':'0','r':'7','s':'7','t':'8','u':'8','v':'8','w':'9','x':'9','y':'9','z':'0'}
    s=''
    for i in word:
        s+=d[i]
    return s
from itertools import permutations
while True:
    num_dict={}
    num_list=[]
    word_list=[]
    num = input()
    if num=='-1':
        break
    loop_len = int(input())
    for i in range(loop_len):
        word_list.append(input())
    for item in word_list:
        num_dict[word_to_num(item)]=item
        num_list.append(word_to_num(item))
    perm = permutations(num_list,2)
    x=0
    for k,v in list(perm):
        if k+v==num:
            print(num_dict[k]+' '+num_dict[v])
        else:
            x += 1

    if x==loop_len*(loop_len-1):
        print('No solution')

Правда вне рейтинга:)

One way I can think of is to sort edge by cost
and use dynamic connectivity

But it's very hard to implement :(
What's the better solution?

O(n*sqrt(n)*log(n)) enough?

Upd: OK with this complexity. But 2.7 c++. How to solve with 0.1 second?

Edited by author 21.02.2026 00:26

Any way to remove test miners from the board?

Oleg Vasilenko (Chelyabinsk) - https://acm.timus.ru/status.aspx?space=1&num=1589&author=55499&from=10681678

Ruben Ashughyan - https://acm.timus.ru/status.aspx?space=1&num=1589&author=202317&from=10649282

kostan3 - https://acm.timus.ru/status.aspx?space=1&num=1589&author=121982 (looks suspicious, is it a system account or something?)

Can you give me some "extra" test or smth like that... My prog passed all my tests but i get wa#3...

Thnx!