Problem
https://vn.spoj.com/problems/LEM6
https://oj.vnoi.info/problem/LEM6
Chỉ năm nay nữa thôi là sherry sẽ tốt nghiệp Đại Học rồi vì thế sherry muốn sinh nhật năm nay của mình sẽ thật ý nghĩa. Và Sherry mời tất cả bạn của mình đến dự sinh nhật ^^
Sherry tổ chức 1 trò chơi nhỏ cho tất cả các bạn cùng tham gia, sherry có 1 tờ giấy HCN kích thước 1 x N và M mảnh nhỏ hơn, mảnh giấy thứ i có kích thước 1 x Ai. bây giờ sherry đố các bạn của mình có bao nhiêu cách đặt các mảnh giấy nhỏ theo thứ tự từ 1 đến M vào mảnh giấy 1 x N sao cho mỗi mảnh giấy cách nhau ít nhất 1 ô vuông ( Nếu i < j thì mảnh giấy thứ i sẽ được đặt nằm trước mảnh giấy thứ j ). Sherry hứa sẽ tặng 1 món quà đặc biệt cho bạn nào trả lời nhanh nhất :D
Input
Dòng 1: N, M ( 1 <= N <= 1000, 1 <= M <= N/2 )
Dòng 2: Gồm M số, số thứ i là Ai
Output
Gồm 1 dòng duy nhất là số cách tìm được
Example
Input
4 2
1 1
Output
3
Tutorial
Submission
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;
import java.text.*;
public class Main {
public static Scanner cin = new Scanner(System.in);
public static void main(String[] args) throws IOException {
/*
FileInputStream fi = new FileInputStream("D:/java.inp");
Scanner in = new Scanner(fi);
FileOutputStream fo = new FileOutputStream("D:/java.out");
PrintWriter out = new PrintWriter(fo);
*/
//BufferedReader in = new BufferedReader(new FileReader(new File("D:/java.inp")));
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
DecimalFormat df = new DecimalFormat("#.000");
//------------------------------------------------------------------------------//
String s[] = in.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
String t[] = in.readLine().split(" ");
int S = 0;
for (int i=0;i<m;i++) {
int x = Integer.parseInt(t[i]);
S += x;
}
if (n < S+m-1) {
System.out.println("0");
return;
}
BigInteger c[][] = new BigInteger[n+5][n+5];
for (int j=0;j<=n-S+1;j++)
for (int i=0;i<=j;i++) c[i][j] = BigInteger.valueOf(0);
for (int j=0;j<=n-S+1;j++) {
for (int i=0;i<=j;i++) {
if (i == 0 || i == j) {
c[i][j] = BigInteger.valueOf(1);
}
else {
c[i][j] = c[i][j-1].add(c[i-1][j-1]);
}
}
}
System.out.println(c[m][n-S+1]);
}
}