В чем моя ошибка в задаче?

Question

[Homemade]

Задача

Мое решение

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
 
int main()
{
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        char c;
        string s;
        cin >> n >> c >> s;
        string b = s;
        sort(b.begin(), b.end());
        if (b[0] == b[b.size() - 1]) {
            cout << "0" << '\n';
            continue;
        }
        vector<bool>prime(n + 1, true);
        prime[0] = prime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            if (prime[i]) {
                for (int j = i * i; j <= n; j += i)
                    prime[j] = false;
            }
        }
        int ans = 0;
        for (int i = n; i >= 0; i--) {
            if (prime[i]) {
                ans = i;
                break;
            }
        }
        if (s[ans - 1] == c) {
            cout << "1" << '\n' << ans << '\n';
        }
        else {
            cout << "2" << '\n';
            if (ans < n)
                cout << ans << " " << ans + 1 << '\n';
            else
                cout << ans - 1 << " " << ans << '\n';
        }
        
    }
 
    return 0;
}

Читаемость кода плоха, поэтому напишу свой алгоритм сюда.
Сначала проверяем случай когда все буквы в строке равны символу c. Потом находим с помощью Эратосфена наибольшее простое число ans в отрезке [1,n], так как никакое число из этого диапазона на него не делится кроме него самого. Затем проверяем s[ans-1]==c, если так то ответ только ans, иначе ans, ans+-1.

Где у меня ошибка (в алгоритме, в коде или и там и там) ?

Answer 1

[Wataru]

У вас правильная идея, что двух чисел в ответе всегда достаточно. Всегда можно выдать, например, n, n-1 и эти две операции покроют все позиции с 1 по n.

Но вот случай, когда достаточно одного числа вы неправильно разобрали. Почему вы ищите самое большое простое число? Какой вообще смысл смотреть, что в позиции ans-1 стоит c?

А еще ваш код выводит 0 неверно иногда.

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

Comments

[Homemade]

Спасибо большое. Я условие неправильно понял.

Answer 2

[Alexandroppolus]

тут на самом деле всё просто
1) проверить, что все символы равны с, если да, то 0
2) проверить символы на позициях [n/2 ... n], то есть из второй половины. Если там есть x, символ на котором равен c, то его и берем - не него ничего больше не делится от 1 до n. А если такого символа не нашлось, то остальное смотреть бесполезно - для любого x из первой половины интервала найдется m*x из второй. И в этом случае возвращаемся к вышеупомянутой стратегии: n, n-1

Comments

[Homemade]

Благодарю