Submission #188109


Source Code Expand

import java.io.*;
import java.math.*;
import java.util.*;


public class Main {

	public static void main(String[] args) throws Exception {
		new Main().solve();
	}


	void solve() throws Exception {
		FastScanner in = new FastScanner(System.in);

		int N = in.nextInt();
		int D = in.nextInt();
		int X = in.nextInt();
		int Y = in.nextInt();


		int r0 = X / D;
		int d0 = Y / D;
		if (r0 * D != X || d0 * D != Y) {
			System.out.println(0);
			return;
		}


		BigDecimal ret = bd(0);
		for (int rr = 0; rr <= N; rr++) {
			int ll = rr - r0;
			for (int dd = 0; dd <= N; dd++) {
				int uu = dd - d0;

				if (rr + ll + uu + dd == N && 0 <= ll && ll <= N && 0 <= uu && uu <= N) {
					// ok
					BigDecimal p1 = f(N);
					BigDecimal p2 = bd(4).pow(N).multiply(f(rr)).multiply(f(ll)).multiply(f(dd)).multiply(f(uu));

					BigDecimal p = p1.divide(p2, MathContext.DECIMAL128);

					ret = ret.add(p);
				}
			}
		}
		System.out.println(ret.doubleValue());
	}

	BigDecimal bd(double a) {
		return BigDecimal.valueOf(a);
	}

	BigDecimal[] memo = new BigDecimal[2000];
	BigDecimal f(int n) {
		if (memo[n] != null) {
			return memo[n];
		} else {
			if (n == 0) {
				return memo[n] = bd(1);
			} else {
				return memo[n] = f(n - 1).multiply(bd(n));
			}
		}
	}
	class FastScanner {

		private InputStream _stream;
		private byte[] _buf = new byte[1024];
		private int _curChar;
		private int _numChars;
		private StringBuilder _sb = new StringBuilder();

		FastScanner(InputStream stream) {
			this._stream = stream;
		}

		public int read() {
			if (_numChars == -1) throw new InputMismatchException();
			if (_curChar >= _numChars) {
				_curChar = 0;
				try {
					_numChars = _stream.read(_buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (_numChars <= 0) return -1;
			}
			return _buf[_curChar++];
		}

		public String next() {
			int c = read();
			while (isWhitespace(c)) {
				c = read();
			}
			_sb.setLength(0);
			do {
				_sb.appendCodePoint(c);
				c = read();
			} while (!isWhitespace(c));
			return _sb.toString();
		}

		public int nextInt() {
			return (int) nextLong();
		}
		public long nextLong() {
			int c = read();
			while (isWhitespace(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9') throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isWhitespace(c));
			return res * sgn;
		}

		public boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}
}
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//

Submission Info

Submission Time
Task D - 大ジャンプ
User ixxa
Language Java (OpenJDK 1.7.0)
Score 101
Code Size 2852 Byte
Status AC
Exec Time 1278 ms
Memory 45756 KB

Judge Result

Set Name part1 part2 All
Score / Max Score 90 / 90 10 / 10 1 / 1
Status
AC × 23
AC × 36
AC × 68
Set Name Test Cases
part1 test_1_151403858_0_0AB.txt, test_1_1_0_1AB.txt, test_1_1_2_0AB.txt, test_1_200416616_-430405070_-79858930AB.txt, test_1_320861287_0_0AB.txt, test_1_445441131_0_0AB.txt, test_2_91743015_0_183486030AB.txt, test_3_165357536_496072608_0AB.txt, test_3_357154050_-106436394_768502001AB.txt, test_3_721501125_-568833455_353553641AB.txt, test_3_893846474_0_0AB.txt, test_4_291388018_-291388018_0AB.txt, test_5_318547875_955643625_-637095750AB.txt, test_5_704387671_-704387671_0AB.txt, test_5_82323965_639854915_-688317394AB.txt, test_6_187422602_374845204_-374845204AB.txt, test_6_346164451_0_0AB.txt, test_6_99058019_194123640_-837769837AB.txt, test_7_166330212_166330212_-332660424AB.txt, test_7_89698746_448493730_-179397492AB.txt, test_8_10000000_-40000000_-40000000AB.txt, test_8_10000000_0_80000000AB.txt, test_8_10000000_80000000_0AB.txt
part2 test_10_227248639_454497278_0B.txt, test_11_692637325_-181424149_-938839075B.txt, test_13_260236679_-780710037_-520473358B.txt, test_13_269280357_807841071_269280357B.txt, test_13_96859935_0_-581159610B.txt, test_16_40374395_-40374395_-565241530B.txt, test_1_151403858_0_0AB.txt, test_1_1_0_1AB.txt, test_1_1_2_0AB.txt, test_1_200416616_-430405070_-79858930AB.txt, test_1_320861287_0_0AB.txt, test_1_445441131_0_0AB.txt, test_21_304856339_609712678_914569017B.txt, test_26_214390232_-857560928_428780464B.txt, test_2_91743015_0_183486030AB.txt, test_30_10000000_-300000000_0B.txt, test_30_10000000_0_300000000B.txt, test_30_10000000_150000000_-150000000B.txt, test_30_54228128_0_813421920B.txt, test_3_165357536_496072608_0AB.txt, test_3_357154050_-106436394_768502001AB.txt, test_3_721501125_-568833455_353553641AB.txt, test_3_893846474_0_0AB.txt, test_4_291388018_-291388018_0AB.txt, test_5_318547875_955643625_-637095750AB.txt, test_5_704387671_-704387671_0AB.txt, test_5_82323965_639854915_-688317394AB.txt, test_6_187422602_374845204_-374845204AB.txt, test_6_346164451_0_0AB.txt, test_6_99058019_194123640_-837769837AB.txt, test_7_166330212_166330212_-332660424AB.txt, test_7_89698746_448493730_-179397492AB.txt, test_8_10000000_-40000000_-40000000AB.txt, test_8_10000000_0_80000000AB.txt, test_8_10000000_80000000_0AB.txt, test_9_283198156_849594468_849594468B.txt
All test_1000_1000000_-500000000_500000000.txt, test_1000_1000000_0_-1000000000.txt, test_1000_1000000_1000000000_0.txt, test_1000_150305_97998860_-32315575.txt, test_1000_1_0_0.txt, test_1000_1_2_0.txt, test_1000_1_2_2.txt, test_1000_3308678_-800700076_-350719868.txt, test_1000_3608549_811923525_689232859.txt, test_1000_3728577_-145414503_-969430020.txt, test_1000_537976_11297496_224335992.txt, test_10_227248639_454497278_0B.txt, test_11_692637325_-181424149_-938839075B.txt, test_130_95365311_-667557177_-286095933.txt, test_131_18204705_-145637640_0.txt, test_13_260236679_-780710037_-520473358B.txt, test_13_269280357_807841071_269280357B.txt, test_13_96859935_0_-581159610B.txt, test_16_40374395_-40374395_-565241530B.txt, test_1_151403858_0_0AB.txt, test_1_1_0_1AB.txt, test_1_1_2_0AB.txt, test_1_200416616_-430405070_-79858930AB.txt, test_1_320861287_0_0AB.txt, test_1_445441131_0_0AB.txt, test_210_28974130_0_260767170.txt, test_217_321156_24407856_22480920.txt, test_21_304856339_609712678_914569017B.txt, test_26_214390232_-857560928_428780464B.txt, test_289_421462830_-487186374_-417635361.txt, test_2_91743015_0_183486030AB.txt, test_30_10000000_-300000000_0B.txt, test_30_10000000_0_300000000B.txt, test_30_10000000_150000000_-150000000B.txt, test_30_54228128_0_813421920B.txt, test_339_4475128_957677392_281933064.txt, test_3_165357536_496072608_0AB.txt, test_3_357154050_-106436394_768502001AB.txt, test_3_721501125_-568833455_353553641AB.txt, test_3_893846474_0_0AB.txt, test_480_402960_-131767920_-34654560.txt, test_4_291388018_-291388018_0AB.txt, test_507_3516183_-879045750_-253165176.txt, test_515_8606048_-25818144_8606048.txt, test_522_2286376_-230923976_-18291008.txt, test_5_318547875_955643625_-637095750AB.txt, test_5_704387671_-704387671_0AB.txt, test_5_82323965_639854915_-688317394AB.txt, test_676_198114948_0_792459792.txt, test_688_151937211_-286341114_10198771.txt, test_6_187422602_374845204_-374845204AB.txt, test_6_346164451_0_0AB.txt, test_6_99058019_194123640_-837769837AB.txt, test_71_367604060_367604060_0.txt, test_752_120973200_0_-725839200.txt, test_772_881340073_0_0.txt, test_777_125719576_-499451637_822057459.txt, test_7_166330212_166330212_-332660424AB.txt, test_7_89698746_448493730_-179397492AB.txt, test_839_166155061_0_-332310122.txt, test_839_923157_923157_564972084.txt, test_849_415705_290993500_0.txt, test_873_418406_2928842_322172620.txt, test_8_10000000_-40000000_-40000000AB.txt, test_8_10000000_0_80000000AB.txt, test_8_10000000_80000000_0AB.txt, test_981_159373724_-637494896_-159373724.txt, test_9_283198156_849594468_849594468B.txt
Case Name Status Exec Time Memory
sample_01.txt AC 497 ms 21220 KB
sample_02.txt AC 375 ms 20660 KB
sample_03.txt AC 399 ms 21440 KB
test_1000_1000000_-500000000_500000000.txt AC 490 ms 28244 KB
test_1000_1000000_0_-1000000000.txt AC 519 ms 28112 KB
test_1000_1000000_1000000000_0.txt AC 504 ms 25460 KB
test_1000_150305_97998860_-32315575.txt AC 416 ms 22084 KB
test_1000_1_0_0.txt AC 1250 ms 36364 KB
test_1000_1_2_0.txt AC 1278 ms 45488 KB
test_1000_1_2_2.txt AC 1271 ms 45248 KB
test_1000_3308678_-800700076_-350719868.txt AC 1006 ms 45756 KB
test_1000_3608549_811923525_689232859.txt AC 958 ms 35652 KB
test_1000_3728577_-145414503_-969430020.txt AC 412 ms 22060 KB
test_1000_537976_11297496_224335992.txt AC 939 ms 35428 KB
test_10_227248639_454497278_0B.txt AC 393 ms 21444 KB
test_11_692637325_-181424149_-938839075B.txt AC 372 ms 20732 KB
test_130_95365311_-667557177_-286095933.txt AC 452 ms 26988 KB
test_131_18204705_-145637640_0.txt AC 388 ms 21356 KB
test_13_260236679_-780710037_-520473358B.txt AC 394 ms 16852 KB
test_13_269280357_807841071_269280357B.txt AC 347 ms 17736 KB
test_13_96859935_0_-581159610B.txt AC 348 ms 17648 KB
test_16_40374395_-40374395_-565241530B.txt AC 351 ms 17772 KB
test_1_151403858_0_0AB.txt AC 340 ms 17772 KB
test_1_1_0_1AB.txt AC 365 ms 17880 KB
test_1_1_2_0AB.txt AC 351 ms 17772 KB
test_1_200416616_-430405070_-79858930AB.txt AC 366 ms 17476 KB
test_1_320861287_0_0AB.txt AC 360 ms 17776 KB
test_1_445441131_0_0AB.txt AC 345 ms 17732 KB
test_210_28974130_0_260767170.txt AC 357 ms 18076 KB
test_217_321156_24407856_22480920.txt AC 347 ms 18088 KB
test_21_304856339_609712678_914569017B.txt AC 353 ms 18032 KB
test_26_214390232_-857560928_428780464B.txt AC 352 ms 18156 KB
test_289_421462830_-487186374_-417635361.txt AC 336 ms 17392 KB
test_2_91743015_0_183486030AB.txt AC 349 ms 17996 KB
test_30_10000000_-300000000_0B.txt AC 347 ms 18156 KB
test_30_10000000_0_300000000B.txt AC 351 ms 18032 KB
test_30_10000000_150000000_-150000000B.txt AC 353 ms 18164 KB
test_30_54228128_0_813421920B.txt AC 341 ms 17780 KB
test_339_4475128_957677392_281933064.txt AC 450 ms 24140 KB
test_3_165357536_496072608_0AB.txt AC 353 ms 17908 KB
test_3_357154050_-106436394_768502001AB.txt AC 338 ms 17384 KB
test_3_721501125_-568833455_353553641AB.txt AC 343 ms 17388 KB
test_3_893846474_0_0AB.txt AC 347 ms 17652 KB
test_480_402960_-131767920_-34654560.txt AC 376 ms 18732 KB
test_4_291388018_-291388018_0AB.txt AC 345 ms 17640 KB
test_507_3516183_-879045750_-253165176.txt AC 372 ms 18796 KB
test_515_8606048_-25818144_8606048.txt AC 370 ms 18804 KB
test_522_2286376_-230923976_-18291008.txt AC 368 ms 18796 KB
test_5_318547875_955643625_-637095750AB.txt AC 356 ms 17868 KB
test_5_704387671_-704387671_0AB.txt AC 361 ms 17904 KB
test_5_82323965_639854915_-688317394AB.txt AC 348 ms 17308 KB
test_676_198114948_0_792459792.txt AC 736 ms 37840 KB
test_688_151937211_-286341114_10198771.txt AC 337 ms 17396 KB
test_6_187422602_374845204_-374845204AB.txt AC 350 ms 17860 KB
test_6_346164451_0_0AB.txt AC 349 ms 17928 KB
test_6_99058019_194123640_-837769837AB.txt AC 347 ms 17300 KB
test_71_367604060_367604060_0.txt AC 367 ms 19444 KB
test_752_120973200_0_-725839200.txt AC 828 ms 38452 KB
test_772_881340073_0_0.txt AC 894 ms 40000 KB
test_777_125719576_-499451637_822057459.txt AC 341 ms 17396 KB
test_7_166330212_166330212_-332660424AB.txt AC 352 ms 17936 KB
test_7_89698746_448493730_-179397492AB.txt AC 351 ms 18032 KB
test_839_166155061_0_-332310122.txt AC 365 ms 18804 KB
test_839_923157_923157_564972084.txt AC 662 ms 34576 KB
test_849_415705_290993500_0.txt AC 368 ms 18796 KB
test_873_418406_2928842_322172620.txt AC 544 ms 26484 KB
test_8_10000000_-40000000_-40000000AB.txt AC 353 ms 18040 KB
test_8_10000000_0_80000000AB.txt AC 356 ms 18024 KB
test_8_10000000_80000000_0AB.txt AC 361 ms 18036 KB
test_981_159373724_-637494896_-159373724.txt AC 1162 ms 42204 KB
test_9_283198156_849594468_849594468B.txt AC 350 ms 17736 KB