پله بازی (یکی از سوالات acm منطقه)

[siryahya]

با سلام به تمام عاشقان برنامه نویسی
دوستان من یه مشکلی در این مسعله دارم اگه راهنماییم کنید ممنون میشم
دقیق بگم مشکلم در تحلیل مسعله هست (میدونم چی میگه و چی میخاد ولی تو سومین test case که داده الگوریتم من یکی کم میاره ولی تو دوتای دیگه کار میکنه) حالا موندم
عکسهاشم آپ میکنم ببینید

[siryahya]

الگوریتمی که خودم به ذهنم اومد اینه که بیام یه ارایه ی دو سطری بسازم یک سطرش برا خود خانه ها و یکی برای اتصال خانه (نردبان)

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

[vasilopita]

هیچ وقت گوگل رو فراموش نکن ...

/* The first ACM Programming Contest , Iran Region , Tehran Site
Fig: Problem G : ladder
*/
#include<iostream>
using namespace std;
int fact(int n)
{
return ((n>0)?n*fact(n-1) : 1 );
}
int C(int n,int r)
{
return ( (n>=r)?fact(n)/(fact(r)*fact(n-r)) : 0 );
}
int main()
{
int m=0,n=0,k=0,r=0,swap0=0,swap1=0;
int**lad;
while(true)
{
r=0;
cin>>m>>n>>k;
if( m==0 && n==0 && k==0 )break;
lad=new int*[k];
for(int i=0;i<k;i++)
{
lad[i]=new int[2];
}
for(int i=0;i<k;i++)
{
cin>>lad[i][0]>>lad[i][1];
if(lad[i][0]>lad[i][1])
{
swap0=lad[i][0];
lad[i][0]=lad[i][1];
lad[i][1]=swap0;
}
}
for(int i=0;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
if(lad[i][0]>lad[j][0])
{
swap0=lad[i][0];
swap1=lad[i][1];
lad[i][0]=lad[j][0];
lad[i][1]=lad[j][1];
lad[j][0]=swap0;
lad[j][1]=swap1;
}
}
}
for(int i=0;i<=k;i++)
{
r+=C(k,i);
}
for(int i=0;i<k;i++)
{
for(int j=i+1;j<k;j++)
{
if(lad[i][1]>lad[j][0])
{
r-=k-(j-i);
}
}
}
cout<<r<<endl;
}
return 0;
}
/* Released On : http://sstarsprograms.blogfa.com
**This code is copyrighted**
For more information visit our weblog
Send suggestions and questions to mer_benz2002@yahoo.com
*/

[siryahya]

مرسی دوست گرامی
کد خودمو هم شب میزارم. :X

[siryahya]

اینم کد من که میگفتم نوشتم ولی من این تست کیس آخری رو نمیدونم چرا باید 11 بده چون من خودم هم رو کاغذ 10 میارم :متفکر:


#include<iostream>
using namespace std;

void swap1(int *x,int *y)
{
int min,max;
max=(*x>=*y)? *x:*y;
min=(*x<=*y)? *x:*y;

*x=min;
*y=max;
}

void main()
{
int i,m,n,k,num1,num2,arr[2][101],cnt,j,c;

while(true)
{
cin>>m>>n>>k;
if(m==0 && n==0 && k==0) break;

for(i=1;i<=m*n;i++)
{
arr[0][i]=i;
arr[1][i]=-1;
}
for(i=0;i<k;i++)
{
cin>>num1>>num2;
swap1(&num1,&num2);
arr[1][num1]=num2; //min=>num1 max=>num2
}

cnt=1;
for(j=1;j<=m*n;j++)
{
c=0;
for(i=j;i<=m*n;i++)
{
if(arr[1][i]>-1)
{
C++‎;
if(c==1) j=i;

cnt++;
i=arr[1][i];
}
}
}
cout<<cnt<<endl;
}
//yahya_30pp@ymail.com
}