//A - Insomnia cure
//第一题的意思就是有a,b,c,d四个数和一个龙的总数f,龙的编号是从1-f,看有多少个不能被a,b,c,d中能整除的数num,然后f-num就为答案
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int a,b,c,d;
int main()
{
int n;
cin>>a>>b>>c>>d;
cin>>n;
int num=0;// 能被a,b,c,d中能整除的数num
for(int i=1;i<=n;i++)
{
if(i%a!=0&&i%b!=0&&i%c!=0&&i%d!=0)
{
num++;
}
}
cout<<n-num<<endl;
return 0;
}
//B - Escape
// 第二题的意思就是给你公主的速度vp,龙的速度vd,和一开始公主先走龙没走的时间t,然后龙研究物体的时间(会老巢
// 研究)f和老巢到终点的距离c,这是一道很简单的模拟题 ,求最少要丢多少东西才能保证安全到达终点,可以是恰好到(就是到终点时龙也到)
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int vp,vd,t,f,s;
int main()
{
cin>>vp>>vd>>t>>f>>s;
if(vp>vd)//如果公主的速度比龙快,那么肯定不要扔东西
{
cout<<0<<endl;
return 0;
}
double place=0,time,t1,t2;
int num=0;
place=t*vp;//公主先出发,等到龙出发时公主的位置
time=place/(vd-vp);//第一次龙追上公主的时间
place+=time*vp;//计算出第一次龙追上公主时公主的位置,这里也可以写place=time*vd;
while(place<s)//循环,知道公主到达目的地
{
num++;//每次快追上时扔东西
t1=place/vd+f;//龙回去+研究物体的时间
place+=t1*vp;//计算出这段时间公主的位置
t2=place/(vd-vp);//龙又追上公主的时间
place+=t2*vp;//此时公主的位置
}
cout<<num<<endl;
return 0;
}
//C - Terse princess
// 第三题的意思就是构造一个数组,如果前面任意一个的值都小于后一个,就oh一声,如果前面任所有值的和小于后一个数,就wow一声,wow了就不oh了
//输入数组的长度n,oh a次,wow b次。最简单的方法就是用二进制做,001+010<100,0001+0010<0100等可以用来表示wow,用+1的方法表示oh
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,a,b;
int p[105];
int main()
{
while(cin>>n>>a>>b)
{
p[0]=1;//开始默认为第一个为1
for(int i=1;i<n;i++)
{
if(b)
{
p[i]=1<<i;//先把wow搞完
b--;
}
else if(a&&i>1)// 因为p[0]=1,p[1]=2的话,会变成喊了一声wow可如果没有b的话就不需要喊
{
p[i]=p[i-1]+1;
a--;
}
else
{
p[i]=p[i-1];//补充到n个数,相等的话就不会叫了
}
}
if(a||b)//如果还存在wow,oh说明没有这个解,可能是n小
{
cout<<-1<<endl;
}
else
{
for(int i=0;i<n-1;i++)
{
cout<<p[i]<<" ";
}
cout<<p[n-1]<<endl;
}
}
return 0;
}
//D - Bag of mice
//第四题的意思为抽老鼠,谁先抽到白老鼠谁就赢,如果谁都没抽到白老鼠(就是龙抽的时候逃走了白老鼠)就算是龙赢,现在求公主赢的概率
//概率dp,公主赢的话肯定是抽到了白老鼠,有3种情况公主可能赢
//(1)公主抽到了白老鼠
//(2)公主没有抽到白老鼠,龙也没有,逃走的老鼠也不是白的
//(3)公主没有抽到白老鼠,龙也没有,逃走的老鼠是白的(保证还有白老鼠)
//公主先抽 ,w为白老鼠的数目,b为黑老鼠的数目
#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
using namespace std;
double dp[1005][1005];//表示有多少只白老鼠和多少只的黑老鼠公主赢的概率
int w,b;
int main()
{
cin>>w>>b;
memset(dp,0,sizeof(dp));
for(int i=1;i<=w;i++)//表示如果没有黑老鼠,那么如果公主选,肯定是公主赢
{
dp[i][0]=1;
}
for(int i=1;i<=b;i++)//表示如果没有白老鼠,公主必输
{
dp[0][i]=0;
}
for(int i=1;i<=w;i++)
{
for(int j=1;j<=b;j++)
{
dp[i][j]+=(double)i/(i+j);//第一种情况,看清楚是加法,不是等于,因为有不同的情况
if(j>=2)//要有2只或以上的老鼠才能出现第二种情况
{
dp[i][j]+=(double)j/(i+j)*(double)(j-1)/(i+j-1)*(double)i/(i+j-2)*dp[i-1][j-2];//注意无论抽掉什么老鼠都要在总数上减去,对应的老鼠种类的数目也要减
}
if(j>=3)//只有3中老鼠才能出现第三种情况
{
dp[i][j]+=(double)j/(i+j)*(double)(j-1)/(i+j-1)*(double)(j-2)/(i+j-2)*dp[i][j-3];//注意同上
}
}
}
cout<<setiosflags(ios::fixed)<<setprecision(9)<<dp[w][b]<<endl;
return 0;
}
//D - Bag of mice
//第5题的意思公主发脾气会摔瓶子,有n层的架子,每层放有num个瓶子,每个瓶子都有对应的价值,求出公主叫几声(就是摔瓶子数)造成的
//总价值最高为多少
// 多重背包问题,每一层取几个,每层只能选最旁边的,可以是左边,又可以是右边,把层数看成物品种类,叫的次数即m看成背包的容量
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int d[100005],sum[100005];//sum为每一层各个花瓶的价值的和,d根据多重背包可得(因为每一层可以取不同的个数)
int w[100005];//表示每一层取n个的最大值
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int num,s;
cin>>num;
for(int j=1;j<=num;j++)//sum[0]==0永远成立
{
cin>>s;
sum[j]=sum[j-1]+s;
}
memset(w,0,sizeof(w));
for(int j=0;j<=num;j++)
{
for(int k=0;k<=j;k++)
{
w[j]=max(w[j],sum[k]+sum[num]-sum[num+k-j]);//表示前面取k个,后面取j-k个,这一层总共取j个。。
}
}
for(int j=m;j>=1;j--)//把摔的次数看成背包的容量,进行枚举
{
for(int k=0;k<=min(j,num);k++)// 随便取啊,但是要注意,万一这一层没有m个花瓶就惨了,所以要取最小值
{
d[j]=max(d[j],d[j-k]+w[k]);
}
}
}
cout<<d[m]<<endl;
return 0;
}