Big-O Coding LogoBig-O Coding
Khóa họcLộ trìnhLuyện phỏng vấnThi đấuBài tậpBảng xếp hạngAI Coding LabSắp ra mắtPremium
Quay lại
Đề bài
|
Lời giải
|
Bài nộp
|
Thảo luận (0)

Mô phỏng lịch sử và bộ nhớ đệm trình duyệt

Medium 256MB

Bạn cần thiết kế mô-đun quản lý lịch sử duyệt web và bộ nhớ đệm (cache) cho một trình duyệt web.

Trình duyệt hoạt động theo các quy tắc sau:

  • Ban đầu, người dùng ở trang mặc định home.
  • Lịch sử quay lại (back history) và lịch sử tiến tới (forward history) đều trống.
  • Bộ nhớ đệm chứa tối đa KKK trang web. Ban đầu, bộ nhớ đệm chỉ chứa 1 trang home (kích thước ban đầu là 1).

Hệ thống nhận lần lượt QQQ thao tác thuộc một trong ba loại sau:

  1. VISIT url: Người dùng truy cập trang web url.

    • Lưu trang hiện tại vào lịch sử quay lại.
    • Trang url trở thành trang hiện tại.
    • Toàn bộ lịch sử tiến tới bị xóa sạch.
    • Thêm trang url vào bộ nhớ đệm.
    • Nếu số trang trong bộ nhớ đệm vượt quá KKK, loại bỏ trang cũ nhất trong bộ nhớ đệm.
    • In ra thông báo:
      • Nếu số trang trong bộ nhớ đệm không vượt quá KKK: VISITED url
      • Nếu số trang trong bộ nhớ đệm vượt quá KKK và trang old_url bị loại bỏ: VISITED url (EVICTED old_url)
  2. BACK: Người dùng nhấn nút Back để quay lại trang trước.

    • Nếu lịch sử quay lại trống, không thể thực hiện thao tác. In ra IGNORED và giữ nguyên trang hiện tại.
    • Nếu lịch sử quay lại không trống:
      • Chuyển trang hiện tại sang lịch sử tiến tới.
      • Lấy trang gần nhất ra khỏi lịch sử quay lại làm trang hiện tại.
      • In ra: BACK TO url (với url là trang hiện tại).
  3. FORWARD: Người dùng nhấn nút Forward để đến trang tiếp theo.

    • Nếu lịch sử tiến tới trống, không thể thực hiện thao tác. In ra IGNORED và giữ nguyên trang hiện tại.
    • Nếu lịch sử tiến tới không trống:
      • Chuyển trang hiện tại sang lịch sử quay lại.
      • Lấy trang gần nhất ra khỏi lịch sử tiến tới làm trang hiện tại.
      • In ra: FORWARD TO url (với url là trang hiện tại).

Yêu cầu: Thực hiện lần lượt QQQ thao tác và in ra kết quả của từng thao tác. Sau QQQ thao tác, in ra các trang còn lại trong bộ nhớ đệm theo thứ tự từ cũ nhất đến mới nhất.

Đầu vào

Dòng đầu tiên chứa hai số nguyên QQQ và KKK (1≤Q≤100000,1≤K≤1000001 \le Q \le 100000, 1 \le K \le 1000001≤Q≤100000,1≤K≤100000) — lần lượt là số thao tác và sức chứa tối đa của bộ nhớ đệm. QQQ dòng tiếp theo, mỗi dòng mô tả một thao tác thuộc một trong ba dạng:

  • VISIT url (với url là xâu tên miền / địa chỉ trang web, dài từ 111 đến 505050 ký tự, chỉ gồm chữ cái tiếng Anh, chữ số và các ký tự ., -, _)
  • BACK
  • FORWARD

Đầu ra

In ra Q+1Q + 1Q+1 dòng:

  • QQQ dòng đầu tiên: Kết quả của từng thao tác theo đúng thứ tự (VISITED ..., BACK TO ..., FORWARD TO ... hoặc IGNORED).
  • Dòng thứ Q+1Q + 1Q+1: Xâu CACHE: theo sau là các trang hiện có trong bộ nhớ đệm theo thứ tự từ cũ nhất đến mới nhất, cách nhau bởi đúng một khoảng trắng. Nếu bộ nhớ đệm rỗng, in CACHE: EMPTY.

Ví dụ 1

Đầu vào

7 2
VISIT google.com
VISIT youtube.com
BACK
BACK
BACK
FORWARD
VISIT github.com

Đầu ra

VISITED google.com
VISITED youtube.com (EVICTED home)
BACK TO google.com
BACK TO home
IGNORED
FORWARD TO google.com
VISITED github.com (EVICTED google.com)
CACHE: youtube.com github.com

Ví dụ 2

Đầu vào

5 3
VISIT codeforces.com
VISIT atcoder.jp
VISIT leetcode.com
FORWARD
BACK

Đầu ra

VISITED codeforces.com
VISITED atcoder.jp
VISITED leetcode.com (EVICTED home)
IGNORED
BACK TO atcoder.jp
CACHE: codeforces.com atcoder.jp leetcode.com

Ví dụ 3

Đầu vào

4 1
BACK
FORWARD
VISIT wikipedia.org
VISIT stackoverflow.com

Đầu ra

IGNORED
IGNORED
VISITED wikipedia.org (EVICTED home)
VISITED stackoverflow.com (EVICTED wikipedia.org)
CACHE: stackoverflow.com
Chỉ viết thân hàm, hệ thống tự lo Input/Output
Bài này không hỗ trợ chế độ Viết chương trình
Bật gợi ý code
|
Loading...
Test Case
|
Output
Ln 1, Col 1
Đang tải test ví dụ...