Задача на умножение и нахождение корня строки. C++

Question

Пусть задана строка s = s1s2...sn. Назовем ее k-ой (k > 0) степенью sk строку sk = s1s2 . . .sns1s2 . . .sn......s1s2...sn (k раз). Например, третьей степенью строки abc является строка abcabcabc.

Корнем k степени из строки s называется такая строка t (если она существует), что t^k = s.

Ваша задача состоит в том, чтобы написать программу, находящую степень строки или корень из нее.

Входные данные Первая строка входного файла INPUT.TXT содержит строку s, она содержит только маленькие буквы английского алфавита и имеет ненулевую длину, не превосходящую 1000.

Вторая строка входного файла содержит целое число k ≠ 0, |k| < 100001. Если k > 0, то необходимо найти k-ую степень строки s, если k < 0, то необходимо найти корень степени |k| из s.

Выходные данные В выходной файл OUTPUT.TXT выведите строку, являющуюся ответом на задачу. Если длина ответа превосходит 1023 символа, выведите только первые 1023 символа. Если искомой строки не существует — выведите NO SOLUTION.

#include <bits/stdc++.h>
using namespace std; 

int main() 
{ 
    string s;
    cin >> s;
    long long k;
    cin >> k;
    if (k > 0)
    {
        string ans;
        for (size_t i = 0; i < k; i++)
        {
            ans += s;
        }
        cout << ans;
    }
    else 
    {   
        k *= -1;
        if (k > 1000)  //<--- с проверкой этого условия проваливаюсь на втором тесте, без - на 11
        {             // и мне не понятно почему. На входе длина строки <= 1000. (самих тестов я не вижу)
            cout << "NO SOLUTION";
            return 0;
        }
        if(s.size() % k != 0)
        {
            cout << "NO SOLUTION";
            return 0;
        }
        int size = s.size() / k;
        for (size_t i = size; i < s.size(); i += size)
        {
            if (s.substr(0, size) != s.substr(i, size))
            {
                cout << "NO SOLUTION";  
                return 0;
            }
        }
        if (size > 1023) //на входе требуется длина строки < 1024 
            size = 1023;
        cout << s.substr(0, size);
    }
}

На одном из тестов мое решение проваливается. Я подозреваю, что я плохо реализовал корень отрицательной степени. В чем может быть проблема?

Answer 1

Уберите проверку k > 1000 - она ничего не дает, и добавьте проверку длины при возведении в степень - иначе получите превышение доступной памяти.

Вот ваше исправленное решение:

#include <bits/stdc++.h>
using namespace std; 

int main() 
{ 
    string s;
    cin >> s;
    int k;
    cin >> k;
    if (k > 0)
    {
        string ans;
        for (size_t i = 0; i < k; i++)
        {
            ans += s;
            if (ans.size() > 1023) break;
        }
        cout << ans.substr(0,1023);
    }
    else 
    {   
        k *= -1;
        if(s.size() % k != 0)
        {
            cout << "NO SOLUTION";
            return 0;
        }
        int size = s.size() / k;
        for (size_t i = size; i < s.size(); i += size)
        {
            if (s.substr(0, size) != s.substr(i, size))
            {
                cout << "NO SOLUTION";  
                return 0;
            }
        }
        if (size > 1023) //эр тїюфх ЄЁхсєхЄё  фышэр ёЄЁюъш < 1024 
            size = 1023;
        cout << s.substr(0, size);
    }
}

Ну, а если захотите рекорд побить - acmp все-таки :) - то попробуйте сократить это решение:

#include <bits/stdc++.h>
std::string s,r,q = "NO SOLUTION";
int k,i,l,z=1023;
#define x .substr(
main()
{
    std::cin >> s >> k;
    if (k > 0)
        for(;i++ < k && (r+=s).size() < z;);
    else
        if ((l=s.size())%-k) r = q; else
            for(r = s x 0,l/=-k);++i<-k;r!= s x i*l,l)? r=q:r);
    std::cout << r x 0,z);
}

БЛОГ НА HUSL

Задача на умножение и нахождение корня строки. C++

Ответы (1 шт):