#P2591. [ZJOI2009] 函数

    ID: 1599 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>各省省选浙江2009容斥状态压缩状压最小割

[ZJOI2009] 函数

题目描述

NN 个连续函数 fi(x)f_i(x),其中 1iN1\le i\le N。如果对于任意不相等的 i,ji,j 满足 1i,jN1\le i,j\le N,恰好存在一个 xx 使得 fi(x)=fj(x)f_i(x)=f_j(x),并且存在无穷多的 xx 使得 fi(x)<fj(x)f_i(x)<f_j(x),对于任意 i,j,ki,j,k 满足 1i<j<kN1\le i < j < k\le N,不存在 xx 使得 fi(x)=fj(x)=fk(x)f_i(x)=f_j(x)=f_k(x),则称这 NN 个连续函数满足条件。

如上左图就是 33 个满足条件的函数,最左边从下往上依次为 f1,f2,f3f_1,f_2,f_3。右图中红色部分是这整个函数图像的最低层,我们称它为第一层。同理绿色部分称为第二层,蓝色部分称为第三层。注意到,右图中第一层左边一段属于 f1f_1,中间属于 f2f_2,最后属于 f3f_3。而第二层左边属于 f2f_2,接下来一段属于 f1f_1,再接下来一段属于 f3f_3,最后属于 f2f_2。因此,我们称第一层分为了三段,第二层分为了四段。同理第三层只分为了两段。求满足前面条件的 NN 个函数,第 KK 层最少能由多少段组成。

输入格式

一行两个整数 N,KN,K

输出格式

一行一个整数,表示 NN 个函数第 KK 层最少能由多少段组成。

1 1

1

提示

对于 100%100\% 的数据满足 1KN1001\le K\le N\le 100