Submission #188852

Source Code Expand

import java.util.Scanner;

public class Main {

    static final int size = 1000;
    static final int limit = 1000;

    static double solve() throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int px = x / d, py = y / d;
        int nlim = Math.min(Math.min(limit, size),n);
        int tlim = Math.min(Math.min(limit, 30),n);
        if ((d > x && x > 0) || (d > y && y > 0) || Math.abs(x) % d > 0 || Math.abs(y) % d > 0 || Math.abs(px)+Math.abs(py) > nlim)
            return 0.0;
        int s = nlim * 2;
        int[][] f = new int[s + 1][s + 1];
        f[nlim][nlim] = 1 << (30 - 1);
        for (int k = 0; k < tlim; k++) {
            int[][] nf = new int[s + 1][s + 1];
            for (int i = 0; i <= s; i++) {
                for (int j = 0; j <= s; j++) {
                    if(f[i][j]==0)continue;
                    int p = f[i][j] >> 2;
                    if (i > 0) nf[i - 1][j] += p;
                    if (i < s) nf[i + 1][j] += p;
                    if (j > 0) nf[i][j - 1] += p;
                    if (j < s) nf[i][j + 1] += p;
                }
            }
            f = nf;
        }
        return (double)f[nlim + px][nlim + py]/(1 << (30 - 1));
    }

    public static void main(String... args) throws Exception {
        System.out.println(solve());
    }
}

Submission Info

Submission Time
Task D - 大ジャンプ
User dolpen
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 1484 Byte
Status WA
Exec Time 1856 ms
Memory 119856 KiB

Judge Result

Set Name part1 part2 All
Score / Max Score 90 / 90 10 / 10 0 / 1
Status
AC × 23
AC × 36
AC × 56
WA × 12
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 473 ms 23344 KiB
sample_02.txt AC 448 ms 23216 KiB
sample_03.txt AC 449 ms 23468 KiB
test_1000_1000000_-500000000_500000000.txt AC 1811 ms 119728 KiB
test_1000_1000000_0_-1000000000.txt AC 1815 ms 119844 KiB
test_1000_1000000_1000000000_0.txt AC 1856 ms 119720 KiB
test_1000_150305_97998860_-32315575.txt AC 1849 ms 119728 KiB
test_1000_1_0_0.txt WA 1831 ms 119728 KiB
test_1000_1_2_0.txt WA 1828 ms 119856 KiB
test_1000_1_2_2.txt WA 1842 ms 119724 KiB
test_1000_3308678_-800700076_-350719868.txt AC 1824 ms 119732 KiB
test_1000_3608549_811923525_689232859.txt AC 1832 ms 119720 KiB
test_1000_3728577_-145414503_-969430020.txt AC 1842 ms 119712 KiB
test_1000_537976_11297496_224335992.txt AC 1822 ms 119728 KiB
test_10_227248639_454497278_0B.txt AC 447 ms 23340 KiB
test_11_692637325_-181424149_-938839075B.txt AC 442 ms 23344 KiB
test_130_95365311_-667557177_-286095933.txt WA 474 ms 31284 KiB
test_131_18204705_-145637640_0.txt WA 475 ms 31276 KiB
test_13_260236679_-780710037_-520473358B.txt AC 450 ms 23472 KiB
test_13_269280357_807841071_269280357B.txt AC 454 ms 23264 KiB
test_13_96859935_0_-581159610B.txt AC 441 ms 23340 KiB
test_16_40374395_-40374395_-565241530B.txt AC 458 ms 23728 KiB
test_1_151403858_0_0AB.txt AC 466 ms 23212 KiB
test_1_1_0_1AB.txt AC 525 ms 23340 KiB
test_1_1_2_0AB.txt AC 447 ms 23336 KiB
test_1_200416616_-430405070_-79858930AB.txt AC 449 ms 23208 KiB
test_1_320861287_0_0AB.txt AC 437 ms 23216 KiB
test_1_445441131_0_0AB.txt AC 441 ms 23216 KiB
test_210_28974130_0_260767170.txt AC 498 ms 33200 KiB
test_217_321156_24407856_22480920.txt AC 495 ms 33312 KiB
test_21_304856339_609712678_914569017B.txt AC 459 ms 24112 KiB
test_26_214390232_-857560928_428780464B.txt AC 453 ms 24240 KiB
test_289_421462830_-487186374_-417635361.txt AC 440 ms 23344 KiB
test_2_91743015_0_183486030AB.txt AC 451 ms 23336 KiB
test_30_10000000_-300000000_0B.txt AC 452 ms 24240 KiB
test_30_10000000_0_300000000B.txt AC 458 ms 24240 KiB
test_30_10000000_150000000_-150000000B.txt AC 452 ms 24236 KiB
test_30_54228128_0_813421920B.txt AC 463 ms 24308 KiB
test_339_4475128_957677392_281933064.txt AC 556 ms 46132 KiB
test_3_165357536_496072608_0AB.txt AC 442 ms 23216 KiB
test_3_357154050_-106436394_768502001AB.txt AC 440 ms 23344 KiB
test_3_721501125_-568833455_353553641AB.txt AC 444 ms 23336 KiB
test_3_893846474_0_0AB.txt AC 447 ms 23344 KiB
test_480_402960_-131767920_-34654560.txt AC 759 ms 55000 KiB
test_4_291388018_-291388018_0AB.txt AC 445 ms 23340 KiB
test_507_3516183_-879045750_-253165176.txt AC 795 ms 56440 KiB
test_515_8606048_-25818144_8606048.txt WA 823 ms 56108 KiB
test_522_2286376_-230923976_-18291008.txt AC 829 ms 55312 KiB
test_5_318547875_955643625_-637095750AB.txt AC 446 ms 23344 KiB
test_5_704387671_-704387671_0AB.txt AC 449 ms 23340 KiB
test_5_82323965_639854915_-688317394AB.txt AC 443 ms 23344 KiB
test_676_198114948_0_792459792.txt WA 1155 ms 65908 KiB
test_688_151937211_-286341114_10198771.txt AC 444 ms 23084 KiB
test_6_187422602_374845204_-374845204AB.txt AC 449 ms 23344 KiB
test_6_346164451_0_0AB.txt AC 443 ms 23336 KiB
test_6_99058019_194123640_-837769837AB.txt AC 445 ms 23216 KiB
test_71_367604060_367604060_0.txt WA 590 ms 26292 KiB
test_752_120973200_0_-725839200.txt WA 1275 ms 78496 KiB
test_772_881340073_0_0.txt WA 1321 ms 81848 KiB
test_777_125719576_-499451637_822057459.txt AC 449 ms 23212 KiB
test_7_166330212_166330212_-332660424AB.txt AC 452 ms 23340 KiB
test_7_89698746_448493730_-179397492AB.txt AC 449 ms 23340 KiB
test_839_166155061_0_-332310122.txt WA 1445 ms 90456 KiB
test_839_923157_923157_564972084.txt AC 1431 ms 90456 KiB
test_849_415705_290993500_0.txt AC 1480 ms 94020 KiB
test_873_418406_2928842_322172620.txt AC 1515 ms 94828 KiB
test_8_10000000_-40000000_-40000000AB.txt AC 454 ms 23472 KiB
test_8_10000000_0_80000000AB.txt AC 455 ms 23336 KiB
test_8_10000000_80000000_0AB.txt AC 449 ms 23344 KiB
test_981_159373724_-637494896_-159373724.txt WA 1796 ms 116244 KiB
test_9_283198156_849594468_849594468B.txt AC 436 ms 23208 KiB