I have 'Time limit exceeded' after 13 test.

Возможно ли решить данную задачу на Питоне? У меня после 13 теста лимит времени исчерпан.

Advertisement contains up to 100000 symbols and ends with a newline.

So may need to store 100000 symbols + newline symbol + one '\0' symbol.

I had problems with this using fgets in C++.

Can it be faster than O(M^2)?

?

There are for n=1..60 all values already exist in internet.

Only required calculate for n=61.
But it takes more 20 hours.

For some, task No. 1033 seemed simple.
A new task is offered especially for them (don't say it's difficult!)
A multidimensional maze (also with wallpaper, walls and entrances).
The input data consists of two sequences of numbers.
The sign of the end of each sequence is zero (it is not part of the sequence).
The first sequence:
Guaranteed: the sum of the modules of the numbers does not exceed 1E+7.
The number of negative numbers is equal to the number of entrances to the maze.
The number of positive numbers is equal to the number of monolithic blocks of stone walls.
Sk=The sum of the modules of the numbers from the beginning determines the unique number of the place in the maze.
The second sequence is the numbers N[i] defining the sizes of the maze.
Guaranteed: 1<N[i]<32
The length of the sequence (d) is equal to the dimension of the maze.
These numbers themselves set the sizes of the maze according to the (i-th) coordinate.
Knowing Sk, it is possible to determine all d coordinate values of a unique place in the maze.
Sk=R[d]+1 where R[0]=0 and R[i+1]=R[i]*N[i]+THE_COORDINATE[i]

Result:
the same as in task No. 1033
P.S. Memory needed ~ 4Mb O(SM). Time limit - O(SM*log(SM)) where SM-the sum of the modules of the numbers

Некоторым задача №1033 показалась простой.
Специально для них предлагается новая задача (не говорите,что сложная!)
Многомерный лабиринт (тоже с обоями,стенами и входами).
Входные данные состоят из двух последовательностей чисел.
Признак конца каждой последовательности - ноль(не является частью последовательности).
Первая последовательнось:
Гарантировано: сумма модулей чисел не превосходит 1Е+7.
Количесво отрицательных чисел равно количеству входов в лабиринт.
Количесво положительных чисел равно количеству монолитных блоков каменных стен.
Sk=Сумма модулей чисел от начала определяет уникальный номер места в лабиринте.
Вторая последовательность: Числа N[i] задающие размеры лабиринта.
Гарантировано: 1<N[i]<32
Длина последовательности (d) равна размерности лабиринта.
Сами эти числа задают размеры лабиринта по (i-той) координате.
Зная Sk можно определить все d значений координат уникального места в лабиринте.
Sk=R[d]+1 где R[0]=0 и R[i+1]=R[i]*N[i]+КООРДИНАТА[i]

Результат:
тот же что и в задаче №1033
P.S. Надеюсь, что удалось объяснить.

Edited by author 03.01.2025 06:52

:(

1) кучи должны быть одинаковыми?
2) если нет то почему нельзя взять самое маленькое число и вычесть из него остальные?

А тестов ровно 128?

Only KS can be skipped but not KD KC KH

if you have a WA5, it is possible that you also did not read the condition, and instead of a 5000 bill you wrote something else (for example, 2000).

Edited by author 29.12.2024 14:51

Looks like Noise function acts like in real world. It is some random variable from normal distribution with zero expected value, and some small variation

Edited by author 27.12.2024 03:35

For a positive integer x, we define R(x) as a number equal to the inverted x in decimal notation. For example, R(123) = 321, R(1) = 1, and R(100500) = 5001.

For a given number S, calculate the number of integers x such that 1 ≤ x and x+R(x) ≤ S.

As an answer, print the remainder of dividing this number by 10^9 + 7.

Input data contains an integer S written without leading zeros (0 < S < 10^100000).

Test: 1000000 Answer: 505449

The idea: the dynamics of the digits of the number?
What other ideas can you suggest?

Im using BFS to find shortest way from S to F, BFS to count dists, BFS to count probability on shortest ways. I tried c++ vectors and arrays, both are getting TLe

Maybe cause is long double values (three BFS can pass in 1 second). How can I fix it? Maybe Dijkstra on two parameters?

O(N*logN) or O(N+max(P))?

It seems, the only solution to this problem is recursion with correct "guess" on how to implement it to avoid TL.

Consider the fact that for any sequence $G$ with the form of fibonacci, that is: $G_{i+1} = G_i + G_{i-1}$, then $G_i = G_1 \cdot F_i + G_0 \cdot F_{i-1]$. So the problem became to solve two linear equations in integers. Prove it with induction or consider the matrix exponentiation for fibonacci.

You should use Python to avoid overflow (long long isn't sufficient, at least for my implementation). Good Luck!

This is painful problem, I spent 3 hours to solve, but very educational actually. If you are struggling, than read this: https://codeforces.com/topic/60789/ru9

"The vertices are listed in the order of traversal" means either in a clockwise or counterclockwise direction.

CODE IS HERE;
#include "stdio.h"
#include "string.h"
long a[401][401];
long n,h,t;
long i,j,m;
int  c[500];
int  p[500];

long count=0;
void bfs(int i)
{
    int k;
    for(k=1;k<=n;k++)
    {
        if(c[k]==0)
        {
            if(a[i][k]==1)
              {
                a[i][k]=0;
                a[k][i]=0;
                c[k]=1;
                p[k]=i;
                bfs(k);
               }
        }
    }

}


void path(int a1,int a2)
{
    int q[500];
    int i=0;
    while(1)
    {
        q[i]=a2;
        i++;
        a2=p[a2];
        if(a2==a1) break;
    }
    printf("%d",i+1);
    printf(" %d",a1);
    while(i>0)
    {
        printf(" %d",q[i-1]);
        i--;
    }
    printf("\n");


}



void main()
{
    for(i=0;i<401;i++)
        for(j=0;j<401;j++)
            a[i][j]=0;
    scanf("%ld %ld",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%ld %ld",&h,&t);
            a[h][t]=1;
            a[t][h]=1;
    }
    for(i=1;i<=n;i++)
        c[i]=0;

    c[1]=1;
    bfs(1);

    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
            if(a[i][j]==1)
            {
                count++;
            }
    }
    printf("%ld\n",count);
    for(i=1;i<n;i++)
    {
        for(j=i+1;j<=n;j++)
            if(a[i][j]==1)
            {
                path(i,j);
            }
    }

}