P179PROB - ROUND 9B - GIẢI MẬT THƯ

Link Sub: http://www.spoj.com/PTIT/problems/P179PROB/

Người Gửi: Dương Lee

• Problem:

Tí đố Tèo giải một đoạn mật thư. Đầu vào là một chuỗi kí tự có độ dài bằng N và có M kí tự ‘#’. Với mỗi kí tự ‘#’, có K kí tự sẵn có để thay thế cho nó. Như vậy, nếu thử chọn sẽ có tất cả K^M trường hợp. Đáp án của mật thư là xâu có thứ tự bằng X theo thứ tự từ điển trong tập hợp tất cả các khả năng trên.  

Việc thay thế lần lượt từng kí tự vào kí tự ‘#’ của mật thư sẽ sinh ra rất nhiều các trường hợp. Tèo nghĩ một lúc lâu mà vẫn chưa ra. Các bạn hãy giúp Tèo nhé.

Input

Dòng đầu tiên gồm 4 số nguyên N, M, K và X (1 <= N <= 500, 1 <= M <= N, 1 <= K <= 26, 1 <= X <= 10^9).

Dòng tiếp theo chứa xâu S có độ dài bằng N, là đoạn mật thư mà Tí gửi cho Tèo, chỉ bao gồm các chữ cái thường và kí tự ‘#’.

M dòng tiếp theo, dòng thứ i gồm K kí tự, là các khả năng có thể thay thế cho kí tự ‘#’ thứ i trong xâu S.

Output

n ra xâu có số thứ tự bằng X theo thứ tự từ điển.

Example:

Input

9 2 3 7
bi#omke#i
abc
efd

Output:

bicomkedi

Input

4 1 2 2
#iek
ab

Output:

biek

• Solution:

Giải thích test 2: Có tất cả 2 xâu là aiek và biek, trong đó biek là xâu có STT bằng 2.

- Đầu tiên cần phải sắp xếp cho các string cần chọn tăng dần (theo thứ tự từ điển). 

- Với mỗi một số x cho trước, kí tự # tìm được (từ cuối lên) và dãy kí tự điền vào tương ứng. Để xác định xem nó là kí tự nào chỉ cần lấy (X%M) thì sẽ xác định được vị trí kí tự cần điền vào. 

(Nói tóm lại sử dụng phép chia ma trận để xác định vị trí hàng, cột).

• Code:

C++:

JAVA:

P143SUMA - ROUND 3A - Bí kíp luyện rồng

Link Sub: http://www.spoj.com/PTIT/problems/P143SUMA/
Người Gửi: Dienmayxanh

• Problem:

Hiccup đang luyện thêm khả năng chiến đấu cùng với những con rồng của mình, vượt qua tất cả cậu sẽ nhận được chứng chỉ dũng sĩ dragon. Hiccup chỉ có thể vượt qua 1 con rồng nếu như chỉ số chiến đấu của cậu lớn hơn chỉ số chiến đấu của con rồng đó, và sau khi giành chiến thắng chỉ số chiến đấu của cậu sẽ tăng thêm một mức nhất định tùy vào con rồng mà cậu đánh bại.  
Các bạn thử đoán xem, liệu Hiccup có thể nhận được chứng chỉ không nhé.

Input

Dòng đầu tiên gồm 2 số nguyên s và n.

n là số con rồng Hiccup cần phải vượt qua (1 <=n <= 10^3).

s là chỉ số chiến đấu ban đầu của Hiccup (1 <=s <= 10^4).

n dòng tiếp theo, dòng thứ i chứa cặp số (x[i], y[i]). Trong đó x[i] là chỉ số chiến đấu của con rồng thứ i (1 <= x[i] <= 10^4), y[i] là mức tăng chỉ số cho Hiccup nếu cậu đánh bại nó (0 <= y[i] <= 10^4).

Output
In ra “YES” nếu Hiccup nhận được chứng chỉ dũng sĩ dragon, ”NO” nếu Hiccup thất bại.

Example:

Input

2 2
1 99
100 0

Output:

YES

Input

10 1
100 100

Output:

NO

• Solution:

Các con rồng này sẽ được sắp xếp tăng dần và sẽ diệt từng con sau khi đã sắp xếp.

• Code:

C++:

JAVA:

BCSAPXEP - Sắp xếp (Cơ bản)

Link Sub: http://www.spoj.com/PTIT/problems/BCSAPXEP/
Người Gửi: Dương Lee

• Problem:

Sắp xếp dãy tăng dần.

Input
- Dòng đầu chứa số n ( số phần tử của dãy 1<=n<=1000)  
- n dòng sau, mỗi dòng là 1 phần tử của dãy (giá trị tuyệt đối không quá 1000)

Output
Mỗi phần tử của dãy in trên 1 dòng, theo thứ tự tăng dần.

Example:

Input

3
3
2
1

Output:

1
2
3

• Solution:

Code C:
Sắp xếp nổi bọt. Với mỗi phần tử [i] chọn được (i: 0 -> n-1) thì sẽ đẩy nó lên trên cao nhất có thể (SX: tăng dần hoặc giảm dần).

• Code:

C:

C++:

JAVA: