Lọc số (TS10LQĐ 2015)

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Small
Dạng bài
Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Cho một xâu \(S\) có độ dài không quá 255 kí tự. Trong xâu \(S\), có chứa các số nguyên mà
mỗi số nguyên đó là một xâu con gồm các kí tự số liên tiếp nhau trong xâu \(S\).

Yêu cầu: Hãy tìm số nguyên lớn nhất có trong xâu \(S\).

Input

  • Có một dòng duy nhất là xâu \(S\) có độ dài không quá 255 kí tự.

Output

  • Ghi ra một số nguyên lớn nhất có trong xâu \(S\)

(Lưu ý: Phải loại bỏ các chữ số 0 vô nghĩa bên trái của kết quả).

Scoring

  • Subtask \(1\) (\(70\%\) số điểm): \(|S|\le 255\) theo đề chuẩn
  • Subtask \(2\) (\(30\%\) số điểm): \(|S|\le 10^{6}\) mở rộng

Example

Test 1

Input 
Abc987hnmh0003456hs006543m
Output 
6543

Bình luận


  • -6
    SBD12_LamLDK    2:04 p.m. 23 Tháng 7, 2024 ← chỉnh sửa 7

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

    1 phản hồi

    • 0
      iq2000laday    4:21 p.m. 11 Tháng 7, 2024

      Python nhanh trí dùng thư viện re :))


      • -3
        thanhlamdnvn    2:51 p.m. 8 Tháng 7, 2024

        ez quá
        code nè


        • 0
          SBD20_Caominhduc    2:44 p.m. 8 Tháng 7, 2024 ← chỉnh sửa 3

          mất 7749 đấm


          • 4
            phuc11731    10:20 p.m. 18 Tháng 2, 2024 
            s=input()
def NMP(s,n):
    global m
    i=0
    while i!=n:
        if s[i] in ex:
            k,i=NMP1(s,n,i)
            t=int(k)
            if t>m:m=t
        i+=1
def NMP1(s,n,i):
    k,j=s[i],0
    for j in range(i+1,n):
        if s[j] in num:k+=s[j]
        else:
            j-=1
            break
    i=j
    return k,i
ex,num,m='-0123456789','0123456789',float('-inf')
NMP(s,len(s))
print(m)

            • 29
              dang7rickroll    7:15 p.m. 2 Tháng 2, 2022 ← đã chỉnh sửa

              Sau 7749 lần submit và debug thì cuối cùng mình cũng đã AC bài này và xin chia sẻ lời giải bài này như sau:

              Mình sẽ chia lời giải này thành 2 phần:

              • Phần 1. Giải subtask 1 (đề chuẩn)
              • Phần 2. Giải subtask 2 (đề mở rộng)

              Phần 1. Giải subtask 1 (đúng 10/13 test)

              • Tư tưởng chính của thuật toán để giải subtask 1 của mình là lọc ra các số nguyên có trong xâu và đưa vào một mảng số nguyên và sử dụng thuật tìm giá trị lớn nhất của mảng và in ra kết quả.
              • Ta sẽ chia ra 3 trường hợp có thể xảy ra đối với subtask 1 và sẽ lần lượt giải từng trường hợp
              • Trường hợp 1. Có các chữ cái trong xâu và chỉ bao gồm số nguyên dương
              • Trường hợp 2. Có các chữ cái trong xâu và có thể bao gồm cả số nguyên âm
              • Trường hợp 3. Không có chữ cái trong xâu.

              Với trường hợp 1, ta sẽ duyệt từ đầu đến cuối xâu, nếu ký tự đang xét là chữ số thì cộng chữ số này vào đáp án theo công thức res = 10*res + (s[i] - '0').

              Ta sẽ lặp lại công thức trên cho đến khi ký tự đang xét không còn là chữ số nữa thì ta sẽ cộng biến res vào mảng số nguyên, khởi tạo lại res = 0.

              Với trường hợp 2, thì ta cần cần xét: nếu ký tự hiện tại đang xét là chữ số và ký tự phía trước là dấu trừ (-) thì vẫn sử dụng công thức ở trên, nhưng thay dấu cộng bằng dấu trừ.

              Rồi làm y hệt như trường hợp 1.

              Với trường hợp 3, ta sử dụng hàm kiểm tra 1 xâu có phải xâu số hay không (tham khảo của mình):

              bool isNumber (string s)
{
    for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]) == false) return false;
    }
    return true;
}

              Nếu nó là xâu số thì không cần phải xét gì nữa, in ra nó luôn (bạn cũng hiểu tại sao mà)

              Phần 2. Giải subtask 2 (Accepted)

              Theo đề mở rộng thì \(|S| \le 10^6\) nên có thể số nguyên lớn nhất có thể vượt quá long long nên dùng string để thao tác.

              Trước hết ta cần viết một hàm so sánh giữa 2 xâu.

              Hàm này của mình đã vẽ ra cho cả 3 trường hợp đã nêu ở phần 1:

              string maximize(string a, string b)
{
    if (a[0] == '-' && b[0] != '-') return b; //1
    if (a[0] != '-' && b[0] == '-') return a; //2
    if (a[0] == '-' && b[0] == '-') return min(a,b); //3
    if (a[0] == '-' && b[0] == '0') return b; //4
    if (a[0] == '0' && b[0] == '-') return a; //5
    if (a.size() < b.size()) return b; //6
    if (a.size() > b.size()) return a; //7
    return max(a,b);//8
}

              Giải thích 1 chút về hàm của mình:

              1. Trường hợp xâu \(a\) là số nguyên âm, xâu \(b\) là số nguyên dương \(\rightarrow\) trả về xâu \(b\).
              2. Trường hợp xâu \(a\) là số nguyên dương, xâu \(b\) là số nguyên âm \(\rightarrow\) trả về xâu \(a\).
              3. Trường hợp cả 2 xâu là số nguyên âm \(\rightarrow\) trả về xâu nhỏ hơn.
              4. Trường hợp xâu \(a\) là số nguyên âm và xâu \(b\) là số \(0\) \(\rightarrow\) trả về xâu \(b\).
              5. Trường hợp xâu \(b\) là số nguyên âm và xâu \(a\) là số \(0\) \(\rightarrow\) trả về xâu \(a\).
              6. Trường hợp xâu \(a\) ngắn hơn xâu \(b\) \(\rightarrow\) trả về xâu \(b\).
              7. Trường hợp xâu \(b\) ngắn hơn xâu \(a\) \(\rightarrow\) trả về xâu \(a\).

              Ta cũng chia subtask 2 này thành 3 trường hợp như subtask 1:

              • Nếu xâu đó là xâu số thì in ra luôn.
              • Trường hợp có cả số nguyên âm và nguyên dương và trường hợp chỉ có số nguyên dương ta gộp thành 1 lần để tiện cài đặt: nếu ký tự đang xét là số hoặc là dấu - thì ta xét tiếp: nếu res rỗng và ký tự đang xét là số 0 thì bỏ qua, ngược lại chèn ký tự đang xét vào phía sau res.
              • Ngược lại thì ta kiểm tra: nếu res khác rỗng thì lấy max của res và ans (ans ở đây là biến lưu kết quả để in ra màn hình), reset lại res.
              • Xuất ra kết quả.

              Code tham khảo cho subtask 1: Đây

              Code tham khảo cho subtask 2: Đây

              P/s: Upvote hoặc tôi sẽ dẫn bạn đến Gulag

              2 phản hồi