시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 201 | 98 | 87 | 51.786% |
상근이는 라스베가스의 엘 도라도 카지노에 도착했다. 태어나서 카지노에 처음 가본 상근이는 휘황찬란한 카지노의 내부에 입을 다물 수 없었다. 그런 그의 눈길을 사로 잡는 게임이 하나있었다. 그 게임은 화면에 n개의 숫자가 화면에 뜨는 아주 단순해 보이는 게임이었다. 이 게임의 참가자는 컴퓨터가 만드는 수열에서 길이가 k인 증가하는 부분 수열의 개수를 예상해야 한다.
수열 a1, ..., an의 부분 수열은 1 ≤ i1 < i2 < ... < il ≤ n를 만족하는 ai1, ..., ail로 정의 한다. 부분 수열이 증가하려면 모든 1 < j ≤ l에 대해서, aij-1 < aij를 만족해야 한다.
상근이는 다른 사람이 작성한 프로그램을 믿지 않는다. 따라서, 기계에 표시된 정답 대신 자신이 직접 정답을 구해 보려고 한다. 기계의 화면에 표시된 숫자가 주어졌을 때, 길이가 k이면서 증가하는 부분 수열의 개수를 세는 프로그램을 작성하시오.
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 n과 k가 주어진다. (1 ≤ k ≤ n ≤ 100) 둘째 줄에는 컴퓨터가 만든 수열 ai가 주어진다. ai는 서로 중복되지 않는다. (-10000 ≤ ai ≤ 10000)
입력의 마지막 줄에는 0이 두 개 주어진다.
각각의 테스트 케이스에 대해서, 길이가 k인 증가하는 부분 수열의 개수를 출력한다. 이 값은 64비트 정수 범위를 넘지 않는다.
10 5 1 2 3 4 5 6 7 8 9 10 3 2 3 2 1 0 0
252 0
Contest > University of Ulm Local Contest > University of Ulm Local Contest 2008 E번