COCI 2014/2015 contest7 2- 열쇠 수리공(KRIZA) > 문제은행 : 정보올림피아드&알고리즘




2597 : 열쇠 수리공(KRIZA)

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
36 회   
시도횟수
167 회   

문제

경제 상황이 좋지 않아 많은 사람들이 일자리를 잃었다. 이러한 위기 상황에도 우리가 읽고 있는 이 문제의 주인공 준혁이는 일자리를 구했다. 한 대형 호텔의 보조 열쇠수리공으로 다음 주 월요일부터 출근할 예정이다. 이에 앞서 오늘 준혁이는 실기 테스트를 받는다.

 

아래 그림과 같이 여러 개의 열쇠가 달려있는 고리를 받아서 객실을 차례로 돌며 객실의 문을 열고 내부를 본 후에 다시 잠그는 일을 K번 해야 하는데 아래 제약 사항을 지켜야 한다.


<제약사항>
- 객실을 방문할때는 방향을 바꾸거나 건너뛸 수 없다. 진행방향은 항상 오른쪽 이다.
- 열쇠고리를 뒤집거나 열쇠를 찾을 때, 방향을 바꾸거나 건너뛰어 찾을 수 없다.
  한 객실 문앞에서 현재 열쇠를 넣어 보고 안 맞으면 다음 열쇠를 넣어 보고 하는 식으로 해야 한다.

 

 

 

객실 복도 역시 원형으로 연결되어 있어 N번 객실 다음이 1번 객실 이다.
방문하는 모든 객실은 가지고 있는 열쇠중에 객실번호와 맞는 하나로만 열고 잠글 수 있다.
또한 준혁이가 모르는 사실하나는 이 테스트가 준혁이의 인내와 끈기를 테스트하는 것이라고 한다.
준혁이는 끈기있는 사람이라 테스트가 끝날때까지 한 마디 말도 없이 묵묵히 임무를 수행한다.
끝나고 나서 한 마디 하는데 “지금까지 객실문 열고 잠그기 시도에서 실패한 횟수의 총합은 몇 번일까?”라고 혼자말을 한다. 고생한 준혁이를 위하여 이 궁긍즘을 해결해주자.

 

입력 예 2번을 보자.
객실수(열쇠수)는 4개이고 객실문 열고 잠그기 실기 테스트 회수는 6이다.
열쇠고리에 주어진 열쇠 순서는 4, 2, 1, 3이다.
1번 객실을 열어야 하므로 4, 2, 1, 3 두 번 실패 후 성공, 열쇠 순서는 1, 3, 4, 2 가 된다.
2번 객실을 열어야 하므로 1, 3, 4, 2 세 번 실패 후 성공, 열쇠 순서는 2, 1, 3, 4 가 된다.
3번 객실을 열어야 하므로 2, 1, 3, 4 두 번 실패 후 성공, 열쇠 순서는 3, 4, 2, 1 이 된다.
4번 객실을 열어야 하므로 3, 4, 2, 1 한 번 실패 후 성공, 열쇠 순서는 4, 2, 1, 3 이 된다.
1번 객실을 열어야 하므로 4, 2, 1, 3 두 번 실패 후 성공, 열쇠 순서는 1, 3, 4, 2 가 된다.
2번 객실을 열어야 하므로 1, 3, 4, 2 세 번 실패 후 성공, 열쇠 순서는 2, 1, 3, 4 가 된다.
따라서 실패횟수의 합은 13번이 된다.


입력형식

첫 행에 객실수(==열쇠의 수)를 나타내는 N과 객실문 열고 잠그기 테스트 횟수 K가 입력된다.( 1 <= N <= 100,000, 1 <= K <= 1,000,000,000) 이어서 N개의 행에 열쇠의 번호가 입력된다. 입력 데이터의 40%는 1 <=N, K <= 1,000 이다. 입력 데이터의 60%는 1 <= K <= 50,000 이다.

출력형식

준혁이가 객실문 열고 잠그기 시도에서 실패한 횟수의 합을 하나의 정수로 출력한다.

입력 예

3 5
1
2
3

출력 예

4

입력 예

4 6
4
2
1
3

출력 예

13

입력 예

10 7
1
3
2
4
5
7
6
8
9
10

출력 예

25


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP