Bài toán (Đề thi HSG Tin học 9 tỉnh Nghệ An năm 2022)
Bạn An rất đam mê lập trình. Một hôm, An nhận được thông báo nhận thưởng từ công ty phần mềm mà An thường xuyên sử dụng sản phẩm của công ty đó. Phần thưởng là phiên bản mới của phần mềm trò chơi trí tuệ mà An rất yêu thích. Tuy nhiên, để tải phần mềm này về máy tính thì An cần phải nhập mật khẩu. Mật khẩu là một xâu kí tự nhận được khi An giải xong bài toán mà công ty đã gửi cho An như sau:
Cho n xâu kí tự chỉ chứa các kí tự thuộc tập chữ cái latinh hoa từ đến . Với mỗi xâu kí tự có một kí tự xuất hiện 1 lần, các kí tự còn lại xuất hiện ít nhất 2 lần. Mật khẩu là một xâu gồm kí tự, trong đó kí tự thứ là kí tự xuất hiện 1 lần trong xâu .
Yêu cầu: Hãy đưa ra mật khẩu mà An cần tìm.
Dữ liệu: tệp văn bản MatKhau.Inp gồm:
- Dòng đầu tiên ghi số nguyên dương là số lượng xâu kí tự.
- Dòng thứ trong dòng tiếp theo ghi một xâu kí tự có độ dài không quá 1000.
Kết quả: ghi ra tệp văn bản MatKhau.Out gồm một xâu kí tự là mật khẩu tìm được.
Cài đặt bài toán với Python
# Đọc dữ liệu đầu vào từ tệp MatKhau.Inp
with open('MatKhau.Inp', 'r') as f:
n = int(f.readline().strip()) # Số lượng xâu kí tự
s = f.readline().strip() # Xâu kí tự
# Xử lý dữ liệu để tìm kí tự xuất hiện đúng một lần và đưa ra mật khẩu tương ứng
count = {}
for c in s:
if c not in count:
count[c] = 1
else:
count[c] += 1
password = ''
for c in s:
if count[c] == 1:
password = c
break
# Ghi kết quả ra tệp văn bản MatKhau.Out
with open('MatKhau.Out', 'w') as f:
f.write(password)
Cài đặt bài toán với C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
unordered_map<char, int> count;
for (char c : s) {
count[c]++;
}
char password;
for (char c : s) {
if (count[c] == 1) {
password = c;
break;
}
}
ofstream out("MatKhau.Out");
out << password;
out.close();
return 0;
}
Cài đặt bài toán với Pascal
program MatKhau;
var
n, i: longint;
s: string;
count: array['A'..'Z'] of longint;
password: char;
f: text;
begin
assign(input, 'MatKhau.Inp');
reset(input);
assign(f, 'MatKhau.Out');
rewrite(f);
readln(n);
readln(s);
for i := 1 to length(s) do begin
count[s[i]] := count[s[i]] + 1;
end;
for i := 1 to length(s) do begin
if count[s[i]] = 1 then begin
password := s[i];
break;
end;
end;
write(f, password);
close(input);
close(f);
end.