種子論壇 | 高雄市資訊培育協會學員討論區

標題: ＝＝阿里不達轟＝＝ [打印本頁]

作者: p17johnny 時間: 2011-11-12 20:02 標題: ＝＝阿里不達轟＝＝

解碼器 Download

作者: p17johnny 時間: 2011-11-12 20:22

求解

作者: ray 時間: 2011-11-30 17:53

/**********************************************************************************/
/*  Problem: d591 "D. 阿里不達轟!!" from 2009 NPSC 國中組初賽          */
/*  Language: CPP (1559 Bytes)                                                 */
/*  Result: AC(328ms, 444KB) judge by this@ZeroJudge                            */
/*  Author: ray0410 at 2011-11-12 21:19:24                                     */
/**********************************************************************************/

#include<iostream>
#include<math.h>
#include<stack>
using namespace std;
struct role
{
int x;
int y;
int r;
};
stack<int>ans;
int bombs,enermys;
role bomb[15],enermy[9];
int hittable[15][9];

void fire(int bombno,int use,int enermylife,int num)
{
   if(use)
   {
   for(int i=0;i<enermys;i++)
   {
      enermylife &= (int)(pow(2,enermys)-1-(pow(2,i)*hittable[bombno][i]));
   }
   }
   bombno++;
   num += use;

   if(enermylife == 0)
   {
   ans.push(num);
   }
   if(enermylife > 0 && bombno < bombs)
   {
   fire(bombno,0,enermylife,num);
   fire(bombno,1,enermylife,num);
   }
}

int main()
{
int total;
cin >> total;
while(total--)
{
   int i,j,enermylife;
   cin >> bombs >> enermys;
   for(i=0;i<bombs;i++)
      cin >> bomb[i].x >> bomb[i].y >> bomb[i].r;
   for(j=0;j<enermys;j++)
      cin >> enermy[j].x >> enermy[j].y >> enermy[j].r;

   for(i=0;i<bombs;i++)
      for(j=0;j<enermys;j++)
      hittable[i][j]=(sqrt(pow(enermy[j].x-bomb[i].x,2)+pow(enermy[j].y-bomb[i].y,2)) <= enermy[j].r+bomb[i].r);

   enermylife = (int)pow(2,enermys)-1;
   fire(0,0,enermylife,0);
   fire(0,1,enermylife,0);

   int answer = 9999;
   while(ans.size())
   {
      answer = min(ans.top(),answer);
      ans.pop();
   }
   if(answer == 9999)
      cout << "Impossible" << endl;
   else
      cout << answer << endl;
}
return 0;
}

歡迎光臨種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/)