QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#672094#7781. Sheep Eat WolvesKOH-#WA 0ms3768kbC++141.3kb2024-10-24 15:36:022024-10-24 15:36:03

Judging History

你现在查看的是最新测评结果

  • [2024-10-24 15:36:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3768kb
  • [2024-10-24 15:36:02]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
template <typename T>
inline void read(T &x){
	x=0;char ch=getchar();bool f=false;
	while(!isdigit(ch))	f|=ch=='-',ch=getchar();
	while(isdigit(ch))	x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	x=f?-x:x;return;
} 
template <typename T>
inline void print(T x){
	if(x<0)	putchar('-'),x=-x;
	if(x>9)	print(x/10);
	putchar(x%10^48);return; 
}
#define ll long long 
const int N=103;
int f[2][N][N];
int x,y,p,q;
void Dfs(int now,int cx,int cy){
//	cout<<now<<" "<<cx<<" "<<cy<<" "<<f[now][cx][cy]<<"???\n";
	if(now==0){
		int tx=x-cx,ty=y-cy; 
		for(int i=0;i<=p&&i<=cx;++i){
			for(int j=0;i+j<=p&&j<=cy;++j){
				if(cx-i-(cy-j)<=p){
					if(f[0][cx][cy]+1<f[1][cx-i][cy-j]){
						f[1][cx-i][cy-j]=f[0][cx][cy]+1;
						Dfs(1,cx-i,cy-j);
					}			
				}
			}
		}
	}
	else{
		int tx=x-cx,ty=y-cy;
		for(int i=0;i<=p&&i<=tx;++i){
			for(int j=0;i+j<=p&&j<=ty;++j){
				if(tx-i-(ty-j)<=p){
					if(f[1][cx][cy]+1<f[0][cx+i][cy+j]){
						f[0][cx+i][cy+j]=f[1][cx][cy]+1;
						Dfs(0,cx+i,cy+j);
					}
				}
			}
		}
	}
}
int main(){
	read(y),read(x),read(p),read(q);
	memset(f,0x3f3f3f3f,sizeof(f));
	f[0][x][y]=0;
	Dfs(0,x,y);
	int minn=0x3f3f3f3f;
	for(int i=0;i<=x;++i)	minn=min(minn,f[1][i][0]);
	if(minn!=0x3f3f3f3f) print(minn);
	else puts("-1");
	return 0;
}
	

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3768kb

input:

4 4 3 1

output:

3

result:

ok 1 number(s): "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

3 5 2 0

output:

5

result:

ok 1 number(s): "5"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3700kb

input:

2 5 1 1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

1 1 1 0

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3684kb

input:

3 3 1 1

output:

9

result:

wrong answer 1st numbers differ - expected: '7', found: '9'