Submission #19005

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19005	2016-02-17T02:54:49 Z	kriii	로봇 (kriii4_F)	C++14	4 / 100	257 ms	524288 KB

F

#include <stdio.h>

const long long mod = 1000000007;

long long pow(long long a, long long p)
{
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int n,l,m,r;
long long sum;

void go(int a, int x, int y, int d, long long pr)
{
	if (pr == 0) return;
	if (a == n){
		sum = (sum + (x * x + y * y) * pr % mod + mod) % mod;
	}
	else{
		go(a+1,x+dx[d],y+dy[d],d,pr*m%mod);
		go(a+1,x+dx[(d+1)%4],y+dy[(d+1)%4],(d+1)%4,pr*l%mod);
		go(a+1,x+dx[(d+3)%4],y+dy[(d+3)%4],(d+3)%4,pr*r%mod);
	}
}

int main()
{
	while (~scanf ("%d %d %d %d",&n,&l,&m,&r)){
		sum = 0;
		go(0,0,0,0,1);

		long long inv = pow(l+m+r,-1);
		for (int i=0;i<n;i++){
			sum = sum * inv % mod;
		}
		printf ("%lld\n",sum);
	}

	return 0;
}

Subtask #1

4.0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1084 KB	Output is correct
2	Correct	0 ms	1084 KB	Output is correct
3	Correct	0 ms	1084 KB	Output is correct
4	Correct	0 ms	1084 KB	Output is correct
5	Correct	0 ms	1084 KB	Output is correct
6	Correct	0 ms	1084 KB	Output is correct
7	Correct	10 ms	1084 KB	Output is correct
8	Correct	0 ms	1084 KB	Output is correct
9	Correct	0 ms	1084 KB	Output is correct
10	Correct	0 ms	1084 KB	Output is correct
11	Correct	0 ms	1084 KB	Output is correct
12	Correct	0 ms	1084 KB	Output is correct
13	Correct	0 ms	1084 KB	Output is correct
14	Correct	0 ms	1084 KB	Output is correct
15	Correct	0 ms	1084 KB	Output is correct
16	Correct	0 ms	1084 KB	Output is correct
17	Correct	0 ms	1084 KB	Output is correct
18	Correct	0 ms	1084 KB	Output is correct
19	Correct	0 ms	1084 KB	Output is correct
20	Correct	0 ms	1084 KB	Output is correct
21	Correct	0 ms	1084 KB	Output is correct
22	Correct	0 ms	1084 KB	Output is correct
23	Correct	0 ms	1084 KB	Output is correct
24	Correct	0 ms	1084 KB	Output is correct
25	Correct	0 ms	1084 KB	Output is correct
26	Correct	0 ms	1084 KB	Output is correct
27	Correct	0 ms	1084 KB	Output is correct
28	Correct	3 ms	1084 KB	Output is correct
29	Correct	86 ms	1084 KB	Output is correct
30	Correct	257 ms	1084 KB	Output is correct

Subtask #2

0.0 / 96.0

#	Verdict	Execution time	Memory	Grader output
1	Memory limit exceeded	143 ms	524288 KB	Memory limit exceeded
2	Halted	0 ms	0 KB	-