PDA

View Full Version : سوال: Surrounded



V0RTEX
شنبه 11 دی 1389, 22:02 عصر
Surroundedمحدودیت زمان پردازش: 1000 میلی‌ثانیه
محدودیت حافظه: 1024 کیلوبایت

محاصره

چند روز پیش به حاکم کپک‌آباد خبر رسید که همسایه‌ی جنوبی قصد حمله دارد. کپک‌آبادی‌ها به دستور او دیوار بلند و مرتفعی در ضلع جنوبی شهر ساختند و نیروهای خودی در نقاط مختلف شهر مستقر شدند. آن‌ها امروز متوجه شدند که تانک‌های دشمن به پشت دیوار رسیده و از آنجا که قصد نفوذ دارند باید هر چه سریع‌تر نابودشان کرد.

http://ispc.schoolnet.ir/sites/ispc/files/u12/problem8-fig1.png
نخبگان کپکی یک موشک زمین به زمین طراحی کرده‌اند که شعاع انفجار آن با تعیین میزان مواد منفجره، به هر اندازه قابل تنظیم است. آن‌ها می‌خواهند با پرتاب فقط یک موشک وبدون آسیب رساندن به نیروهای خودی بیشترین تانک دشمن را نابود کنند. تعداد این تانک‌ها را به دست آورید.
در نظر داشته باشید که به علت بلندی دیوار قادر به نشانه گرفتن بعد از دیوار نیستند.
تانک‌ها و دیوار شهر قطر ندارند. همچنین دیوار شهر مماس بر تانک‌های دشمن است. اگر موشک مماس بر تانک‌های خودی هم شود باز هم منهدم می‌شوند. ساختار ورودی:

در خط اول دو عدد N (تعداد تانک‌های دشمن) و سپس M (تعداد تانک‌های خودی) داده می‌شود. (۱≤N,M≤۱۰۰۰)
در خط دوم N عدد XBi داده می‌شود که مختصات مکان تانک‌های دشمن است. تانک‌های دشمن روی محور X قرار دارد. پس مؤلفه‌ی Y همگی آنها صفر خواهد بود.
در خط سوم و چهارم در هر خط به ترتیب XRj و YRj داده می‌شود که مختصات مکان نیرو های خودی است.
(-۱۰۸≤XBi, XRj≤۱۰۸, ۰<YRj≤۱۰۸, ۱≤i≤N, ۱≤j≤M) ساختار خروجی:

یک عدد K که بیشترین تعداد ممکن تانک منهدم شده است را در بنویسید.
ورودی نمونه:



7 3
5 17 -5 -4 1 -1 8
7 -2 10
3 1 5

خروجی نمونه:


4
این مسئله مسابقات دانش آموزی بخش پیش رفته بود که تموم شد
http://algorithms.ir/arbiter
حالا می تونید بگید جوابش چی میشه؟
آقای مدیر می بینی که برای کار دانشگاهی و این جور چیز ها نیست پس حذفش نکن بزار یک چیزی یاد بگیرم

V0RTEX
دوشنبه 13 دی 1389, 15:07 عصر
این هم همون اسبه که راه میره!!!



#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;


/*=========Function declare==========*/
int isPossible(int, int);
void printArray(void);
void turn( int, int&, int& );
/*=========Variable declare==========*/
const int rows = 8;
const int hor[rows] = { 2, 1, -1, -2, -2, -1, 1, 2 },
ver[rows] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int hCurrent, vCurrent, move;
int board[rows][rows] = {0};
int accessibility[rows][rows]={
2,3,4,4,4,4,3,2,
3,4,6,6,6,6,4,3,
4,6,8,8,8,8,6,4,
4,6,8,8,8,8,6,4,
4,6,8,8,8,8,6,4,
4,6,8,8,8,8,6,4,
3,4,6,6,6,6,4,3,
2,3,4,4,4,4,3,2};

int main()
{
cout << "X,Y:\n"
cin >> hCurrent;
cout << "\ncolumn: ";
cin >> vCurrent;

board[hCurrent][vCurrent] = 1;
system("CLS");

for ( int counter = 2; counter < 65; counter++ )
{
cout <<"Move : " << counter - 1 << endl;
move = isPossible (hCurrent, vCurrent);
turn( move, hCurrent, vCurrent);
printArray();
}
cout <<endl;
system("pause"):
return 0;
}
void printArray()
{
system("cls");
for ( int i = 0; i < rows; i++)
{
for ( int j = 0; j < rows; j++)
{
if(board[i][j] < 10 )
cout << ' ';
cout << board[i][j] << ' ';
}
cout << endl;
}
// system("pause");

return;
}
int isPossible(int hCurrent, int vCurrent)
{
int movement, bestMove=-1, min = 10, nextrow, nextcol;

for( movement = 7; movement >= 0; movement--)
{

nextrow = hCurrent + ver[movement];
nextcol = vCurrent + hor[movement];

if (nextrow < 0 || nextrow > 7 || nextcol < 0 || nextcol > 7 || board[nextrow][nextcol] != 0)
continue;
if (accessibility[nextrow][nextcol] < min)
{
min = accessibility[nextrow][nextcol];
bestMove = movement;
}
}
return bestMove;
}
void turn ( int move, int& hCurrent, int& vCurrent )
{
static count = 2;
hCurrent += ver[move];
vCurrent += hor[move];

board[hCurrent][vCurrent] = count++;
}

V0RTEX
دوشنبه 13 دی 1389, 15:11 عصر
حالا نوبت شماست که بگید جواب مسئله ی من چی میشه:قلب:

راستی اگه این برنامه خوب بود و دوست داشتید دکمه ی تشکر هم فشار بدید:خجالت:

adminOFsite
دوشنبه 13 دی 1389, 15:24 عصر
boro halesho beber