시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 103 | 57 | 41 | 56.944% |
어떤 프로그래밍 대회에서는 경기를 끝마치고 나면 뒤풀이로 빙고 게임을 하는 이상한 관습이 있다고 합니다. 하지만 이 빙고 게임에서 사용되는 "빙고 표"는 보통 빙고 게임과 다르게 밑에 있는 조건에 따라 빈 칸을 채워야 합니다.
아래 그림은 N = 5, M = 50, S = 685일 때 빙고 표 배치로 나올 수 있는 예입니다.
뒤풀이에 참석하고 싶어하는 사람이 많기 때문에 될 수 있는 한 많은 빙고 표를 만들려고 합니다. 하지만 모든 사람들은 자신만의 빙고 표를 갖고 싶어합니다. 그러므로 같은 빙고 표를 2개 이상 만들어선 안 됩니다. 만들 수 있는 빙고 표 개수의 최댓값을 100,000으로 나눈 값을 출력하는 프로그램을 작성하세요.
입력은 1줄입니다. 그 줄에는 각각 빙고 표의 크기 N(1 ≤ N ≤ 7)과 숫자 칸에 적혀 있는 정수들의 최댓값 M(1 ≤ M ≤ 2000), 빙고 표에 적혀 있는 정수의 합계인 S(1 ≤ S ≤ 3000)을 나타내는 3개의 정수가 공백으로 구분되어 주어집니다.
주어지는 모든 입력 데이터에 대해서, 조건을 만족하는 빙고 표를 적어도 1개 이상 만드는 것이 가능합니다.
만들 수 있는 빙고 표 개수의 최댓값을 100,000으로 나눈 값을 출력하세요.
3 9 45
1
3 100 50
7
5 50 685
74501
예제 입력 3을 예로 들면 만들 수 있는 빙고 표의 최대 개수는 642499974501개이고, 이를 100,000으로 나누면 74501이 됩니다.
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2008/2009 예선 6번