시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 1053 | 284 | 215 | 28.628% |
우리는 웹 페이지에 접속할 때 '웹 브라우저'를 사용한다. 웹 브라우저에는 크게 뒤로 가기(Backward), 앞으로 가기(Frontward), 웹페이지 접속(Access) 기능이 있다.
사용자가 웹 사이트에 접속하면 컴퓨터의 캐시(cache)공간에 웹페이지 정보가 저장된다. 그리고 뒤로 가기 또는 앞으로 가기 기능을 사용하면 캐시 공간에 저장되어 있던 페이지의 정보를 불러오게 된다. 하지만 캐시 공간은 한정적이기 때문에 무한정 정보를 저장할 수 없다. 그래서 일정 캐시 용량을 초과하게 되면 방문한지 오래된 페이지가 삭제되도록 설계되어 있다. 사용 중인 캐시 용량은 뒤로 가기 공간,앞으로 가기 공간 그리고 현재 접속 중인 페이지가 사용하고 있는 용량의 총합으로 계산된다. 여기에 주헌이가 개발한 웹 브라우저에는 신기한 기능이 있는데, 바로 압축(Compress)이라는 기능이다. 압축 기능은 뒤로 가기 공간에 같은 번호의 페이지가 연속해서 들어있을 때, 이를 하나로 줄일 수 있는 기능이다.
각 기능의 작동방식은 각각 다음과 같다.
Q개의 작업을 모두 마친 뒤에 현재 접속 중인 페이지와 뒤로 가기 공간, 앞으로 가기 공간에 저장되어 있는 페이지의 번호를 구하여라.
초기 상태에는 뒤로 가기 공간, 앞으로 가기 공간이 모두 비어있으며 어떤 페이지에도 접속해있지 않는 상태이다. 또한 같은 번호의 페이지에 여러번 접속할 수 있으며, 그럴 경우 같은 번호의 페이지이라도 방문 순서는 각기 다르게 취급된다.
첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 와 최대 캐시 용량 C 이 순서대로 주어진다.(1 ≤ N, Q ≤ 2,000, 1 ≤ C ≤ 200,000)
둘째 줄에는 N개의 정수 CAPi 가 주어진다. i 는 웹페이지의 번호이며, i 번째 숫자는 i 번째 웹페이지를 방문할 때 사용하는 캐시 공간의 크기를 의미한다. 각 캐시 공간의 크기는 1 ≤ CAPi ≤ C 를 만족한다.
셋째 줄부터는 Q개의 작업이 주어지며, 각 작업이 의미하는 바는 다음과 같다.
A(접속)작업이 적어도 한 번은 등장한다.
3줄에 걸쳐서 출력한다.
첫째 줄에는 현재 접속 중인 페이지의 번호를 출력한다.
둘째 줄에는 뒤로 가기 공간에서 가장 최근에 방문한 순서대로 페이지의 번호를 출력한다. 저장된 페이지가 없다면 -1
을 출력한다.
셋째 줄에는 앞으로 가기 공간에서 가장 최근에 방문한 순서대로 페이지의 번호를 출력한다. 저장된 페이지가 없다면 -1
을 출력한다.
3 11 20 4 5 6 B F A 1 A 1 A 2 A 3 B A 1 A 1 A 2 C
2 1 2 -1
2 8 10 1 1 A 1 A 1 A 2 A 2 A 2 B B C
2 1 2 2
3 8 18 4 5 6 A 1 A 2 A 1 A 2 C B A 3 A 1
1 3 1 -1
아래 그림은 에제 입력 1을 나타내고 있다.
파란색 도형 안에 괄호 밖 숫자는 페이지의 번호를, 괄호 안 숫자는 해당 페이지가 사용하는 캐시 공간의 크기이다.
University > 아주대학교 > 2021 아주대학교 프로그래밍 경시대회 APC > Div.1 C번