Rescue The Princess
Time Limit: 1000MS Memory limit: 65536K
题目描述
Several days ago, a beast caught a beautiful princess and the princess was put in prison. To rescue the princess, a prince who wanted to marry
the princess set out immediately. Yet, the beast set a maze. Only if the prince find out the maze’s exit can he save the princess.
Now, here comes the problem. The maze is a dimensional plane. The beast is smart, and he hidden the princess snugly. He marked
two coordinates of an equilateraltriangle
in the maze. The two marked coordinates are A(x1,y1) and B(x2,y2). The third coordinate C(x3,y3) is the maze’s exit. If the prince can find out the exit, he can save the princess. After the
prince comes into the maze, he finds out the A(x1,y1) and B(x2,y2), but he doesn’t know where the C(x3,y3) is. The prince need your help. Can you
calculate the C(x3,y3) and tell him?
输入
The first line is an integer T(1 <= T <= 100) which is the number of test cases. T test cases follow. Each test case contains two
coordinates A(x1,y1) and B(x2,y2), described by four floating-point numbers x1, y1, x2, y2 ( |x1|, |y1|, |x2|, |y2|<=
1000.0).
Please notice that A(x1,y1) and B(x2,y2) and C(x3,y3) are in an anticlockwise
direction from the equilateraltriangle. And coordinates A(x1,y1) and B(x2,y2)
are given by anticlockwise.
输出
to 2 decimal places in a line.
示例输入
4 -100.00 0.00 0.00 0.00 0.00 0.00 0.00 100.00 0.00 0.00 100.00 100.00 1.00 0.00 1.866 0.50
示例输出
(-50.00,86.60) (-86.60,50.00) (-36.60,136.60) (1.00,1.00)
告诉你是一个等边三角形并且给你两个点a(x1,y1)和b(x2,y2)，让你求第三个点，按照逆时针顺序求。
只要知道公式就会很容易做出，否则要推半天。向量的旋转，参考这个链接：点击打开链接。
#include<stdio.h>
#include<math.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
double x1,x2,y1,y2,x3,y3,x,y;
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
x=x2-x1;
y=y2-y1;
x3=x/2-y*sqrt(3)/2+x1;
y3=y/2+x*sqrt(3)/2+y1;
printf("(%.2f,%.2f)\n",x3,y3);
}
return 0;
}
Thrall’s Dream
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
We never paid any heed to the ancient prophecies, like fools we clung to the old hatreds, and fought as we had for generations. Until one day the sky rained fire, and a new enemy came upon us. We stand now upon the brink of destruction, for the Reign of
Chaos has come at last.
Thrall, the warchief of the Orcish Horde, all along, he led his tribe live in the fringe of Lordaeron under the human control. In a downpour night, Thrall falls into sleep in a Orc hall at Arathi Highlands, at this moment he heard a voice:
“The sands of time have run out, son of Durotan. The cries of war echo upon the winds, the remnants of the past scar the land which is besieged once again by conflict. Heroes arise to challenge fate, and lead their brethren to battle. As mortal armies rush
blindly towards their doom, The Burning Shadow comes to consume us all. You must rally the Horde, and lead your people to their destiny.
I will answer all of your questions in time, young warchief. For now, rally your warriors and prepare to leave this land, cross the sea to the distant land of Kalimdor. We will speak again. ”
Thrall believes the prophesy of Blood Raven Medivh. Three days later, He and Grom Hellscream's Warsong Clan meet in the Lordaeron coast to the distant lands of Kalimdor. But the Goblin Zeppelins they take encountered storms in the middle. Thrall and Grom
falling to the islands, they want to find each other and then to Kalimdor.
For the sake of simplicity, we assume that Thrall and Grom may fall into any islands x and y, only by Thrall to find Grom or by Grom to find Thrall. Give you the map of this island, please judge that Thrall and Gtom can meet?
输入
Next M lines each line contains two integers a and b, indicated there is a portal in island a that people can go from a to b by this portal. The island numbered from 1 to N.
输出
sample output.
示例输入
23 21 21 33 21 22 3
示例输出
Case 1: The Burning Shadow consume us allCase 2: Kalimdor is just ahead
提示
来源
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define M 2007
using namespace std;
int head[M],low[M],dfn[M],stack[M],vis[M];
int ans[M],cnt,scnt,num,top,n,m,countt,belong[M];
int indegree[M],outdegree[M];
int map[M][M];
struct E
{
int v,to;
}edg[M*20];
void init()
{
memset(head,-1,sizeof(head));
memset(vis,0,sizeof(vis));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
cnt=countt=num=top=0;
}
void addedge(int u,int v)
{
edg[num].v=v;
edg[num].to=head[u];
head[u]=num++;
}
void tarjan(int x)
{
int i;
dfn[x]=low[x]=++cnt;
stack[top++]=x;
vis[x]=true;
for(int i=head[x];i!=-1;i=edg[i].to)
{
int v=edg[i].v;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])
low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x])
{
countt++;
int tmp;
while(1)
{
tmp=stack[--top];
belong[tmp]=countt;
vis[tmp]=false;
if(tmp==x)break;
}
}
}
void output()
{
memset(map,0,sizeof(map));
memset(indegree,0,sizeof(indegree));
memset(outdegree,0,sizeof(outdegree));
int inde=0,outde=0,flag=0,flag1=0,flag2=0;
for(int i=1;i<=n;i++)
for(int j=head[i];j!=-1;j=edg[j].to)
{
int v=edg[j].v;
if(belong[i]!=belong[v])
map[belong[i]][belong[v]]=1;
}
for(int i=1;i<=countt;i++)
for(int j=1;j<=countt;j++)
if(map[i][j])
{
indegree[j]++;
outdegree[i]++;
}
for(int i=1;i<=countt;i++)
{
if(indegree[i]==0&&outdegree[i]==1)flag1++;
else if(indegree[i]==1&&outdegree[i]==0)flag2++;
else if(indegree[i]==1&&outdegree[i]==1)flag++;
}
if(flag==(countt-2)&&flag1==1&&flag2==1)printf("Kalimdor is just ahead\n");
else printf("The Burning Shadow consume us all\n");
}
int main()
{
int t;
scanf("%d",&t);
for(int textcase=1;textcase<=t;textcase++)
{
scanf("%d%d",&n,&m);
init();
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
addedge(a,b);
}
for(int i=1;i<=n;i++)
if(!dfn[i])tarjan(i);
printf("Case %d: ",textcase);
if(countt==1){printf("Kalimdor is just ahead\n");continue;}
output();
}
}
The number of steps
Time Limit: 1000MS Memory limit: 65536K
题目描述
Mary stands in a strange maze, the maze looks like a triangle（the first layer have one room，the second layer have two rooms，the third layer have three rooms
…）. Now she stands at the top point(the first layer), and the KEY of this maze is in the lowest layer’s leftmost room. Known that each room can only access to its left room and lower left and lower right rooms .If a room doesn’t have its left room, the probability
of going to the lower left room and lower right room are a and b (a + b = 1 ). If a room only has it’s left room, the probability of going to the room is 1. If a room has its lower left, lower right rooms and its left room, the probability of going to each
room are c, d, e (c + d + e = 1). Now , Mary wants to know how many steps she needs to reach the KEY. Dear friend, can you tell Mary the expected number of steps required to reach the KEY?
输入
输出
示例输入
3 0.3 0.7 0.1 0.3 0.6 0
示例输出
3.41
第一行有一个位置，第二行两个，第三行三个......第n行n个。此时你在最左上角的位置，如果你左面没有位置，只能往左下和右下走，概率(a,b)。否则可以往左，左下和右下三个方向走，,概率(c,d,e)。让你求到达最左下角的期望。
求期望的题目。可以看一下这个链接：点击打开链接
#include<stdio.h>
#include<string.h>
double dp[57][57];
int main()
{
int t;
while(scanf("%d",&t),t)
{
int i,j;
double a,b,c,d,e;
scanf("%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e);
memset(dp,0,sizeof(dp));
dp[t][1]=0;
for(i=1;i<=t-1;i++)
{
dp[t][i+1]+=(dp[t][i]+1);
}
for(i=t-1;i>=1;i--)
{
dp[i][1]+=a*(dp[i+1][1]+1)+b*(dp[i+1][2]+1);
for(j=2;j<=i;j++)
dp[i][j]+=c*(dp[i+1][j]+1)+d*(dp[i+1][j+1]+1)+e*(dp[i][j-1]+1);
}
printf("%.2lf\n",dp[1][1]);
}
return 0;
}
Alice and Bob
Time Limit: 1000MS Memory limit: 65536K
题目描述
Alice and Bob like playing games very much.Today, they introduce a new game.
There is a polynomial like this: (a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1). Then Alice ask Bob Q questions. In the expansion of the Polynomial, Given an integer P, please tell the coefficient of the
x^P.
Can you help Bob answer these questions?
输入
For each case, the first line contains a number n, then n numbers a0, a1, .... an-1 followed in the next line. In the third line is a number Q, and then following Q numbers P.
1 <= T <= 20
1 <= n <= 50
0 <= ai <= 100
Q <= 1000
0 <= P <= 1234567898765432
输出
示例输入
122 1234
示例输出
20
提示
给出一个多项式：(a0*x^(2^0)+1) * (a1 * x^(2^1)+1)*.......*(an-1 * x^(2^(n-1))+1)，输入P，求X^p
前边的系数。
将p转换成一个二进制的数，然后分别乘上系数。
#include<stdio.h>
#include<string.h>
int a[55],b[55];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,p,i,j;
scanf("%d",&n);
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d",&p);
int count,ans;
long long c;
while(p--)
{
count=1,ans=0;
scanf("%lld",&c);
if(c==0)
{
printf("1\n");
continue;
}
while(c)
{
b[ans++]=c%2;
c/=2;
}
for(i=0;i<ans;i++)
if(b[i])
{
count=count*a[i]%2012;
}
printf("%d\n",count);
}
}
return 0;
}
Contest Print Server
Time Limit: 1000MS Memory limit: 65536K
题目描述
输入
In each case,the first line contains 5 integers n,s,x,y,mod (1<=n<=100, 1<=s,x,y,mod<=10007), and n lines of requests follow. The request is like "Team_Name request p pages" (p is integer, 0<p<=10007, the length of
"Team_Name" is no longer than 20), means the team "Team_Name" need p pages to print, but for some un-know reason the printer will break down when the printed pages counter reached s(s is generated by the function s=(s*x+y)%mod ) and then the counter will become
0. In the same time the last request will be reprint from the very begin if it isn't complete yet(The data guaranteed that every request will be completed in some time).
You can get more from the sample.
输出
Please note that you should print an empty line after each case.
示例输入
23 7 5 6 177Team1 request 1 pagesTeam2 request 5 pagesTeam3 request 1 pages3 4 5 6 177Team1 request 1 pagesTeam2 request 5 pagesTeam3 request 1 pages
示例输出
1 pages for Team15 pages for Team21 pages for Team31 pages for Team13 pages for Team25 pages for Team21 pages for Team3
TeamA request B pages。按照这个形式输入第A个队伍需要打印B张纸。然后定义s=(s*x+y)%mod。当打印的纸张数>=s时，便会重新打印这个队伍的纸张。按照要求输出。
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
struct sa
{
int num;
string name;
}data[1007],cnt;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,s,x,y,mod,i,j,flag;
string name,tmp1,tmp2;
scanf("%d%d%d%d%d",&n,&s,&x,&y,&mod);
getchar();
for(i=1;i<=n;i++)
{
cin>>name>>tmp1>>flag>>tmp2;
data[i].name=name;
data[i].num=flag;
}
int count=0,ans=0;
for(i=1;i<=n;i++)
{
ans=count+data[i].num;
if(ans<=s)
{
count+=data[i].num;
cnt=data[i];
}
else
{
cnt.name=data[i].name;
cnt.num=s-count;
count=0;
s=(s*x+y)%mod;
if(s==0)s=(s*x+y)%mod;
i--;
}
cout<<cnt.num<<" pages for "<<cnt.name<<endl;
}
cout<<endl;
}
return 0;
}