2313 - 灯的排列问题
设在一排上有N个格子（N≤20），若在格子中放置有不同颜色的灯，每种灯的个数记为N1，N2，……Nk（k表示不同颜色灯的个数）。
放灯时要遵守下列规则：
①同一种颜色的灯不能分开；
②不同颜色的灯之间至少要有一个空位置。
例如：N=8（格子数）
R=2（红灯数）
B=3（蓝灯数）
放置的方法有：
R-B顺序
|
R |
R |
|
B |
B |
B |
|
|
|
R |
R |
|
|
B |
B |
B |
|
|
R |
R |
|
|
|
B |
B |
B |
|
|
R |
R |
|
B |
B |
B |
|
|
|
R |
R |
|
|
B |
B |
B |
|
|
|
R |
R |
|
B |
B |
B |
B-R顺序
|
B |
B |
B |
|
R |
R |
|
|
|
B |
B |
B |
|
|
R |
R |
|
|
B |
B |
B |
|
|
|
R |
R |
|
|
B |
B |
B |
|
R |
R |
|
|
|
B |
B |
B |
|
|
R |
R |
|
|
|
B |
B |
B |
|
R |
R |
放置的总数为12种。
程序要求：求排列总数。
题目输入
数据输入的方式为：
N
P1（颜色，为一个字母） N1（灯的数量）
P2 N2
……
Q（结束标记，Q本身不是灯的颜色）
颜色和灯的数量之间由一个空格分隔。
题目输出
输出排列总数。
输入/输出样例
输入格式
8 R 2 B 3 Q
输出格式
12
C++解答
#include<iostream> using namespace std; int main() { char x; int k=0,t,n,ans=1,i; cin>>n; while(1) {cin>>x; if(x=='Q')break; cin>>t; k++; n-=t; } ans=1; for(i=-1;i<k-1;i++) ans*=(n-i); cout<<ans; }
Python解答
# coding=utf-8 def main(): N = int(input()) C = [] while True: temp = input() if temp == 'Q': break else: C.append(int(temp.split()[1])) N_color = len(C) N_space = N - sum(C) cnt_color = 1 for i in range(1, N_color+1): cnt_color *= i cnt_space = 1 nn = N_space - N_color + 1 for i in range(nn): cnt_space *= N_space + 1 - i for i in range(1, nn + 1): cnt_space /= i print(int(cnt_color*cnt_space)) if __name__ == '__main__': main()