A 题目连接：HDU 5922 Minimum’s Revenge
水题，每次连接上1就行，就是一个等差数列。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int main() {
int n,t,cas=1;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
ll res=n;
printf("Case #%d: %lld\n",cas++,(res+2)*(res-1)/2);
}
return 0;
} B 题目链接：HDU 5923 Prediction
题意：一棵树，每个点代表一条边，每次选择几个点，需要把他的祖先也选上，然后把图里面相应的边连接上，问连接后的图有多少个联通块。
题解：可持续化并查集，每个顶点开一个并查集，维护从根节点到当前节点已经连接的图，再把自己这条边连上。
查询，把所有点的并查集合并一下就可以，然后输出合并后并查集块的个数。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e2+2;
const int maxm=1e4+5;
bool u[maxm];
int par[maxm][maxn];
struct node {
int x,y;
int fa;
} tree[maxm];
int n,m;
int find(int y,int x) {
return par[y][x]==x?x:par[y][x]=find(y,par[y][x]);
}
void dfs(int x) {
int fa=tree[x].fa;
u[x]=1;
if(u[fa]==0) {
dfs(fa);
} else {
if(x==1) {
// cout<<"1asd"<<endl;
for(int i=0; i<=n; i++)par[1][i]=i;
par[1][tree[x].x]=tree[x].y;
} else {
for(int i=0; i<=n; i++)par[x][i]=par[fa][i];
int X=find(x,tree[x].x),Y=find(x,tree[x].y);
if(X!=Y) {
par[x][X]=par[x][Y];
}
}
}
}
int main() {
int t,cas=1;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&n,&m);
for(int i=1; i<=m; i++) {
if(i==1)tree[i].fa=1;
else {
int x;
scanf("%d",&x);
tree[i].fa=x;
}
}
for(int i=1; i<=m; i++) {
u[i]=0;
scanf("%d%d",&tree[i].x,&tree[i].y);
}
for(int i=1; i<=m; i++) {
if(!u[i]) {
dfs(i);
}
}
int q;
scanf("%d",&q);
printf("Case #%d:\n",cas++);
while(q--) {
int k,s;
scanf("%d",&k);
int res=0;
for(int i=0; i<=n; i++)par[0][i]=i;
while(k--) {
scanf("%d",&s);
// for(int i=1; i<=n; i++)printf("%d ",par[s][i]);
for(int i=1; i<=n; i++) {
int t1=find(0,i),t2=find(s,i);
if(t1!=t2) {
int t3=find(0,t2);
if(t3!=t1) {
res++;
par[0][t1]=par[0][t3];
}
}
}
}
printf("%d\n",n-res);
}
}
return 0;
} C 题目连接：HUD 5924 Mr. Frog’s Problem
A/B+ B/A 只有在两个数最接近的时候最小，所以如果A<=C<D<=B,C /D+D/C必定小于于等 A/B+B/A所以只有和A B相同的时候才会满足条件。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
ll a,b,t,n;
int main() {
int cas=1;
cin>>t;
while(t--) {
cin>>a>>b;
printf("Case #%d:\n",cas++);
if(a==b) {
puts("1");
cout<<a<<" "<<b<<endl;
} else {
puts("2");
cout<<a<<" "<<b<<endl;
cout<<b<<" "<<a<<endl;
}
}
return 0;
} D 题目连接:HDU 5925 Coconuts
题意：给你一个R*C的矩阵中间有几个n个点，问分成了几个联通块，联通块的大小是多少。
题解：R，C范围是1e9肯定是要离散，离散之后变成了一个不到 2000*2000的矩阵，求联通块数量直接DFS一遍就可以了。
问题来了了，离散之后怎么求每个块的大小呢。
首先你是根据行和列分别离散，计算主要是把离散掉的重新算回来。
如下图加入黄色是你被覆盖的格子，你会把横着离散黑色的格子为一个格子，红色的竖着离散成一个格子。因此，你只要把这些离散的格子从新加回来就行了，另外还要加上中间那一块被离散掉的。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=205;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n;
map<int,int> mpx,mpy;
int x[maxn],y[maxn];
int lx[maxn],ly[maxn];
ll vx[maxn*10],vy[maxn*10];
int mp[maxn*10][maxn*10],mx,my;
int dx[]= {-1,0,1,0},dy[]= {0,-1,0,1};
ll ans[maxn*10];
void dfs(int tx,int ty,int pos) {
if(mp[tx][ty]!=0)return ;
mp[tx][ty]=pos;
++ans[pos];
for(int i=0; i<4; i++) {
int ttx=tx+dx[i],tty=ty+dy[i];
if(ttx>0&&ttx<=mx&&tty>0&&tty<=my) {
dfs(ttx,tty,pos);
}
}
}
int main() {
int cas=1,t;
// freopen("in.txt","r",stdin);
scanf("%d", &t);
while(t--) {
mpx.clear();
mpy.clear();
mem(ans,0);
int r,c;
scanf("%d%d",&r,&c);
scanf("%d",&n);
for(int i=0; i<n; i++) {
scanf("%d%d",&x[i],&y[i]);
lx[i]=x[i];
ly[i]=y[i];
}
lx[n]=r;
sort(lx,lx+n+1);
int d=0;
vx[d]=0;
for(int i=0; i<=n; i++) {
if(lx[i]==vx[d])continue;
else if(lx[i]==vx[d]+1) {
vx[d+1]=vx[d]+1;
mpx[lx[i]]=d+1;
d+=1;
} else if(lx[i]-d==2) {
vx[d+1]=vx[d]+1;
vx[d+2]=vx[d]+2;
mpx[lx[i]]=d+2;
d+=2;
} else {
vx[d+1]=vx[d]+1;
vx[d+2]=lx[i];
mpx[lx[i]]=d+2;
d+=2;
}
}
ly[n]=c;
sort(ly,ly+n+1);
mx=d;
d=0;
vy[d]=0;
for(int i=0; i<=n; i++) {
if(ly[i]==vy[d])continue;
else if(ly[i]==vy[d]+1) {
vy[d+1]=vy[d]+1;
mpy[ly[i]]=d+1;
d+=1;
} else if(ly[i]-d>=2) {
vy[d+1]=vy[d]+1;
vy[d+2]=ly[i];
mpy[ly[i]]=d+2;
d+=2;
}
}
my=d;
mem(mp,0);
for(int i=0; i<n; i++) {
mp[mpx[x[i]]][mpy[y[i]]]=-1;
}
int num=1;
for(int i=1; i<=mx; i++) {
for(int j=1; j<=my; j++) {
if(mp[i][j]==0) {
dfs(i,j,num++);
}
}
}
for(int j=1; j<=my; j++) { //把离散竖着的加起来
for(int i=1; i<=mx; i++) {
if(mp[i][j]!=-1) {
ans[mp[i][j]]+=vx[i]-vx[i-1]-1;
} else if(mp[i-1][j]!=-1) {
ans[mp[i-1][j]]+=vx[i]-vx[i-1]-1;
}
}
}
for(int i=1; i<=mx; i++) { //把横着离散掉的加起来
for(int j=1; j<=my; j++) {
if(mp[i][j]!=-1) {
ans[mp[i][j]]+=vy[j]-vy[j-1]-1;
} else if(mp[i][j-1]!=-1) {
ans[mp[i][j-1]]+=vy[j]-vy[j-1]-1;
}
}
}
for(int i=1; i<=mx; i++) { //把中间那块离散掉的加起来
for(int j=1; j<=my; j++) {
if(mp[i][j]!=-1) {
ans[mp[i][j]]+=(vy[j]-vy[j-1]-1)*(vx[i]-vx[i-1]-1);
} else if(mp[i-1][j-1]!=-1) {
ans[mp[i-1][j-1]]+=(vy[j]-vy[j-1]-1)*(vx[i]-vx[i-1]-1);
}
}
}
printf("Case #%d:\n%d\n",cas++,num-1);
sort(ans+1,ans+num);
for(int i=1; i<num; i++) {
printf("%lld",ans[i]);
if(i+1==num)printf("\n");
else printf(" ");
}
}
return 0;
}
下面是2组数据，正确答案能手算出来
/*
2
100 100
20
1 50
1 51
1 55
1 60
2 50
2 54
2 56
2 60
3 50
3 51
3 55
3 60
4 51
4 52
4 53
4 54
4 56
4 57
4 58
4 59
100 100
8
1 2
2 1
100 99
99 100
99 1
100 2
1 99
2 100
*/ E:题目链接 HDU 5926 Mr. Frog’s Game
水题不解释了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int ar[35][35];
int n,m;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
int main() {
int cas=1,t;
scanf("%d", &t);
while(t--) {
scanf("%d%d", &n, &m);
for(int i=0;i<n;++i){
for(int j = 0; j < m; ++j){
scanf("%d", &ar[i][j]);
}
}
int flag = 0;
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
for(int k=0;k<4;++k){
int px = i + dir[k][0],py = j + dir[k][1];
if(px<0||py<0||px>=n||py>=m)continue;
if(ar[px][py]==ar[i][j]){
flag=1;break;
}
}
if(flag)break;
}
if(flag)break;
}
for(int i=0;i<n;++i){
for(int j=i+1;j<n;++j){
if(ar[i][0]==ar[j][0]||ar[i][m-1]==ar[j][m-1]){
flag=1;break;
}
}
if(flag)break;
}
for(int i=0;i<m;++i){
for(int j=i+1;j<m;++j){
if(ar[0][i]==ar[0][j]||ar[n-1][i]==ar[n-1][j]){
flag=1;break;
}
}
if(flag)break;
}
printf("Case #%d: ",cas++);
if(flag)printf("Yes\n");
else printf("No\n");
}
return 0;
} F 题目链接：HDU 5927 Auxiliary Set
题意：随便选几个点作为不重要的点，其他的全是重要的点，然后把不重要的点中如果是两个不同节点的最近公共祖先就把他变为重要的点，问，选了几个不重要的点，最后重要的点总共有多少个。
题解：数据看的挺吓人的 1e3 组 1e5的数据那命去写啊，实际上没多少。。。。。直接按不重要的点深度排个序，如果是另外两个重要的点的LCA就变成重要的点。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=1e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int n,m;
struct edge {
int to,next;
} eg[maxn*2];
int head[maxn],tot;
void init() {
mem(head,-1);
tot=0;
}
void add(int u,int v) {
eg[tot].to=v;
eg[tot].next=head[u];
head[u]=tot++;
}
int dep[maxn],pre[maxn];
int u[maxn];
int res[maxn];
int num[maxn];
int dfs(int r,int p,int d) {
dep[r]=d;
pre[r]=p;
int ans=0;
for(int i=head[r]; i!=-1; i=eg[i].next) {
if(eg[i].to!=p) {
ans+=dfs(eg[i].to,r,d+1);
}
}
num[r]=ans;
return ans;
}
void read(int &sum) {
scanf("%d",&sum);
return ;
sum=0;
int flag=0;
char ch=getchar();
while(!(ch>='0'&&ch<='9')) {
if (ch == '-') {
flag = 1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=getchar();
if(flag)sum*=-1;
}
bool cmp(int &a,int &b) {
return dep[a]>dep[b];
}
int main() {
int t,cas=1;
scanf("%d",&t);
while(t--) {
read(n);
read(m);
init();
for(int i=0; i<n-1; i++) {
int a,b;
read(a);
read(b);
add(a,b);
add(b,a);
}
dfs(1,-1,1);
printf("Case #%d:\n",cas++);
while(m--) {
int k,d,ans=0;
read(k);
ans=n-k;
for(int i=0; i<k; i++) {
read(res[i]);
u[res[i]]=-1;
}
sort(res,res+k,cmp);
for(int i=0; i<k; i++) {
d=0;
for(int j=head[res[i]]; j!=-1; j=eg[j].next) {
int to=eg[j].to;
if(to==pre[res[i]]) {
continue;
} else {
if(u[to]<0) {
continue;
}
if(u[res[i]]==-1) {
u[res[i]]=1;
} else u[res[i]]++;
if(u[res[i]]==2) {
ans++;
break;
}
}
}
}
for(int i=0; i<k; i++)u[res[i]]=0;
printf("%d\n",ans);
}
}
return 0;
} H 题目连接：HDU 5929 Basic Data Structure
简单模拟一下就可以了，记录下一最后一个零的位置，因为到零除了是第一个位置之外全都必定是1.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int a[maxn];
int l,r;
int t,cas=1;
int Q;
char s[100];
deque<int> q;
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&Q);
int x;
bool b=1;
l=r=2e5+5;
printf("Case #%d:\n",cas++);
q.clear();
while(Q--) {
scanf("%s",s);
if(b) {
if(s[0]=='P'&&s[1]=='U') {
scanf("%d",&x);
a[++r]=x;
if(x==0)q.push_back(r);
} else if(s[0]=='Q') {
if(r==l)printf("Invalid.\n");
else if(r-l==1)printf("%d\n",a[r]);
else {
if(q.size()==0) {
printf("%d\n",(r-l)&1);
} else {
int k=q.front();
if(r==k)printf("%d\n",(k-l+1)&1);
else printf("%d\n",(k-l)&1);
}
}
} else if(s[0]=='R') {
b=0;
} else {
if(a[r]==0)q.pop_back();
--r;
}
} else {
if(s[0]=='P'&&s[1]=='U') {
scanf("%d",&x);
a[l--]=x;
if(x==0)q.push_front(l+1);
} else if(s[0]=='Q') {
if(r==l)printf("Invalid.\n");
else if(r-l==1)printf("%d\n",a[r]);
else {
if(q.size()==0)printf("%d\n",(r-l)&1);
else {
int k=q.back();
if(k==l+1)printf("%d\n",(r-k)&1);
else printf("%d\n",(r-k+1)&1);
}
}
} else if(s[0]=='R') {
b=1;
} else {
if(a[l+1]==0)q.pop_front();
++l;
}
}
}
}
return 0;
} I -题目链接：HDU - 5930 GCD
这题是真的难理解.这题要是不用线段树大家都会写吧，首先暴力从前面的每个位置到当前位置的GCD ，然后记录每个GCD的个数，更新一个点就是删除一个点，然后再加一个点，就是暴力从前面所有位置到后面所有位置的GCD，减去这个值。把值更新再一次算从前面所有位置到后面所有位置的GCD，然后加上去。
竟然会这个这个，这题就是用线段树维护一下GCD的值，，，就像二分一样，因为会有很长一段的GCD值是一样的，每次不用一个个去找，直接找到前面GCD改变的位置，然后减去上一次GCD改变的位置。也是一种暴力。。。修改其实也是一样的就是把前面GCD和后面GCD求一个GCD，然后前后GCD 的数量相乘
比如 1 1 1 2 4 4 4 前面3个数的GCD是3 个 1 和后面3个数 是 2 那么GCD为 gcd(1,2) 数量就是 3 * 3;
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
int g[maxn<<4],c[maxn];
int f[maxn<<4],a[maxn],aa[maxn],b[maxn],bb[maxn];
int A,B,n,m;
long long gcd(long long a,long long b) {
return b==0?a:gcd(b,a%b);
}
void build(int l,int r,int k) {
if(r-l==1) {
g[k]=c[r];
} else {
build(lson);
build(rson);
g[k]=gcd(g[chl],g[chr]);
}
}
int findleft(int l,int r,int k,int u,int v) {
if(r<=u) {
if(gcd(g[k],v)==v)return 0;
if(l+1==r)return r;
int x=findleft(rson,u,v);
if(x)return x;
else return findleft(lson,u,v);
}
if(u>mid) {
int x=findleft(rson,u,v);
if(x)return x;
}
return findleft(lson,u,v);
}
void getleft(int x) {
A=0;
for(int i=c[x],j=x,k; j!=0; j=k) {
k=findleft(0,n,0,j,i);
a[A]=j-k;
aa[A++]=i;
if(k==0)return ;
i=gcd(c[k],i);
}
return ;
}
int findright(int l,int r,int k,int u,int v) { //这个是用线段树往左找GCD
if(l+1>=u) {
if(gcd(g[k],v)==v)return n+1;
if(l+1==r)return r;
int x = findright(lson,u,v);
if(x<=n)return x;
else return findright(rson,u,v);
}
if(u<=mid) {
int x=findright(lson,u,v);
if(x<=n)return x;
}
return findright(rson,u,v);
}
void getright(int x) {
B=0;
for(int i= c[x],j=x,k; j<=n; j=k) { //这个是暴力X所有左边的GCD
k=findright(0,n,0,j,i);
b[B]=k-j;
bb[B++]=i;
i=gcd(c[k],i);
}
return ;
}
void change(int l,int r,int k,int u,int v) {
if (l+1==r) {
g[k] = v;
return;
}
if (u<=mid) change(lson,u,v);
else change(rson,u,v);
g[k]=gcd(g[chl],g[chr]);
}
int main() {
int t,cas=1;
scanf("%d",&t);
while(t--) {
printf("Case #%d:\n",cas++);
scanf("%d%d",&n,&m);
for(int i=1; i<=n; ++i)scanf("%d",&c[i]);
build(0,n,0); //初始化线段树
memset(f,0,sizeof(f));
int ans=0;
for(int i=1; i<=n; i++) {
getleft(i); //初始化只要找所有i左边的GCD或者右边也可以，但是只能找一边不然会重复。
for(int j=0; j<A; j++) {
if(!f[aa[j]])ans++;
f[aa[j]]+=a[j];
}
}
while(m--) {
int x,y;
scanf("%d%d",&x,&y);
getleft(x); //找到所有左边的GCD
getright(x); //找到所有右边的GCD
for(int j=0; j<A; j++) {//暴力所有左右两边GCD所有可能
for(int k=0; k<B; k++) {
int t=gcd(aa[j],bb[k]); //左右两边的GCD的GCD
f[t]-=1LL *a[j]*b[k]; // 暴力删除
if(!f[t])ans--;
}
}
c[x]=y;
change(0,n,0,x,y);
getleft(x);
getright(x);
for(int j=0; j<A; j++) {
for(int k=0; k<B; k++) {
int t=gcd(aa[j],bb[k]);//暴力添加
if(!f[t])ans++;
f[t]+=1LL*a[j]*b[k];
}
}
printf("%d\n",ans); // 得出结论
}
}
return 0;
}
J 题目链接：HDU5931 - Mission Possible
暴力所有速度，推一下公式，发现要么是用初始血量去掉不加血，要么是加血等于掉血数量的时候是最优解。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
#define bug printf("*********\n");
#define debug(x) cout<<"["<<x<<"]" <<endl;
#define mid (l+r)/2
#define chl 2*k+1
#define chr 2*k+2
#define lson l,mid,chl
#define rson mid,r,chr
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a));
const long long mod=1e9+7;
const int maxn=5e5+5;
const int INF=0x7fffffff;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
ll D,A,GA,GB,GC;
int main() {
int t,cas=1;
scanf("%d",&t);
while(t--) {
scanf("%lld%lld%lld%lld%lld",&D,&A,&GA,&GB,&GC);
ll v,r,h;
ll ans=1e18,temp;
for(v=1; v<=D; v++) {
double t=1.0*D/v;
temp=v*GB+A*GC+A*GA;
ans=min(ans,temp);
double tem2=t*A;
temp=v*GB+floor(t*A-eps+1)*GA;
// debug(temp-v*GB);
ans=min(ans,temp);
}
printf("Case #%d: %lld\n",cas++,ans);
}
return 0;
}
京公网安备 11010502036488号