2060:
#include <cstdio>
using namespace std;
int ball[10] = {0};
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
int b, p ,o; // 剩余球的数量,自己得分,对手得分
scanf("%d %d %d", &b, &p, &o);
if(b >= 7)
{
p += (b-6) + (b-6) * 7;
for(int i=2; i<=7; i++)
p += i;
}
else if(b < 7)
{
for(int i=7; i>7-b; i--)
p += i;
}
if(p >= o)
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
2061:
#include <cstdio>
#include <cstring>
using namespace std;
struct node{
char cname[30+7];
double credit;
double score;
};
struct node a[100000+7];
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
int k;
scanf("%d", &k);
double tc = 0, ts = 0; // 记录学分,学分*成绩的总和
bool flag = false;
for(int i=0; i<k; i++)
{
scanf("%s %lf %lf", &a[i].cname, &a[i].credit, &a[i].score);
tc += a[i].credit;
if(a[i].score < 60)
flag = true;
}
if(flag)
printf("Sorry!\n");
else
{
for(int i=0; i<k; i++)
{
ts += a[i].credit * a[i].score;
}
double ans = 1.0 * ts / tc;
printf("%.2lf\n", ans);
}
if(n != 0)
printf("\n");
}
return 0;
}
2062:
#include <cstdio>
using namespace std;
typedef long long LL;
LL n; // 元素的个数
LL m;
int s[20+7]; // 分组后每组的首元素
LL g[20+7]; // 分组后每组子集的个数
void init()
{
g[0] = 0;
for(int i=1; i<27; i++)
g[i] = g[i-1] * (i-1) + 1;
}
int main()
{
init();
while(scanf("%lld %lld", &n, &m) != EOF)
{
for(int i=0; i<27; i++)
s[i] = i;
while(n>0 && m>0) // 只有n个元素最多执行n次,或者执行到m=0
{
// 第m个子集在分组后在第t组
int t = m / g[n] + (m%g[n]>0?1:0);
if(t > 0)
{
printf("%d", s[t]);
for(int i=t; i<=n; i++) // 删除i以后,i之后的要加一,比如删除2,那么下次的第二组开头是3
s[i] = s[i+1];
// 减去1 - t-1组无用的和删除i后当前组第一个元素变成的空集。方便在当前组内重新分组,并重新定位t
m = m - ((t-1)*g[n] + 1);
if(m == 0) printf("\n"); // 格式控制
else printf(" ");
}
n --; // 循环每执行一次减一,因为删除了一个元素
}
}
return 0;
}
2063:
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 500+7;
int k, male, female;
int line[MAXN][MAXN];
int used[MAXN], man[MAXN];
int find(int x)
{
for(int i=1; i<=male; i++)
{
if(used[i]==0 && line[x][i])
{
used[i] = 1;
if(man[i]==0 || find(man[i]))
{
man[i] = x;
return 1;
}
}
}
return 0;
}
int main()
{
while(scanf("%d", &k), k)
{
memset(line, 0, sizeof(line));
memset(man, 0, sizeof(man));
scanf("%d %d", &female, &male);
int f, m;
for(int i=0; i<k; i++)
{
scanf("%d %d", &f, &m);
line[f][m] = 1;
}
int sum = 0;
for(int i=1; i<=female; i++)
{
memset(used, 0, sizeof(used));
if(find(i))
sum ++;
}
printf("%d\n", sum);
}
return 0;
}
2064:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[40];
int main()
{
a[1] = 2;
for(int i=2; i<=40; i++)
{
a[i] = a[i-1] * 3 + 2;
}
int n;
while(scanf("%d", &n) != EOF)
{
printf("%lld\n", a[n]);
}
return 0;
}
2065:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 100;
typedef long long LL;
struct matrix{
int m[4][4];
};
const matrix E = { // 某个矩阵的0次幂是单位矩阵
1, 0, 0 ,0,
0, 1, 0, 0,
0, 0, 1, 0,
0, 0, 0, 1,
};
const matrix P = {
2, 1, 1, 0,
1, 2, 0, 1,
1, 0, 2, 1,
0, 1, 1, 2,
};
matrix multi(const matrix &a, const matrix &b) // 矩阵乘法
{
matrix c;
for(int i=0; i<4; i++)
{
for(int j=0; j<4; j++)
{
c.m[i][j] = 0;
for(int k=0; k<4; k++)
c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
}
}
return c;
}
matrix pow_mod(LL n) // 快速幂运算
{
matrix res = E, a = P;
while(n)
{
if(n&1)
res = multi(res, a);
a = multi(a, a);
n = n/2;
}
return res;
}
int main()
{
int t;
while(scanf("%d", &t), t)
{
for(int i=1; i<=t; i++)
{
LL n;
scanf("%lld", &n);
printf("Case %d: %d\n", i, pow_mod(n).m[0][0]);
}
puts("");
}
return 0;
}
2066:
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;
struct edge{
int to, cost; // to是到达的点,cost是对应的权值
};
typedef pair<int, int> P; // first是最小权值,second是顶点编号
vector<edge> G[N];
int dis[N];
int t, s, d;
void djk(int s)
{
priority_queue<P, vector<P>, greater<P> > q; // 优先队列,权值越小优先级越高
for(int i=0; i<N; i++) // 初始化
dis[i] = INF;
dis[s] = 0;
q.push(P(0, s)); // 把起点放入队列中
while(!q.empty())
{
P p = q.top(); q.pop();
int v = p.second;
if(dis[v] < p.first) continue;
for(int i=0; i<G[v].size(); i++) // 遍历当前顶点所能到达的所有顶点
{
edge e = G[v][i];
if(dis[e.to] > dis[v] + e.cost) // 如果到下一个点的距离大于通过当前这个点到下一个点的距离,就更新下一个点的最小距离
{
dis[e.to] = dis[v] + e.cost;
q.push(P(dis[e.to], e.to)); // 更新后放入队列中
}
}
}
}
int maps[N][N]; // 用于辅助的邻接矩阵,方便去掉重边
int main()
{
while(scanf("%d %d %d", &t, &s, &d) != EOF)
{
for(int i=0; i<N; i++) G[i].clear();
int a;
edge b;
for(int i=0; i<N; i++)
for(int j=0; j<N; j++)
maps[i][j] = INF;
for(int i=0; i<t; i++)
{
scanf("%d %d %d", &a, &b.to, &b.cost);
// G[a].push_back(b);
// a可能到b,b也可能到a,而且权值可能不一样
maps[a][b.to] = maps[b.to][a] = min(min(maps[a][b.to], maps[b.to][a]), b.cost); // 去重边
}
for(int i=0; i<N; i++) // 把边从邻接矩阵中读入邻接表
{
for(int j=0; j<N; j++)
{
if(maps[i][j] != INF)
{
b.to = j;
b.cost = maps[i][j];
G[i].push_back(b);
}
}
}
for(int i=0; i<s; i++)
{
scanf("%d", &b.to);
b.cost = 0;
G[0].push_back(b);
}
djk(0);
int ans = INF;
for(int i=0; i<d; i++)
{
scanf("%d", &a);
ans = min(ans, dis[a]);
}
printf("%d\n", ans);
}
return 0;
}
2067:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 40;
typedef long long LL;
LL a[N][N];
int main()
{
int n;
int cnt = 1;
while(scanf("%d", &n), n != -1)
{
for(int i=0; i<N; i++)
{
a[i][0] = 1; // 棋盘边上的点只有一条路径
a[0][i] = 1;
}
for(int i=1; i<N; i++)
{
for(int j=1; j<i; j++)
{
a[i][j] = a[i-1][j] + a[i][j-1];
}
a[i][i] = a[i][i-1];
}
// a[n][n] = a[n][n-1];
printf("%d %d %lld\n", cnt++, n, 2 * a[n][n]);
}
return 0;
}
2068:
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
typedef long long LL;
LL a[N];
LL c[N][N];
void tri() // 杨辉三角求组合数
{
for(int i=1; i<N; i++)
{
c[i][0] = c[i][i] = 1;
for(int j=1; j<i; j++)
c[i][j] = c[i-1][j] + c[i-1][j-1];
}
}
int main()
{
tri();
a[1] = 0;
a[2] = 1;
for(int i=3; i<N; i++)
{
a[i] = (i-1) * (a[i-1] + a[i-2]);
}
int n;
while(scanf("%d", &n), n)
{
LL res = 0;
for(int i=0; i<=n/2; i++)
{
res += c[n][i] * a[i];
}
printf("%lld\n", res+1);
}
return 0;
}
2069:
#include <bits/stdc++.h>
using namespace std;
int a[] = {50, 25, 10, 5, 1};
int main()
{
int money;
while(scanf("%d", &money) != EOF)
{
int ans = 0;
for(int i=0; i<=100; i++)
{
if(i*50 > money) break;
for(int j=0; j<=100-i; j++)
{
if(i*50 + j*25 > money) break;
for(int k=0; k <= 100 -i -j; k++)
{
if(i*50 + j*25 + k*10 > money) break;
for(int h=0; h <= 100 -i -j -k; h++)
{
if(i*50 + j*25 + k*10 + h*5 > money) break;
for(int u=0; u <= 100 -i -j -k -h; u++)
{
if(i*50 + j*25 + k*10 + h*5 + u*1 > money)
break;
if(i*50 + j*25 + k*10 + h*5 + u*1 == money)
{
ans ++;
break;
}
}
}
}
}
}
printf("%d\n", ans);
}
return 0;
}