1176번

수정 전

시간 제한 메모리 제한
2 초 128 MB

문제

  조교는 N명의 학생들을 벌주기 위해 한 방에 불러 앉혔다. 그리고 이 N명을 어깨동무 앉았다 일어나기를 시키려한다. 하지만 아이들을 최대한 힘들게 하기위한 방법을 고민하던 중 모든 이웃한 학생들의 키 차이가 K를 초과하는 순서로 배열하는 방법을 생각해냈다.

  이에 현재 서있는 아이들의 순서를 섞어서 조건을 만족하는 순서로 재배열하는 가짓수가 총 몇 가지가 있는지 알고 싶었다. 예들 들어, 학생들의 키가 1, 3, 5, 2, 6, 4인 순서대로 섞였다면 모든 이웃한 학생 키가 1을 초과하지만 1, 3, 6, 5, 2, 4로 섞였다면 6과 5사이 차이가 1이기 때문에 조건을 만족하지 못한다.
 

입력

  첫 줄에는 학생의 수 N(1 ≤ N ≤ 15)과 최소 넘어야할 키의 차이 값 K(1 ≤ K ≤ 3,400)가 주어진다. 다음 N개의 줄에는 학생들의 키가 순서대로 들어온다. 키는 25,000 이하인 자연수만 들어온다.
 

출력

  첫 줄에 조건을 만족하는 가능한 배열의 개수를 출력한다.
 

예제 입력

4 1 3 4 2 1

예제 출력

2

힌트

수정 후

시간 제한 메모리 제한
2 초 128 MB

문제

  조교는 N명의 학생들을 벌주기 위해 한 방에 불러 앉혔다. 그리고 이 N명을 어깨동무 앉았다 일어나기를 시키려한다. 하지만 아이들을 최대한 힘들게 하기위한 방법을 고민하던 중 모든 이웃한 학생들의 키 차이가 K를 초과하는 순서로 배열하는 방법을 생각해냈다.

  이에 현재 서있는 아이들의 순서를 섞어서 조건을 만족하는 순서로 재배열하는 가짓수가 총 몇 가지가 있는지 알고 싶었다. 예들 들어, 학생들의 키가 1, 3, 5, 2, 6, 4인 순서대로 섞였다면 모든 이웃한 학생 키가 1을 초과하지만 1, 3, 6, 5, 2, 4로 섞였다면 6과 5사이 차이가 1이기 때문에 조건을 만족하지 못한다.
 

입력

  첫 줄에는 학생의 수 N(1 ≤ N ≤ 16)과 최소 넘어야할 키의 차이 값 K(1 ≤ K ≤ 3,400)가 주어진다. 다음 N개의 줄에는 학생들의 키가 순서대로 들어온다. 키는 25,000 이하인 자연수만 들어온다.
 

출력

  첫 줄에 조건을 만족하는 가능한 배열의 개수를 출력한다.
 

예제 입력

4 1 3 4 2 1

예제 출력

2

힌트