The students of the HEU are maneuvering for their military training.
The red army and the blue army are at war today. The blue army finds that Little A is the spy of the red army, so Little A has to escape from the headquarters of the blue army to that of the red army. The battle field is a rectangle of size m*n, and the headquarters of the blue army and the red army are placed at (0, 0) and (m, n), respectively, which means that Little A will go from (0, 0) to (m, n). The picture below denotes the shape of the battle field and the notation of directions that we will use later.
image
The blue army is eager to revenge, so it tries its best to kill Little A during his escape. The blue army places many castles, which will shoot to a fixed direction periodically. It costs Little A one unit of energy per second, whether he moves or not. If he uses up all his energy or gets shot at sometime, then he fails. Little A can move north, south, east or west, one unit per second. Note he may stay at times in order not to be shot.
To simplify the problem, let’s assume that Little A cannot stop in the middle of a second. He will neither get shot nor block the bullet during his move, which means that a bullet can only kill Little A at positions with integer coordinates. Consider the example below. The bullet moves from (0, 3) to (0, 0) at the speed of 3 units per second, and Little A moves from (0, 0) to (0, 1) at the speed of 1 unit per second. Then Little A is not killed. But if the bullet moves 2 units per second in the above example, Little A will be killed at (0, 1).
Now, please tell Little A whether he can escape.
Input
For every test case, the first line has four integers, m, n, k and d (2<=m, n<=100, 0<=k<=100, m+ n<=d<=1000). m and n are the size of the battle ground, k is the number of castles and d is the units of energy Little A initially has. The next k lines describe the castles each. Each line contains a character c and four integers, t, v, x and y. Here c is ‘N’, ‘S’, ‘E’ or ‘W’ giving the direction to which the castle shoots, t is the period, v is the velocity of the bullets shot (i.e. units passed per second), and (x, y) is the location of the castle. Here we suppose that if a castle is shot by other castles, it will block others’ shots but will NOT be destroyed. And two bullets will pass each other without affecting their directions and velocities.
All castles begin to shoot when Little A starts to escape.
Proceed to the end of file.
Output
If Little A can escape, print the minimum time required in seconds on a single line. Otherwise print “Bad luck!” without quotes.
Sample Input
4 4 3 10
N 1 1 1 1
W 1 1 3 2
W 2 1 2 4
4 4 3 10
N 1 1 1 1
W 1 1 3 2
W 1 1 2 4
Sample Output
9
Bad luck!
题意：题意：
一个人从（0,0）跑到(n,m),只有k点能量，一秒消耗一点，在图中有k个炮塔，给出炮塔的射击方向c，射击间隔t，子弹速度v，坐标x,y
问这个人能不能安全到达终点
要求:
人不能到达炮塔所在的坐标,炮塔会挡住子弹,途中遇到子弹是安全的，但是人如果停在这个坐标，而子弹也刚好到这个坐标，人就被射死，人可以选择停止不动。
因为人可以选择原地不动，所以vis数组要开三维，每个时间只能访问某个地点一次。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<cstring>
#include<cmath>
using namespace std;
int m, n, k, d;
bool bullet[105][105][1005], vis[105][105][1005];
int map[105][105];
int dir[5][2] = { 0,0,0,-1,0,1,-1,0,1,0 };
struct node
{
int x;
int y;
int step;
};
struct tank
{
int d;
int t, v, x, y;
}tk[105];
void init()
{
for (int i = 0;i < k;i++)
{
for (int j = 0;j <= d;j += tk[i].t)
for (int k = 1;;k++)
{
int nx = tk[i].x + k * dir[tk[i].d][0];
int ny = tk[i].y + k * dir[tk[i].d][0];
if (nx<0 || ny<0 || nx>n || ny>m || map[nx][ny]) break;
if (k%tk[i].v == 0)
bullet[nx][ny][j + k / tk[i].v] = 1;
}
}
}
bool edge(int x, int y)
{
if (x >= 0 && y >= 0 && x <= m && y <= n && map[x][y] == 0)
{
return 1;
}
else {
return 0;
}
}
int BFS()
{
queue<node>q;
node p1;
p1.x = 0;
p1.y = 0;
p1.step = 0;
vis[0][0][0] = 1;
q.push(p1);
while (!q.empty())
{
node p2;
p2 = q.front();
q.pop();
if (p2.step > d)
{
return -1;
}
else if (p2.x == m && p2.y == n)
{
return p2.step;
}
for (int i = 0;i < 5;i++)
{
int next_x = p2.x + dir[i][0];
int next_y = p2.y + dir[i][1];
p1.step = p2.step + 1;
if (edge(next_x, next_y) && vis[next_x][next_y][p1.step] == 0 && bullet[next_x][next_y][p1.step] == 0)
{
p1.x = next_x;
p1.y = next_y;
vis[p1.x][p1.y][p1.step] = 1;
q.push(p1);
}
}
}
}
int main()
{
std::ios::sync_with_stdio(false);
while (cin >> m >> n >> k >> d)
{
char ch;
for (int i = 0;i < k;i++)
{
cin >> ch >> tk[i].t >> tk[i].v >> tk[i].x >> tk[i].y;
if (ch == 'W') tk[i].d = 1;
if (ch == 'N') tk[i].d = 3;
if (ch == 'S') tk[i].d = 4;
if (ch == 'E') tk[i].d = 2;
map[tk[i].x][tk[i].y] = 1;
}
init();
int ans;
memset(vis, 0, sizeof(vis));
memset(map, 0, sizeof(map));
memset(bullet, 0, sizeof(bullet));
ans = BFS();
if (ans) {
cout << ans << endl;
}
else {
cout << "Bad luck!" << endl;
}
}
One of the first users of BIT’s new supercomputer was Chip Diller. He extended his exploration of
powers of 3 to go from 0 to 333 and he explored taking various sums of those numbers.
“This supercomputer is great,” remarked Chip. “I only wish Timothy were here to see these results.”
(Chip moved to a new apartment, once one became available on the third floor of the Lemon Sky
apartments on Third Street.)
Input
The input will consist of at most 100 lines of text, each of which contains a single VeryLongInte-
ger. Each VeryLongInteger will be 100 or fewer characters in length, and will only contain digits (no
VeryLongInteger will be negative).
The final input line will contain a single zero on a line by itself.
Output
Your program should output the sum of the VeryLongIntegers given in the input.
Sample Input
123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0
Sample Output
370370367037037036703703703670
题意：
几个非常大的数据相加求和，输入0时结束。
将每个数据相加并存储在a数组中，并记录它们的长度
#include <iostream>
#include <string>
using namespace std;
void add(int a[], int & lentha, int b[], int & lenthb)
{
int res[10001];
memset(res, 0, sizeof(res));
int i;
int len = (lentha >= lenthb) ? (lentha + 1) : (lenthb + 1);
int ia = 0, ib = 0;
for (i = 1;i < len;i++)
{
if (i + lentha >= len)
{
res[i] += a[ia];
ia++;
}
if (i + lenthb >= len)
{
res[i] += b[ib];
ib++;
}
}
for (i = len - 1;i >= 0;i--)
{
if (res[i] > 9)
{
res[i - 1] += res[i] / 10;
res[i] = res[i] % 10;
}
}
i = 0;
while (res[i] == 0)
{
i++;
}
lentha = len - i;
for (int j = 0;i < len;i++, j++)
{
a[j] = res[i];
}
}
int main()
{
int numa[10001];
int numb[10001];
char s[101];
int lentha = 0, lenthb = 0;
cin >> s;
if (s[0] == 0)
{
cout << "0" << endl;
return 0;
}
int i = 0;
while (s[i] != 0)
{
lentha++;
numa[i] = s[i] - '0';
i++;
}
memset(s, 0, sizeof(s));
cin >> s;
while (strcmp(s, "0") != 0)
{
i = 0;
lenthb = 0;
while (s[i] != 0)
{
lenthb++;
numb[i] = s[i] - '0';
i++;
}
add(numa, lentha, numb,lenthb);
memset(s, 0, sizeof(s));
cin >> s;
}
for (i = 0;i < lentha;i++)
{
cout << numa[i];
}
cout << endl;
return 0;
}
The International Space Station contains many centrifuges in its labs. Each centrifuge will have some
number (C) of chambers each of which can contain 0, 1, or 2 specimens. You are to write a program
which assigns all S specimens to the chambers such that no chamber contains more than 2 specimens
and the following expression for IMBALANCE is minimized.
IMBALANCE =
∑
C
i=1
| CMi − AM |
where:
CMi
is the Chamber Mass of chamber i and is computed by summing the masses of the specimens
assigned to chamber i.
AM is the Average Mass of the chambers and is computed by dividing the sum of the masses of all
specimens by the number of chambers (C).
Input
Input to this program will be a file with multiple sets of input. The first line of each set will contain
two numbers. The first number (1 ≤ C ≤ 5) defines the number of chambers in the centrifuge and the
second number (1 ≤ S ≤ 2C) defines the number of specimens in the input set. The second line of
input will contain S integers representing the masses of the specimens in the set. Each specimen mass
will be between 1 and 1000 and will be delimited by the beginning or end of the line and/or one or
more blanks.
Output
For each input set, you are to print a line specifying the set number (starting with 1) in the format
‘Set #X’ where X is the set number.
The next C lines will contain the chamber number in column 1, a colon in column number 2, and
then the masses of the specimens your program has assigned to that chamber starting in column 4.
The masses in your output should be separated by exactly one blank.
Your program should then print ‘IMBALANCE = X’ on a line by itself where X is the computed
imbalance of your specimen assignments printed to 5 digits of precision to the right of the decimal.
The final line of output for each set should be a blank line. (Follow the sample output format.)
Sample Input
2 3
6 3 8
3 5
51 19 27 14 33
5 9
1 2 3 5 7 11 13 17 19
Sample Output
Set #1
0: 6 3
1: 8
IMBALANCE = 1.00000
Set #2
0: 51
1: 19 27
2: 14 33
IMBALANCE = 6.00000
Set #3
0: 1 17
1: 2 13
2: 3 11
3: 5 7
4: 19
IMBALANCE = 11.60000
题意：......
待续
网友评论