The problem of multiplying and finding the root of a string. C++

Question

The problem of multiplying and finding the root of a string. C++

Task condition :

Let the string s = be given s1s2...sn. Let's call it the kth (k > 0) power of sk , sk = s1s2... sns1s2 . . .sn......s1s2...sn (k times). For example, the third power of the string abc is the string abcabcabc.

The root k of the power of a string s is a string t (if it exists) such that t^k = s.

Your task is to write a program that finds the degree of a string or the root of it.

Input data data The first line of the input file INPUT.TXT contains the string s, it contains only small letters of the English alphabet and has a non-zero length not exceeding 1000.

The second line of the input file contains an integer k ≠ 0, |k| 0, then it is necessary to find the k-th degree of the string s, if k

Output data To the output file OUTPUT.TXT output a string that is the answer to the problem. If the response length is exceeds 1023 characters, output only the first 1023 characters. If the search string does not exist - output 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);
    }
}

On one of the tests, my solution fails. I suspect that I have implemented the negative degree root poorly. What could be the problem?

1

c++строки олимпиада

Author: Grundy, 2020-06-29

Source

1 answers

score 3 · Accepted Answer

Remove the k > 1000 check - it does not give anything, and add a length check when raising to a power - otherwise you will get an excess of available memory.

Here is your corrected solution:

#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);
    }
}

Well, if you want to break the record-acmp still :) - then try to shorten this solution:

#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);
}