Hoàn chỉnh số N để N là số đối xứng

#1

Đề bài:

Một số được gọi là số đối xứng nếu đem đảo ngược số đó ta lại nhận được số ban đầu.
Cho số nguyên N, hãy tìm số chữ số ít nhất cần thêm vào N để N trở thành số đối xứng(N <= 10^1000).

Chú ý: Input đảm bảo không có số 0 vô nghĩa ở đầu

Mình đang bế tắc và chưa biết làm thế nào, mọi người giúp đỡ mình với ạ.

Input:
Nhập vào số N(N <= 10^1000).

Output:
Số chữ số ít nhất cần thêm vào N để N là số đối xứng

Ví dụ:
Số 1231 -> 12321 -> Đáp án là 1

#2

Theo em cứ thêm đúng số chữ số của n :upside_down_face::upside_down_face::upside_down_face:

1 Like
#3

Thêm như thế nào nhỉ?

Ví dụ với số có n chữ số là an-1an-2…a1a0.

  • Chỉ được thêm trước an-1 (1)
  • Chỉ được thêm sau a0 (2)
  • Chỉ thêm đầu và cuối số, (1) + (2)
  • Thêm đầu và cuối, thêm giữa ai và ai+1, với 0 <= i < n-1.

Mình thấy đề chưa rõ ràng thôi. :grin:
Còn cách giải thì đang như thế này => :thinking:

1 Like
#5

bài này thấy quen quen, hình như là đảo xâu N thành xâu N’ rồi tìm dãy con chung dài nhất của N và N’ rồi lấy độ dài N trừ độ dài dãy con chung là ra :V

3 Likes
#6

Có thể thêm bất kỳ vị trí nào của số N bạn nhé.

2 Likes
#7

Ví dụ 1 bộ input để dễ hình dung hơn cách của bạn được không? Mình chưa hiểu lắm.

#8

ví dụ là 59474815 thì đảo của nó là 51847495, dãy con chung dài nhất là 54745 vậy cần thêm 8 - 5 = 3 số là ra

ví dụ ẹ quá :joy:

chuỗi bình thường với chuỗi đảo của nó có cái gì chung thì dãy đối xứng tạo thành cũng có cái chung đó, nên tìm cái chung này rồi lấy độ dài ban đầu trừ nó ra là ra những ký tự chưa nằm trong chuỗi đối xứng, cần thêm mấy số đó vào là đc

4 Likes
#9

code thế này ko biết đúng chưa :kissing_closed_eyes:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    string s; cin >> s;
    vector<int> p(s.size() + 1), q = p;
    for (size_t j = s.size(); j--; p.swap(q))
        for (size_t i = 0; i < s.size(); i++)
             q[i+1] = s[i] == s[j] ? 1 + p[i] : max(p[i+1], q[i]);
    cout << s.size() - p.back() << "\n";
}
2 Likes
#10

Có vẻ chuẩn rồi bạn ạ.
Code đẹp quá :kissing_heart:
Mình đánh dấu solution phát

#11

Bài này hồi đó đọc còn tới O(n) nữa mà h tìm ko ra (không biết có nhầm không :sweat_smile: ) à thuật toán Manacher.

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?