레이팅 미적용설명
베시는 커다란 바위에 새겨진 비문을 발견했다. 비문은 C, O, W 단 세 글자로 이루어진 알파벳을 쓰는 수수께끼의 고대 언어로 쓰여 있다. 베시는 이 글에 COW가 몇 번 나타나는지 궁금하다.
베시는 COW 사이에 다른 문자가 끼어 있어도 상관하지 않으며, 문자들이 올바른 순서로 나타나기만 하면 된다. 또한 서로 다른 COW의 등장이 일부 글자를 공유해도 상관하지 않는다. 예를 들어 CWOW에는 COW가 한 번, CCOW에는 두 번, CCOOWW에는 여덟 번 나타난다.
비문의 내용이 주어질 때, COW가 (반드시 연속일 필요는 없는) 부분 수열로 몇 번 나타나는지 세도록 베시를 도와주자.
제약
입력 형식
첫째 줄에 정수 N이 주어진다 (N <= 10^5). 둘째 줄에 N개의 문자로 이루어진 문자열이 주어지며, 각 문자는 C, O, W 중 하나이다.
출력 형식
입력 문자열의 부분 수열로 COW가 나타나는 횟수를 출력한다. 답이 매우 클 수 있으므로 64비트 정수를 사용해야 한다.
Standard input / output
This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:
입력을 읽을 파일
cow.in · 출력을 쓸 파일 cow.out예제 1
입력
6
COOWWW출력
6문제 정보
riseoj 작성
출처 올림피아드 > USACO > 2014-2015 > February > Bronze
태그