Hệ cơ số 3 và 2

[nguyenhieuckt (nguyenhieu)]

Mọi người cho em xin ý tưởng về bài này ạ.

Khánh vừa mới học phương pháp chuyển đổi giữa các hệ cơ số khác nhau. Nhưng cậu ta thường hay sai sót khi ghi lại các dãy số vừa chuyển đổi. Mỗi khi chuyển đổi một số từ hệ cơ số này sang hệ cơ số khác và ghi lại dãy kết quả, cậu ta luôn luôn viết sai một số ở một vị trí nào đó trong dãy kết quả.

Ví dụ, khi chuyển đổi số 14 từ hệ cơ số 10 sang hệ cơ số 2, kết quả đúng phải là “1110”, nhưng Khánh có thể viết thành “0110” hoặc “1111” hoặc “1100” hoặc “1010”. Khánh không bao giờ thêm hoặc bớt bất kỳ số nào trong dãy kết quả, và vì thế nếu có chữ số “0” ở vị trí đầu tiên thì vị trí đó là vị trí mà cậu ta đã viết sai.

Yêu cầu: Cho biết dãy kết quả khi chuyển số N (ở hệ cơ số 10) thành hệ cơ số 2 và 3 (trong đó có đúng 1 vị trí sai). Hãy xác định giá trị chính xác của N, biết rằng số N lớn nhất có thể là 109, và có duy nhất một số N trong một test.

Dữ liệu vào: cho trong file digits.inp gồm:

• Dòng 1: Chứa dãy số ở hệ cơ số 2 của N, với đúng một chữ số được viết không chính xác.
• Dòng 2. Chứa dãy số ở hệ cơ số 3 của N, với đúng một chữ số được viết không chính xác.

Kết quả: ghi vào file digits.out một số nguyên duy nhất là giá trị chính xác của số N.

input :
1010
212
output
14

giải thích: Chỉ có thể là cặp số: “1110” ở hệ 2 và “112” ở hệ 3 là thỏa mãn với N=14

[phamdat2 (Phạm Tiến Đạt)]

Đưa luật trước : https://daynhauhoc.com/faq (II mục 2.1)

Nhờ giải bài tập

• Nên đưa ra giải pháp của mình trước
• Sau đó đưa ra vấn đề mình đang mắc phải và nhờ giải đáp

Đáp sau :

Tóm tắt đề bài :

Mỗi khi chuyển đổi một số từ hệ cơ số này sang hệ cơ số khác và ghi lại
dãy kết quả, cậu ta luôn luôn viết sai một số ở một vị trí nào đó trong dãy kết quả.

Khánh không bao giờ thêm hoặc bớt bất kỳ số nào trong dãy kết quả

Mã giả :
WARNING : 101% naive code

# base 2 gồm các số 0, 1
# base 3 gồm các số 0, 1, 2

in2 = đọc chuỗi base2
in3 = đọc chuỗi base3
n2 = chiều dài chuỗi in2
n3 = chiều dài chuỗi in3
arr2 = [] # lưu trữ các số sau khi thay đổi của base 2
arr3 = [] # lưu trữ các số sau khi thay đổi của base 3

for index = 0 -> n2 - 1; index += 1
  n2_temp = n2[index] # giữ số tại vị trí đang xét 
  if n2[index] = 1 => n2[index] = 0 và ngược lại
  thêm vào arr2 chuỗi n2 
  gán lại n2[index] = n2_temp

for index = 0 -> n3 - 1; index += 1
  n3_temp = n3[index] # giữ số tại vị trí đang xét 

  if n3[index] = 1
    n3[index] = 2 
    thêm vào arr3 chuỗi n3
    n3[index] = n3_temp
    # ------------------------
    n3[index] = 0
    thêm vào arr3 chuỗi n3
    n3[index] = n3_temp
  # làm tương tự cho 2 trường hợp còn lại 

# insert code đổi từ base n qua base 10
# bạn tự làm nhé

Tham khảo : code đổi từ base 2 qua base 10 và làm tương tự với base3

[phamdat2 (Phạm Tiến Đạt)]

nhìn code bác trên mà em thấy kiến thức algorithm của em “lẹt đẹt” quá. Sợ chủ thớt nhìn shock quá thôi
Với lại cho em xin tên ngôn ngữ tìm cái tài liệu để hiểu code của bác đi.

[tntxtnt]

Python 3

p = [(ord(c) - 48, 2**i) for i, c in enumerate(input()[::-1])]
q = [(ord(c) - 48, 3**i) for i, c in enumerate(input()[::-1])]
a = sum(d * w for d, w in p)
b = sum(d * w for d, w in q)
p = {a + (x - d) * w for d, w in p for x in range(2) if x != d}
q = {b + (x - d) * w for d, w in q for x in range(3) if x != d}
print((p & q).pop())

edit: gộp cho khó đọc tí nữa

p = [[(ord(c) - 48, b**i) for i, c in enumerate(input()[::-1])] for b in (2, 3)]
s = [sum(d * w for d, w in t) for t in p]
p = [{s[i] + (x - d) * w for d, w in t for x in range(2 + i) if x != d}
     for i, t in enumerate(p)]
print((p[0] & p[1]).pop())

[rogp10]

Đại loại là để cho bước tính dãy số là O(n) chứ tính như bạn thì nó sẽ ntn.

#pseudo

uInteger find_match(s1, s2)
  # prepping
  first_num = s1[0].to_uInt();
  candidates = <uInteger>[0, 1]; # array literal

  for i=1 to s1.len-1 do
    digit = s1[i].to_uInt();
    candidates.map!(c -> (c << 1 | digit))  # thêm chữ số thứ i từ phải qua
              .append(first_num << 1 | ~digit); # thêm số có khả năng bị sai
    first_num = first_num << 1 | digit;
  end

  first_num = s2[i].to_UInt();
  candidates2 = <uInteger> [0, 1, 2]; # đã có số ban đầu trong này rồi :D
  for i=1 to s1.len-1 do
    digit = s2[i].to_UInt();
    first_num = first_num*3 + digit;
    x = digit==0?1:digit==1?2:0;
    y = digit==1?0:digit==0?2:1;
    candidates2.map!(c -> c*3 + digit)
               .append(first_num*3 + x)
               .append(first_num*3 + y);
    first_num = first_num*3 + digit; # thêm vào nữa là thừa.
  end
  return candidates2.first_duplicate(candidates)
end