thảo luận [Học Tập] Topic thuật toán

Mới xong, test của PropertyGuru Singapore.
Thời gian 20 phút.


View attachment 568957
@Lập Trình Viên Số Khổ Ok, đã sửa code, giờ thì work với hầu hết test case

Python:
def semialtstring(s):
    str_len = len(s)
  
    # Check if string length < 3
    if str_len < 3:
        return str_len
      
    # Check if all characters are the same
    if s == str_len*s[0]:
        return 2
      
    tmp_list = []
    repeat_count = 0
    character_count = 1
    n = 1
    # print("Start at {}\n\ncharacter count is 1\n".format(s[0]))
    while n < str_len:
        # print("char {}\n".format(s[n]))
        character_count += 1
        if s[n] == s[n-1]:
            repeat_count += 1
        else:
            repeat_count = 0
          
        if repeat_count >= 2:
            # print("current repeat count is {}. Save current char_count to list. Reseting...\n".format(repeat_count))
            tmp_list.append(character_count-1) # Doesn't take the current character
            repeat_count = 1
            character_count = 2
        # print("repeat count: {}\n".format(repeat_count))
        # print("character count: {}\n".format(character_count))
        n += 1
        if n == str_len:
            tmp_list.append(character_count)
    return max(tmp_list)
  
if __name__ == "__main__":
    print("Semialtstring Solution\n")
    test_string = "aaaaaa"
    print(semialtstring(test_string))
 
Last edited:
Ủa sao cái testcase đầu lại ko có ký tự b ở đầu nhỉ!?
Nó phải là baabbabb -> 8 chứ ta.
Ko biết mình đang hiểu sai chỗ nào
 
Ủa sao cái testcase đầu lại ko có ký tự b ở đầu nhỉ!?
Nó phải là baabbabb -> 8 chứ ta.
Ko biết mình đang hiểu sai chỗ nào

A substring (contiguous fragment) of S is [...]

già rồi mắt mờ hả anh
BlYu2Cr.png
 
test case 'bbbba' cho kết quả = 4?
Cảm ơn bạn đã test giúp :love: .Đoạn sai ở đây:

Python:
if repeat_count >= 2:

            # print("current repeat count is {}. Save current char_count to list. Reseting...\n".format(repeat_count))

            tmp_list.append(character_count-1) # Doesn't take the current character

            repeat_count = 0 <- Chỗ này phải là 1

            character_count = 2

Đã sửa code
 
Mình năm 2 bị mất gốc CSDL, thuật toán nặng. Chỉ nắm được C++ cơ bản thôi :( . Theo mọi người mình nên tự học từ đâu để lấy lại căn bản. Thuật toán nào trước ?
 
Mình năm 2 bị mất gốc CSDL, thuật toán nặng. Chỉ nắm được C++ cơ bản thôi :( . Theo mọi người mình nên tự học từ đâu để lấy lại căn bản. Thuật toán nào trước ?
Cắm mặt cày game tiếp đi anh sinh viên, đời là mấy tí :sexy_girl:
 
Để đi làm cần biết sử dụng sử dụng biểu thức bool 1 cách hiệu quả, thêm biết dùng LinkedList, Hashmap, Đệ Quy, Quy Hoạch Động là đủ rồi :embarrassed:
Dạ vâng để em học tập thêm. Em đang làm bt cuối kì môn phân tích tk & gt. Thầy kêu là phải thêm 1 thuật toán như quy hoạch động ... vào để được qua môn. Em làm đề tài quản lí sinh viên.
 
Chắc các thím trong đây cũng có một số thím chơi bộ môn này nhỉ.
Các thím cứu em ca này với. Em tạch một testcase mà số nó lớn quá thành ra em không biết nó sai đâu.
Bài thứ 301 trong 300 bài code thiếu nhi nên em chịu :too_sad::too_sad:
1622521963629.png
 
Last edited:
Nếu a mod b = c thì (a*a) mod b = (a*c) mod b
Sau đó dùng 1 vòng lặp for 1-> n là ra được (a^n) mod b rồi nhỉ?
Nếu thích chia để trị kiểu a^n = (a^ n/2) ^2 rồi chia tiếp (a^ n/2) = (a^ n/4) ^2 có thể nhanh hơn.
 
Vấn đề là a vs b rất lớn, 10^(100000) thì quá cả long rồi, nên phải xử lý. A cho link đề gốc trên Codeforces đi để tối tôi về thử. Nếu n là prime thì có thể dùng little fermat theorem. Trong th này thì hình như là ko nên khó hơn nhiều.
 
Chắc các thím trong đây cũng có một số thím chơi bộ môn này nhỉ.
Các thím cứu em ca này với. Em tạch một testcase mà số nó lớn quá thành ra em không biết nó sai đâu.
Bài thứ 301 trong 300 bài code thiếu nhi nên em chịu :too_sad::too_sad:
View attachment 576336
tính a <- a % n.

rồi tính a^b % n bằng cách:

a^b = (a^(b / 10))^10 * (a^(b % 10))

vậy từ công thức có thể thấy chỉ cần duyệt qua và tính (a^(b đến chữ số thứ i-1))^10 * (a^(chữ số thứ i của b)).

C++:
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ll expt(ll a, ll b, ll m) {
    ll ans = 1;
    for (; b; b >>= 1) {
        if (b & 1)
            ans = ans * a % m;
        a = a * a % m;
    }
    return ans;
}

int main() {
    string a, b; int n;
    cin >> a >> b >> n;
    ll as = 0;
    for (char c : a) {
        as = (as * 10 + (c - '0')) % n;
    }
    ll ans = expt(as, b[0] - '0', n);
    for (int i = 1; i < b.size(); ++i) {
        ans = expt(ans, 10, n) * expt(as, b[i] - '0', n) % n;
    }
    cout << ans;
    return 0;
}
 
Last edited:
Back
Top