시간 제한메모리 제한제출정답맞힌 사람정답 비율
4 초 512 MB65201427.451%

문제

지훈이는 평소에 자주 들어가지 않는 어떤 사이트에 오랜만에 들어가려고 했는데, 비밀번호를 잊어버렸다는 사실을 깨달아 버렸다!

그래서 지훈이는 비밀번호 찾기를 하려고 하였으나, 그 사이트는 암호를 해시를 이용하여 관리하기 때문에, 지훈이가 잃어버렸던 비밀번호를 다시 복구하지는 못하고, 새로 비밀번호를 만들라고 하였다. 그 사이트는 보안을 철저하게 하는 사이트였기 때문에, 비밀번호를 정할 때 다음과 같은 조건을 충족시킬 것을 의무화하고 있다.

  • 비밀번호의 길이는 A이상이어야 한다.
  • 비밀번호에 숫자는 B글자 이상 있어야 한다.
  • 비밀번호에 특수 문자(숫자나 알파벳이 아닌 문자)는 C개 이상 있어야 한다.
  • 비밀번호에 알파벳 대문자는 D개 이상 있어야 한다.

그래서 지훈이는 다음과 같은 과정으로 비밀번호를 만들려고 한다.

  1. 임의로 글자(여기서 글자는 알파벳 대소문자, 숫자, 특수문자!@#\$%^&*()_-를 의미한다)를 N개 생성하여 문자열을 만든다.
  2. 총 N(N-1)/2개의 연속부분문자열들이 존재할텐데, 하나씩 살펴보면서 위 조건을 만족하는 경우에만 후보 리스트에 넣어 둔다. 이때 똑같은 연속부분문자열이 두 번 이상 등장하더라도 한 번만 고려한다. (ex - “abab”에서 “ab”는 후보 리스트에 한 개만 들어있음)
  3. 후보 리스트에 든 연속부분문자열들을 사전순으로 정렬한다.
  4. 후보 리스트에 든 연속부분문자열의 개수가 M 이고, candidate[1...M]에 저장되어 있을 때, candidate[(M+1)/2] 을 최종 비밀번호로 채택한다.

지훈이는 길이 N의 문자열을 작성했는데, 비밀번호의 조건이 너무 까다로운 나머지 비밀번호로 어떤 것이 채택될 지 알 수가 없어서 여러분에게 비밀번호를 구해 달라고 요청했다. 지훈이가 쓴 길이 N의 문자열이 주어질 때, 지훈이가 최종적으로 채택할 비밀번호를 출력하라.

입력

첫째 줄에 다섯 정수 N, A, B, C, D가 띄어쓰기로 구분되어 차례대로 주어진다.

둘째 줄에 지훈이가 쓴 길이 N의 문자열이 주어진다.

출력

지훈이가 최종적으로 채택하게 될 비밀번호를 출력한다. 답이 항상 존재하는 경우만 주어진다.

제한

  • 1 ≤ N ≤ 500000
  • 1 ≤ A ≤ N
  • 0 ≤ B, C, D ≤ N

예제 입력 1

10 9 1 0 1
h4llowOrld

예제 출력 1

h4llowOrl

출처

University > KAIST > 2016 KAIST 6th ACM-ICPC Mock Competition H번

  • 문제를 만든 사람: jihoon