TRAINING
Điểm: 2
Số siêu nguyên tố là số nguyên tố mà khi bỏ một số tùy ý các chữ số bên phải cùa nó thì phần còn lại vẫn là số nguyên tố. Ví dụ số ~2333~ là số siêu nguyên tố có ~4~ chữ số vì các số ~233, 23, 2~ đều là số nguyên tố. Cho số ~n~ ~(1 < n < 10)~, hãy đưa ra các số nguyên tố có ~n~ chữ số.
Dữ liệu vào:
- Số nguyên dương ~n~.
Kết quả:
- Các số siêu nguyên tố có ~n~ chữ số, mỗi số trên một dòng và theo thứ tự từ nhỏ đến lớn. Nếu không có số nào thoả mản thì in ~-1~.
Input
4
Output
2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
Điểm: 2
Cho n phần tử và dãy n các số nguyên, tìm độ dài chu kỳ lặp lại dài nhất (tức là một dãy phần tử lặp lại).
VD: ~n=7~
- Input:
7
1 2 3 4 2 3 4
Output: 3
(2 3 4)
Điểm: 2
Cho một danh sách gồm ~n~ phần tử số nguyên ~a_1, a_2, ..., a_n~. Nhiệm vụ của bạn là xóa các phần tử trùng lặp sao cho mỗi phần tử chỉ xuất hiện một lần và giữ nguyên thứ tự xuất hiện ban đầu.
Input:
- Dòng đầu tiên chứa số nguyên ~n~ ~(1 ≤ n ≤ 10^5)~: Số phần tử trong danh sách.
- Dòng thứ hai chứa n số nguyên ~a_1, a_2, ..., a_n~ ~(1 ≤ a_i ≤ 10^9)~: Các phần tử của danh sách.
Output:
In ra danh sách sau khi đã loại bỏ các phần tử trùng nhau, mỗi số cách nhau một khoảng trắng.
Ví dụ:
Input:
10
5 3 2 3 7 8 5 2 4 6
Output:
5 3 2 7 8 4 6
Điểm: 2
Người khổng lồ muốn leo lên một ngọn núi có ~N~ bậc thang. Mỗi lần, người khổng lồ có thể bước lên một số bậc thuộc tập hợp các bước chân ~{a_1, a_2, ..., a_M}~ (gồm ~M~ loại bước khác nhau).
Hãy tính số cách người khổng lồ có thể leo từ bậc ~0~ đến bậc ~N~.
Dữ liệu vào:
- Dòng đầu tiên chứa hai số nguyên ~N, M (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 100)~.
- Dòng thứ hai chứa M số nguyên khác nhau ~a_1, a_2, ..., a_M~ ~(1 ≤ a_i ≤ N)~.
Dữ liệu ra:
- In ra một số nguyên duy nhất là số cách người khổng lồ có thể leo lên bậc thang thứ ~N~.
Ví dụ 1:
Input:
5 2
1 2
Output:
8
Ví dụ 2:
Input:
7 3
1 3 5
Output:
12
Đề bài: Tìm đường đi nhanh nhất trong thành phố
Một thành phố có ~n~ giao lộ được đánh số từ ~1~ đến ~n~ và ~m~ con đường hai chiều kết nối các giao lộ. Mỗi con đường có một độ dài tương ứng.
Bạn là tài xế xe công nghệ, nhận được yêu cầu đón khách từ giao lộ ~s~ và đưa họ đến giao lộ ~t~. Hãy tìm quãng đường ngắn nhất để di chuyển từ ~s~ đến ~t~. Nếu không thể đến nơi, in ra NO.
Dữ liệu vào (input)
- Dòng đầu tiên chứa 4 số nguyên:
- ~n~ ~(1 \leq n \leq 1000)~ - số giao lộ
- ~m~ ~(1 \leq m \leq 10^5)~ - số con đường
- ~s~ ~(1 \leq s \leq n)~ - giao lộ xuất phát
- ~t~ ~(1 \leq t \leq n)~ - giao lộ cần đến
- ~m~ dòng tiếp theo, mỗi dòng chứa 3 số nguyên:
- ~u~ ~v~ ~w~ ~(1 \leq u, v \leq n, 1 \leq w \leq 10^6)~ - có con đường giữa giao lộ ~u~ và ~v~ có độ dài ~w~.
Dữ liệu ra (output)
- Nếu có đường đi từ ~s~ đến ~t~, in ra độ dài ngắn nhất.
- Nếu không thể đi đến ~t~, in
NO.
Ví dụ 1
Input
5 6 1 5
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
Output
6
Giải thích
- Lộ trình ngắn nhất từ ~1 → 5: 1 → 2 → 3 → 5~, tổng quãng đường = ~2 + 1 + 3 = 6~.
Ví dụ 2
Input
4 2 1 4
1 2 5
2 3 10
Output
NO
Giải thích
- Không có cách nào đi từ 1 đến 4, nên in "NO".
Gợi ý cách giải (thuật toán Dijkstra)
- Dùng danh sách kề (~adj[u]~ chứa cặp ~(v, w)~) để lưu thông tin đường đi.
- Khởi tạo khoảng cách ~dist[]~ với tất cả các giao lộ là ~∞~, riêng giao lộ xuất phát ~s~ có ~dist[s] = 0~.
- Dùng hàng đợi ưu tiên (priority queue) để lấy đỉnh có khoảng cách ngắn nhất trước.
- Cập nhật khoảng cách nếu tìm được đường đi tốt hơn.
- Trả về ~dist[t]~ nếu có đường đi, ngược lại in
NO.
🚀 Bài toán này giúp mô phỏng hệ thống chỉ đường GPS hoặc tìm đường đi tối ưu trong giao thông đô thị.