5470번 - 균형잡힌 직선형 정원 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 142 | 70 | 59 | 55.660% |
문제
람세스 2세가 전투에서 승리를 거두고 귀환했다. 그는 승리를 기리기 위해 웅장한 정원을 조성하기로 결심했다. 그래서 궁궐이 있는 Lubrr에서부터 시작해 Karnak 신전에 이르는 긴 길을 따라 식물을 일렬로 쭉 심을 예정이다. 심는 식물은 연꽃(L)과 파피루스(P) 이렇게 단 두 종류이다. 이들은 각각 이집트 북부와 남부의 상징이기 때문이다.
정원에는 그런 식으로 N개의 식물을 심는데, 종류별 식물 배치에 균형이 있어야 한다. 정원 내부의 어떤 연속적인 구간이라도 연꽃과 파피루스의 개수 차이가 2를 넘어서는 안 된다.
람세스가 세우고자 하는 정원은 L 아니면 P로 이루어진 문자열로 나타낼 수 있다. 예를 들어 N=5인 경우 위에서 제시한 균형을 갖춘 정원은 14가지가 있을 수 있다. (LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP, PPLPL)
그리고 특정 길이에 대해 균형을 갖춘 정원 식물 배치를 나타내는 문자열들은 알파벳 오름차순으로 나열하여 1부터 번호를 매길 수 있다. 가령 N=5의 경우, 12번에 해당하는 정원 문자열은 PLPPL이다.
길이가 N인 균형 잡힌 정원을 나타내는 어떤 문자열을 입력 받아 이것이 그 길이에 해당하는 전체 균형 잡힌 정원 문자열 중 오름차순으로 몇째 순서에 해당하는지 서열을 구하고, 이 값을 어떤 정수 M으로 나눈 나머지를 출력하는 프로그램을 작성하시오.
이 M이라는 수는 문제 풀이를 더 쉽게 해 주기 위해 있는 것으로, 다른 의미는 없음을 밝힌다.
입력
첫째 줄에는 심을 식물의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
둘째 줄에는 정수 M이 주어진다. (7 ≤ M ≤ 10,000,000)
셋째 줄에는 길이가 N이며, L(연꽃)과 P(파피루스)로 이루어진 균형 잡힌 정원을 나타내는 문자열이 주어진다.
출력
0 이상 M 미만의 정수 하나를 출력한다.
입력에서 주어진 정원 문자열의 오름차순 서열을 M으로 나눈 나머지의 값이다.
예제 입력 1
5 7 PLPPL
예제 출력 1
5
예제 입력 2
12 10000 LPLLPLPPLPLL
예제 출력 2
39
힌트
예제 입력에서 PLPPL은 사실 12번째에 있는 정원 배열이다. 그래서 12를 7로 나눈 나머지인 5를 정답으로 한다.
출처
Olympiad > International Olympiad in Informatics > IOI 2008 > Day 2 4번
- 문제의 오타를 찾은 사람: portableangel
- 문제를 번역한 사람: race0630
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호