Bài 2. Mã số nhân viên
Tổng Giám đốc công ty Hoa Hồng nổi tiếng là người rất cẩn trọng. Ông ta thực hiện
việc quản lí nhân viên bằng cách gán cho mỗi nhân viên một mã số. Công ty có N nhân
viên thì mỗi nhân viên i (i = 1, 2, …, N) đều có một mã số hoàn toàn khác nhau. Do bận đi
công tác một thời gian dài nên ông ta giao lại quyền quản lí cho trợ lý của ông. Khi ông trở
về, công ty đã có sự thay đổi số lượng nhân viên. Vì vậy, khi tiếp nhận thêm nhân viên
mới, ông ta muốn biết mã số lớn nhất để gán cho nhân viên mới.
Yêu cầu: Hãy tìm mã số lớn nhất chưa xuất hiện trong N mã số đã cho.
Dữ liệu vào: Từ tệp văn bản CODE.INP gồm:
- Dòng thứ nhất ghi số nguyên dương N là số lượng nhân viên (1 < N ≤ 106);
- N dòng tiếp theo, dòng thứ i ghi số ai (i = 1, 2, …, N; |ai| ≤ 109).
Kết quả: Ghi ra tệp văn bản CODE.OUT gồm một số duy nhất là mã số tìm được.
Ví dụ:
CODE.INP CODE.OUT
6
7
4
2
6
1
3
5
Ràng buộc: - Sub1: Có 50% test tương ứng 50% số điểm của bài với N ≤ 100 và |ai| ≤ 103;
- Sub2: Có 30% test tương ứng 30% số điểm của bài với N ≤ 1000 và |ai| ≤ 106;
- Sub3: Có 20% test tương ứng 20% số điểm còn lại của bài với N ≤ 106 và |ai| ≤ 109.
Code mẫu:
with open(‘CODE.INP’) as f,open(‘CODE.OUT’,’w’) as fo:
n=int(f.readline())
ap=[False]*(n+2)
for _ in range(n):
x=int(f.readline())
if 1<=x<=n+1:
ap[x]=True
for i in range(1,n+2):
if not ap[i]:
fo.write(str(i))
break