COCI 2016/2017 - Contest 1 - Cezar

View as PDF

Submit solution

Points: 0.70 (partial)
Time limit: 1.0s
Memory limit: 64M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2016/2017 - Contest 1
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mirko có một mảng chứa ~N~ từ khác nhau, và Mirko muốn mã hoá những từ trong mảng đó sử dụng một phương pháp mã hoá.

Chúng ta mã hoá đoạn văn bản bằng cách chọn một mã khoá - một bảng hoán vị của các chữ cái trong bảng chữ cái tiếng Anh. Chúng ta thay toàn bộ kí tự a trong văn bản bằng chữ cái thứ nhất của mã khoá, thay toàn bộ kí tự b bằng chữ cái thứ hai của mã khoá, và cứ tiếp tục như vậy tới kí tự z.

Ngoài mảng trên ra, Mirko còn có một mảng ~A~ chứa các số nguyên từ ~1~ tới ~N~ theo một thứ tự nhất định nào đó. Mirko muốn chọn một mã khoá sao cho mảng chứa các từ sau khi được mã hoá và sắp xếp theo thứ tự từ điển phải tương ứng với mảng ~A~. Chính xác hơn, Mirko muốn từ có vị trí ban đầu ở ~A_i~ phải có vị trí ~i~ sau khi được mã hoá và sắp xếp.

Thứ tự từ điển là thứ tự mà các từ xuất hiện trong từ điển. Để so sánh thứ tự của hai từ, chúng ta so sánh lần lượt các kí tự từ trái qua phải của hai từ đó để xác định xem từ nào xuất hiện trước. Nếu như từ Y bắt đầu bằng từ X, thì ta nói từ X có thứ tự nhỏ hơn từ Y.

Mirko đang cảm thấy không muốn tự mã hoá mảng văn bản của mình, vậy nên Mirko muốn nhờ bạn làm việc này.

Input

  • Dòng đầu tiên chứa số nguyên ~N~ ~(2 \le N \le 100)~.
  • ~N~ dòng tiếp theo mỗi dòng chứa một từ (dài nhất ~100~ kí tự tiếng Anh viết thường). Các từ không trùng lặp.
  • Dòng cuối chứa ~N~ số nguyên - các thành phần của mảng ~A~.

Output

  • Trong trường hợp không có mã khoá tương thích, in NE.
  • Trong trường hợp có mã khoá tương thích, in DA ở dòng thứ nhất, ở dòng thứ hai in ra đoạn mã khoá được sử dụng (một từ gồm ~26~ kí tự khác nhau trong bảng chữ cái tiếng Anh).
  • Trong trường hợp có nhiều hơn một mã khoá tương thích, in ra một đoạn mã khoá bất kì.

Sample Input 1

2
ab
bc
2 1

Sample Output 1

DA
bacdefghijklmnopqrstuvwxyz

Sample Input 2

3
abc
bcd
add
1 2 3

Sample Output 2

NE

Sample Input 3

3
bbb
ccc
ddd
2 3 1

Sample Output 3

DA
adbcefghijklmnopqrstuvwxyz

Giải thích ví dụ 1

Sau khi mã hoá, các từ trở thành ba,ac, và sau khi sắp xếp thứ tự, mảng trở thành ac, ba, nghĩa là từ thứ nhất sau khi sắp xếp có vị trí thứ hai, và từ thứ hai sau khi sắp xếp có vị trí thứ nhất.

Giải thích ví dụ 3

Sau khi mã hoá, các từ trở thành ddd, bbb, ccc, và sau khi sắp xếp thứ tự, mảng trở thành bbb, ccc, ddd, nghĩa là từ thứ nhất sau khi sắp xếp có vị trí thứ ba, từ thứ ba ở vị trí thứ hai, và từ thứ hai sau khi sắp xếp có vị trí thứ nhất.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.