武林[HDU 1107]
18554 ワード
武林
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1959 Accepted Submission(s): 535
Problem Descriptionは12行12列の四角い武林の世界で、少林、武当、峨嵋の3派の弟子たちが武林を独占するために互いに殺し合っている.武林ワールドの1行目の格子の座標は(1,1)、1行目の2列目の座標は(1,2)......右下の座標は(12,12)です.図:
少林派の弟子はいつも同じ列をひっきりなしに歩いている.先に下へ行って、行き止まりになったら上へ行って、行き止まりになったらまた下へ行って…例えば、(1,1)->(2,1)->(3,1).武当派の弟子はいつも同じ行を歩いている.先に右へ行って、行き止まりになったら左へ、行き止まりになったら右へ…例えば、(2,1)->(2,2)->(2,3)です.峨嵋派の弟子はいつも右下-左上方向に行ったり来たりして、まず右下に行ったり、行き止まりになったら左上に行ったり、行き止まりになったら右下に行ったりしています.例えば、(1,1)->(2,2)->(3,3).峨嵋の弟子が(1,12)か(12,1)にいるなら、もちろん永遠に動かないしかない.
歩くたびに、弟子一人一人が必要で、しかも1つの格子しか移動できません.弟子一人一人には内力、武芸、生命力の3つの属性がある.この3つのプロパティの値範囲は、0以上100以下です.
2人の異なる門派の弟子が同じ格子に入ると、必ず1回の戦闘が発生し、このような状況でこそ戦闘が発生する.(同派の弟子の間ではもちろん互いに殺し合うことはありません;1つの格子の中の3派の弟子はすべて時には、みんなはすべて他の漁夫の利益を恐れて手を出すことができません;多くの同派の弟子も手を携えて敵に対処することはできません.これは武林の中で崇拝するシングルス独闘の精神に反して、人に笑われます)
一度の戦闘の結果、参戦双方の生命力が変化する可能性があります.計算方法は:
戦後生命力=戦前生命力-相手攻撃力
異なる門派の弟子の攻撃力の計算方法は異なる.
少林派攻撃力=(0.5*内力+0.5*武芸)*(戦前生命力+10)/100武当派攻撃力=(0.8*内力+0.2*武芸)*(戦前生命力+10)/100峨嵋派攻撃力=(0.2*内力+0.8*武芸)*(戦前生命力+10)/100
攻撃力の計算過程は浮動小数点演算であり,最終結果は小数点を除いた部分を整列させ,攻撃力が常に整数になるようにした.一度の戦闘が終わると、生命力が0以下の弟子になり、「戦死」と見なされ、武林から消える.2人の異なる門派の弟子が出会った時、戦闘は1回しか起こらなかった.
初期状態では,生命値が0以下の弟子は存在せず,1つの格子に複数の弟子が同時に存在する可能性がある.一連の戦闘は初期状態から勃発する可能性があり、すべての戦闘が終わった後、まだ生きている弟子は次の格子に一斉に歩き始めた.とにかく、戦い続ける-歩く-戦う-歩く......すべての弟子は戦いが終わった後、次の格子まで一斉に歩かなければならない.最初の状態から、Nステップ(N<1000)を経た状態を算出する必要があります.すべての弟子はまず完全部戦闘を行い(もちろん何の戦闘も起こらないかもしれない)、それから一斉に次の格子まで歩いて、これを一歩と言います.すべての弟子の総数は1000を超えない.
Inputの最初の行は、テストデータのグループ数であり、その後、各テストデータのグループである.1行目のデータ群は、歩行ステップ数Nである.次のいくつかの行は、各行が弟子の位置とその各パラメータを説明します.弟子を描く場合、形式は「弟子代号行号列号内力武芸生命力」である.弟子の代号は1つのアルファベットです:“S”は少林派の弟子“W”を代表して武当派の弟子“E”を代表して峨嵋派の弟子を代表します
例えば、W 10 2 10 3 10は10行2列目に武当派の弟子がいて、彼の内力は10で、武芸は3で、生命力は10です.
各テストデータのセットは、終了フラグ行で終わります.終了フラグ行には、1文字'0'しか含まれません.
Outputは各テストデータのセットに対して、あなたの出力は4行であるべきで、前の3行の各行はスペースで区切られた2つの整数で、前の1つはある派の弟子の総数で、後の1つは本派のすべての弟子の生命力の和です.第1行は少林派、第2行は武当派、第3行は峨嵋派を代表することを規定している.4行目は「***」で終わりを表します.
Sample Input21S 1 2 20 20 20W 2 1 20 20 2002S 1 2 20 20 20W 2 1 20 20 20E 12 12 20 20 1000
Sample Output1 201 200 0***1 141 141 100***
SourcePOJ
RecommendEddy
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 1959 Accepted Submission(s): 535
Problem Descriptionは12行12列の四角い武林の世界で、少林、武当、峨嵋の3派の弟子たちが武林を独占するために互いに殺し合っている.武林ワールドの1行目の格子の座標は(1,1)、1行目の2列目の座標は(1,2)......右下の座標は(12,12)です.図:
少林派の弟子はいつも同じ列をひっきりなしに歩いている.先に下へ行って、行き止まりになったら上へ行って、行き止まりになったらまた下へ行って…例えば、(1,1)->(2,1)->(3,1).武当派の弟子はいつも同じ行を歩いている.先に右へ行って、行き止まりになったら左へ、行き止まりになったら右へ…例えば、(2,1)->(2,2)->(2,3)です.峨嵋派の弟子はいつも右下-左上方向に行ったり来たりして、まず右下に行ったり、行き止まりになったら左上に行ったり、行き止まりになったら右下に行ったりしています.例えば、(1,1)->(2,2)->(3,3).峨嵋の弟子が(1,12)か(12,1)にいるなら、もちろん永遠に動かないしかない.
歩くたびに、弟子一人一人が必要で、しかも1つの格子しか移動できません.弟子一人一人には内力、武芸、生命力の3つの属性がある.この3つのプロパティの値範囲は、0以上100以下です.
2人の異なる門派の弟子が同じ格子に入ると、必ず1回の戦闘が発生し、このような状況でこそ戦闘が発生する.(同派の弟子の間ではもちろん互いに殺し合うことはありません;1つの格子の中の3派の弟子はすべて時には、みんなはすべて他の漁夫の利益を恐れて手を出すことができません;多くの同派の弟子も手を携えて敵に対処することはできません.これは武林の中で崇拝するシングルス独闘の精神に反して、人に笑われます)
一度の戦闘の結果、参戦双方の生命力が変化する可能性があります.計算方法は:
戦後生命力=戦前生命力-相手攻撃力
異なる門派の弟子の攻撃力の計算方法は異なる.
少林派攻撃力=(0.5*内力+0.5*武芸)*(戦前生命力+10)/100武当派攻撃力=(0.8*内力+0.2*武芸)*(戦前生命力+10)/100峨嵋派攻撃力=(0.2*内力+0.8*武芸)*(戦前生命力+10)/100
攻撃力の計算過程は浮動小数点演算であり,最終結果は小数点を除いた部分を整列させ,攻撃力が常に整数になるようにした.一度の戦闘が終わると、生命力が0以下の弟子になり、「戦死」と見なされ、武林から消える.2人の異なる門派の弟子が出会った時、戦闘は1回しか起こらなかった.
初期状態では,生命値が0以下の弟子は存在せず,1つの格子に複数の弟子が同時に存在する可能性がある.一連の戦闘は初期状態から勃発する可能性があり、すべての戦闘が終わった後、まだ生きている弟子は次の格子に一斉に歩き始めた.とにかく、戦い続ける-歩く-戦う-歩く......すべての弟子は戦いが終わった後、次の格子まで一斉に歩かなければならない.最初の状態から、Nステップ(N<1000)を経た状態を算出する必要があります.すべての弟子はまず完全部戦闘を行い(もちろん何の戦闘も起こらないかもしれない)、それから一斉に次の格子まで歩いて、これを一歩と言います.すべての弟子の総数は1000を超えない.
Inputの最初の行は、テストデータのグループ数であり、その後、各テストデータのグループである.1行目のデータ群は、歩行ステップ数Nである.次のいくつかの行は、各行が弟子の位置とその各パラメータを説明します.弟子を描く場合、形式は「弟子代号行号列号内力武芸生命力」である.弟子の代号は1つのアルファベットです:“S”は少林派の弟子“W”を代表して武当派の弟子“E”を代表して峨嵋派の弟子を代表します
例えば、W 10 2 10 3 10は10行2列目に武当派の弟子がいて、彼の内力は10で、武芸は3で、生命力は10です.
各テストデータのセットは、終了フラグ行で終わります.終了フラグ行には、1文字'0'しか含まれません.
Outputは各テストデータのセットに対して、あなたの出力は4行であるべきで、前の3行の各行はスペースで区切られた2つの整数で、前の1つはある派の弟子の総数で、後の1つは本派のすべての弟子の生命力の和です.第1行は少林派、第2行は武当派、第3行は峨嵋派を代表することを規定している.4行目は「***」で終わりを表します.
Sample Input21S 1 2 20 20 20W 2 1 20 20 2002S 1 2 20 20 20W 2 1 20 20 20E 12 12 20 20 1000
Sample Output1 201 200 0***1 141 141 100***
SourcePOJ
RecommendEddy
#include<stdio.h>
#include<string.h>
#include<vector>
#include<iostream>
using namespace std;
struct Knight
{
int nl,wy,hp;
int type;
int dx,dy;
};
vector<Knight> G[2][15][15];
void init(int x)
{
int i,j;
for (i=1;i<=12;i++)
for (j=1;j<=12;j++)
G[x][i][j].clear();
}
int CP(int type,int nl,int wy,int hp)
{
double nl_=nl,wy_=wy,hp_=hp;
if (type=='S') return (int)((0.5*nl_+0.5*wy_)*(hp_+10)/100.0);
if (type=='W') return (int)((0.8*nl_+0.2*wy_)*(hp_+10)/100.0);
return (int)((0.2*nl_+0.8*wy_)*(hp_+10)/100.0);
}
int main()
{
int T,N,SK,SH,i,j,k;
char ch;
scanf("%d",&T);
while (T--)
{
init(0);
scanf("%d",&N);
ch=getchar();
ch=getchar();
while (ch!='0')
{
int a,b,c,d,e;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
Knight tmp;
tmp.type=ch;
tmp.nl=c;
tmp.wy=d;
tmp.hp=e;
if (ch=='S')
{
if (a==12) tmp.dx=-1;
else tmp.dx=1;
tmp.dy=0;
}
if (ch=='W')
{
if (b==12) tmp.dy=-1;
else tmp.dy=1;
tmp.dx=0;
}
if (ch=='E')
{
if ((a==12 && b==1) || (a==1 && b==12)) tmp.dx=0;
else if (a==12 || b==12) tmp.dx=-1;
else tmp.dx=1;
tmp.dy=tmp.dx;
}
G[0][a][b].push_back(tmp);
ch=getchar();
ch=getchar();
}
int last=0;
while (N--)
{
for (i=1;i<=12;i++)
for (j=1;j<=12;j++)
if (G[last][i][j].size()==2 && G[last][i][j][0].type!=G[last][i][j][1].type)
{
int sp0=CP(G[last][i][j][0].type,G[last][i][j][0].nl,G[last][i][j][0].wy,G
[last][i][j][0].hp);
int sp1=CP(G[last][i][j][1].type,G[last][i][j][1].nl,G[last][i][j][1].wy,G
[last][i][j][1].hp);
G[last][i][j][0].hp-=sp1;
G[last][i][j][1].hp-=sp0;
}
int oper=1-last;
init(oper);
for (i=1;i<=12;i++)
for (j=1;j<=12;j++)
for (k=0;k<G[last][i][j].size();k++)
if (G[last][i][j][k].hp>0)
{
Knight tmp=G[last][i][j][k];
int x=i+tmp.dx,y=j+tmp.dy;
int xx=x+tmp.dx,yy=j+tmp.dy;
if (xx<1 || xx>12 || yy<1 || yy>12)
{
tmp.dx*=-1;
tmp.dy*=-1;
}
G[oper][x][y].push_back(tmp);
}
last=oper;
}
SK=0,SH=0;
for (i=1;i<=12;i++)
for (j=1;j<=12;j++)
for (k=0;k<G[last][i][j].size();k++)
if (G[last][i][j][k].type=='S')
{
Knight tmp=G[last][i][j][k];
SK++;
SH+=tmp.hp;
}
printf("%d %d
",SK,SH);
SK=0,SH=0;
for (i=1;i<=12;i++)
for (j=1;j<=12;j++)
for (k=0;k<G[last][i][j].size();k++)
if (G[last][i][j][k].type=='W')
{
Knight tmp=G[last][i][j][k];
SK++;
SH+=tmp.hp;
}
printf("%d %d
",SK,SH);
SK=0,SH=0;
for (i=1;i<=12;i++)
for (j=1;j<=12;j++)
for (k=0;k<G[last][i][j].size();k++)
if (G[last][i][j][k].type=='E')
{
Knight tmp=G[last][i][j][k];
SK++;
SH+=tmp.hp;
}
printf("%d %d
",SK,SH);
printf("***
");
}
return 0;
}