THTB Sơn Trà, Đà Nẵng 2023

Bài 1: Xếp lều trại

Test đặc biệt

121 120000 12

121 12 120

Cách 1 - 6 string - liệt kê 6 trường hợp và so sánh

• a + b + c
• a + c + b
• b + a + c
• b + c + a
• c + a + b
• c + b + a

Chuyển thành long long hết? Số

${10}^6$ có 7 chữ số. 1000000

So sánh theo string vẫn đúng vì các cách ghép có cùng độ dài

Làm tổng quát cho

$n$ xâu ghép lại

• Sắp xếp giảm dần theo phép so sánh sau

• "

  $a$ đứng trước
  $b$" nếu như str(a) + str(b) > str(b) + str(a)
  • Dùng hàm sort của thư viện –> Độ phức tạp
    $O(n\log )$

• Selection Sort (Đức Bảo) = số lượng phép so sánh * ĐPT / 1 phép so sánh =

  $O(n^2)\times O(L)$
  • 7 6 9
  • 7 9 6
  • 9 7 6

Bài 2

Bài yêu cầu đếm số ước?

Đếm số bộ

$a,b$ mà

$a\times b=n$. Đây là mô tả của thuật toán tìm ước bằng cách chạy for tới căn !!!

Bài 3

• Mật mã Caesar
• Mật mã Vigenere

https://www.khanacademy.org/computing/computer-science/cryptography

Bài 4

Xâu nhị phân: 0 là không chọn, 1 là có chọn

Subtask 1:

$n\le 20$

Xâu nhị phân độ dài

$n$.

• Bit thứ i =
  $1$ nghĩa là ta đã đặt một viên gạch tại ô thứ
  $i$.

Sau khi gen ra mỗi một xâu nhị phân bất kỳ:

• Thống kê số bước độ dài
  $x,y$, số bước độ dài không phải
  $x,y$

Subtask 1.5:

(credit: 3H)

$a,b$ tương đối nhỏ

Xét hoán vị các số

$0,1$. Trong đó

$0$ là bước đi

$x$ đơn vị và

$1$ là bước đi

$y$ đơn vị

Thêm kỹ thuật nhánh cận (dùng Prefix sum) để ngắt sớm những trường hợp chắc chắn sẽ cho ra kết quả tệ hơn kết quả tốt nhất hiện có.

Subtask 2:

$n\le 100$

Đặt

$f(i)$ là tổng mảng

$A[.]$ lớn nhất trong tất cả cách di chuyển đến

$i$.

Đặt

$dp(i,c)$ (ý nghĩa như trên …) nhưng

$c$ là số lượng skill loại 1 (bước nhảy độ dài

$x$) đã dùng.

Giả sử có

$d$ bước độ dài

$y$ đã dùng để đi tới

$i$

Vì đã biết

$x,y,c$ nên

$cx+dy=i\Rightarrow d=\frac{i-cx}{y}$

Khi đi tới bước tiếp theo:

• Dùng bước nhảy độ dài
  $x$ –
  $dp(i+x,c+1)$
• Dùng bước nhảy độ dài
  $y$ –
  $dp(i+y,c)$

Đáp án:

$dp(n,a)$

$b=\frac{n-ax}{y}$

$O(n^2)$