Link Sub: https://www.spoj.com/PTIT/problems/P176PROA/
Người Gửi: Dương Lee
- Problem:
Cuối tuần vừa rồi, Lều được Chim mời đi giao hữu kèo solo Random. Vốn là người thân thiện, nên sau buổi giao hữu, Chim có ý muốn đổi laptop với Lều thể hiện tinh thần đoàn kết, thân thiện. Về nhà Lều mở máy lên code, thì mới thấy trong máy còn sẵn một danh sách các Custom_map của Chim tạo và sợ mất dữ liệu của Chim nên Lều không xóa.
Bây giờ Lều muốn tạo một Custom_map tuy nhiên không biết đặt tên là gì. Lâu nay Lều luôn đặt tên cho từng Custom_map trong danh sách của mình sao cho 2 tên bất kỳ trong số đó không có quan hệ xâu con. Và Lều chắc chắnsẽ tiếp tục giữ nguyên tắc đó khi thêm một Custom_map vào danh sách mà Chim sẵn có.
Một xâu B được coi là xâu con của xâu A nếu tìm được trong A xâu C mà B = C với : C = {A[i],A[i+1],… ,A[j]} ( C là một đoạn các ký tự liên tiếp trong A). Ví dụ : Xâu “xyz” là xâu con của “axyzb” còn “xyb” thì không.
Hãy giúp Lều đặt tên cho map mới tạo. Đương nhiên sẽ có nhiều cách đặt tên nên hãy đưa ra cách đặt tên càng ngắn càng tốt và nếu có nhiều tên cùng độ dài thì hãy đưa ra tên có thứ tự từ điển bé nhất.
InputBây giờ Lều muốn tạo một Custom_map tuy nhiên không biết đặt tên là gì. Lâu nay Lều luôn đặt tên cho từng Custom_map trong danh sách của mình sao cho 2 tên bất kỳ trong số đó không có quan hệ xâu con. Và Lều chắc chắnsẽ tiếp tục giữ nguyên tắc đó khi thêm một Custom_map vào danh sách mà Chim sẵn có.
Một xâu B được coi là xâu con của xâu A nếu tìm được trong A xâu C mà B = C với : C = {A[i],A[i+1],… ,A[j]} ( C là một đoạn các ký tự liên tiếp trong A). Ví dụ : Xâu “xyz” là xâu con của “axyzb” còn “xyb” thì không.
Hãy giúp Lều đặt tên cho map mới tạo. Đương nhiên sẽ có nhiều cách đặt tên nên hãy đưa ra cách đặt tên càng ngắn càng tốt và nếu có nhiều tên cùng độ dài thì hãy đưa ra tên có thứ tự từ điển bé nhất.
- Dòng đầu tiên là số Custom_map sẵn có : N(1<=N<=30)
- N dòng tiếp theo, mỗi dòng là một chuỗi các ký tự chữ cái in thường liên tiếp là tên của mỗi Custom_map (Độ dài chuỗi không quá 20).
- N dòng tiếp theo, mỗi dòng là một chuỗi các ký tự chữ cái in thường liên tiếp là tên của mỗi Custom_map (Độ dài chuỗi không quá 20).
Output
Example:
- In ra một chuỗi là tên của map mà Lều vừa tạo
Input
5
hocvien
hoanggia
ptit
banana
diamond
Output:
f
Input
6
aa
bcdefg
hijklm
nopqrs
tuvwxy
z
Output:
ab
- Solution:
Input
6
aa
bcdefg
hijklm
nopqrs
tuvwxy
z
Output:
ab
mình dùng thử cách duyệt toàn bộ đầu tiên mà vẫn AC nên không nghĩ cách tối ưu nữa :v
Cách làm: Liệt kê toàn bộ xâu theo thứ tự từ điển: a, b, ..., z, aa, ab, ac,... Sau đó tìm xâu đó có trong chuỗi ký tự không? Nếu không có trong chuỗi thì đó là xâu cần tìm.
cái quan trọng là liệt kê xâu trên như thế nào? Có nhiều cách nhưng code dưới đây sử dụng queue để liệt kê.
Queue:
0: ""
1: a b c d e f ... z
2: b c d e f ... z aa ab ac ad ... az
3: c d e f ... z aa ab ac ad ... az ba bb bc ... bz
...
p/s: Sử dụng tính chất của queue đó là: first in, first out.
Cách làm: Liệt kê toàn bộ xâu theo thứ tự từ điển: a, b, ..., z, aa, ab, ac,... Sau đó tìm xâu đó có trong chuỗi ký tự không? Nếu không có trong chuỗi thì đó là xâu cần tìm.
cái quan trọng là liệt kê xâu trên như thế nào? Có nhiều cách nhưng code dưới đây sử dụng queue để liệt kê.
Queue:
0: ""
1: a b c d e f ... z
2: b c d e f ... z aa ab ac ad ... az
3: c d e f ... z aa ab ac ad ... az ba bb bc ... bz
...
p/s: Sử dụng tính chất của queue đó là: first in, first out.
- Code:
C++:
https://ideone.com/3yw1Bp
#include <iostream>
#include <queue>
using namespace std;
int main ()
{
int n;
string total = "";
cin>>n;
for (int i=1; i<=n; i++)
{
string tmp;
cin>>tmp;
total+=(tmp + " ");
}
/*input:
3
a
bv
gva
-> total = "a bv gva"
*/
string base = "abcdefghijklmnopqrstuvwxyz";
string u = "";
queue <string> q;
q.push(u);
while (!q.empty())
{
string f = q.front();
q.pop();
for (int i=0; i<base.length(); i++)
{
string v = f+base[i]; //each v we have: a, b, c ..., z, aa, ab, ..., zz, ... aaa, ...
q.push(v);
if (total.find(v)==-1)
{
cout<<v;
return 0;
}
}
}
return 0;
}JAVA:
...Python:
...