SỐ LỚN NHẤT

View as PDF

Submit solution

Points: 1600 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Author:
Problem type

Khi được học về LCS Tèo rất hứng thú vì học được phương pháp hay, học được cách vận dụng biến đổi các bài toán liên quan về dạng quen thuộc để ứng dụng được LCS vào để giải. Biết Tèo đang hứng thú, Tí đố Tèo một bài toán như sau:

Cho hai xâu kí tự số XY, tìm một xâu con chung có giá trị lớn nhất của hai xâu đã cho. Ví dụ X = '1003456'Y = '001435': Một số xâu con chung như '00', '0035', '135', '145', \cdots Xâu con chung có giá trị lớn nhất là '145'. Xâu con chung phải lớn nhất phải là một số không chứa số 0 vô nghĩa.

Bạn hãy giúp Tèo viết chương trình tìm xâu con chung có giá trị lớn nhất đó để Tèo có thể kiểm tra đáp án của mình.

Input

  • Dòng 1 là xâu kí tự X
  • Dòng 2 là xâu kí tự Y

Hai xâu chỉ chứa kí tự số. Độ dài mỗi xâu số không quá 1000.

Output

  • in ra dòng 1 là độ dài của xâu con chung lớn nhất cần tìm.
  • Dòng thứ hai in ra xâu con chung lớn nhất theo đúng định dạng đã cho ở ví dụ bên dưới.

Example

Test 1

Input
1003456
001435   
Output
3
LCS MAX NUMBER is 145

Test 2

Input
10103456
0101435 
Output
5
LCS MAX NUMBER is 10145

Test 3

Input
000314
3000410 
Output
2
LCS MAX NUMBER is 34

Test 4

Input
12345
6789 
Output
0
LCS MAX NUMBER is NULL

Test 5

Input
60005
90204    
Output
1
LCS MAX NUMBER is 0

Comments


  • 0
    itachicbh  commented on 9:41 p.m. 7 jan, 2023

    bài này làm lcs đc k ạ ?
    đc thì ntn, tks ạ


  • 1
    vô_nhiễm  commented on 11:18 a.m. 12 mar, 2022

    có thể nào cho bộ nhớ lên xí xí được không ạ :) chứ bộ nhớ vậy thấy hơi căng ạ


  • 1
    NguyenfromVN  commented on 3:47 a.m. 6 sep, 2021

    góp ý thêm bộ test sau: 2 chuỗi, mỗi chuỗi 1000 số 1, code mình sẽ bị MLE nhưng hiện tại thì nó vẫn AC ngon lành .(_).


  • 1
    arena89  commented on 10:55 a.m. 27 jun, 2021

    ai giúp mình không bị TLE test 16 với ạ. Mình cảm ơn ! arena89


  • 1
    A518Backtrack  commented on 11:38 a.m. 4 aug, 2020

    sao contest ni cứ chặt giới hạn bộ nhớ zậy :(((


  • 1
    algorit  commented on 11:21 a.m. 4 aug, 2020

    Test thiếu trường hợp nha :V


  • 2
    Maowonh  commented on 5:01 p.m. 3 aug, 2020

    cuối cùng :(, mãi mới AC


    • 0
      lengocnga  commented on 9:22 a.m. 4 aug, 2020

      ai vậy


      • 0
        Maowonh  commented on 9:36 a.m. 4 aug, 2020

        =)) Manh11IT


        • 0
          lengocnga  commented on 10:06 a.m. 4 aug, 2020

          chẳng quen


          • 0
            Maowonh  commented on 10:10 a.m. 4 aug, 2020

            :D ??? tất nhiên là ko quen rồi, người lạ cả mà


  • 0
    tuanlinh  commented on 3:53 p.m. 3 aug, 2020

    sao mình làm giống TCA_Khoa nhưng dùng c++ thì bị tràn bộ nhớ ?

    (đã đọc code TCA_Khoa :v)


    • 0
      hhoangcpascal  commented on 3:54 p.m. 3 aug, 2020 edited

      Mình giảm memory limit lại đấy không phải Khoa đâu :V Tăng độ khó của game


      • 0
        tuanlinh  commented on 3:56 p.m. 3 aug, 2020

        mình thử nộp lại = code Khoa nhưng vẫn AC :v


        • 0
          hhoangcpascal  commented on 3:57 p.m. 3 aug, 2020

          Giờ nộp lại thử xem


          • 0
            tuanlinh  commented on 3:58 p.m. 3 aug, 2020

            vẫn AC :v


            • 0
              TCA_Khoa  commented on 4:00 p.m. 3 aug, 2020

              nhân phẩm


            • 0
              hhoangcpascal  commented on 4:00 p.m. 3 aug, 2020

              Nộp ở đâu vậy :V


              • 0
                tuanlinh  commented on 4:01 p.m. 3 aug, 2020

                ngoài contest


                • -1
                  hhoangcpascal  commented on 4:02 p.m. 3 aug, 2020 edit 3

                  À há =)) thấy rồi. Tối ưu hoá mảng. Vậy thì... giảm time :3 mà thôi vậy chs khó mọi người quá :V


                  • 0
                    Maowonh  commented on 4:49 p.m. 3 aug, 2020

                    :( làm vậy ai chơi


  • 0
    Maowonh  commented on 12:50 p.m. 3 aug, 2020

    sao limit bộ nhớ lại nhỏ hơn rồi :(


    • 0
      hhoangcpascal  commented on 2:20 p.m. 3 aug, 2020

      tránh việc duyệt trâu full test =))


  • 0
    TCA_Khoa  commented on 10:28 p.m. 2 aug, 2020

    ai có test LCS MAX NUMBER is NULL thì ấn nút báo cáo vấn đề giúp mình nhé :(