Submission #259383
Source Code Expand
#include <bits/stdc++.h>
#include <sys/time.h>
#include <unistd.h>
using namespace std;
#define i64 int64_t
#define rep(i, n) for(i64 i = 0; i < ((i64)(n)); ++i)
#define sz(v) ((i64)((v).size()))
#define bit(n) (((i64)1)<<((i64)(n)))
#define all(v) (v).begin(), (v).end()
template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){}
template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); }
template <class ...Ts> std::ostream& operator<<(std::ostream &os, const std::tuple<Ts...> &t){ os << "("; deploy<0, std::tuple<Ts...>, Ts...>(os, t); os << ")"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.front() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T> std::ostream& operator<<(std::ostream &os, std::priority_queue<T> &q){ auto qq = q; os << "{"; for(; !qq.empty(); qq.pop()){ os << qq.top() << (qq.size() != 1 ? ", " : ""); } os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::pair<T, K> &p){ os << "(" << p.first << ", " << p.second << ")"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
template <class T, class K> std::ostream& operator<<(std::ostream &os, std::unordered_map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "" : ", "); os << "}"; return os; }
#define DEBUG0() { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << std::endl; }
#define DEBUG1(var0) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << std::endl; }
#define DEBUG2(var0, var1) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << std::endl; }
#define DEBUG3(var0, var1, var2) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << std::endl; }
#define DEBUG4(var0, var1, var2, var3) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << std::endl; }
#define DEBUG5(var0, var1, var2, var3, var4) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << std::endl; }
#define DEBUG6(var0, var1, var2, var3, var4, var5) { char buf[1000]; sprintf(buf, "line:%3d | ", __LINE__); std::cout << buf << (#var0) << "=" << (var0) << ", " << (#var1) << "=" << (var1) << ", " << (#var2) << "=" << (var2) << ", " << (#var3) << "=" << (var3) << ", " << (#var4) << "=" << (var4) << ", " << (#var5) << "=" << (var5) << std::endl; }
#define ASSERT(f) { if(!(f)){ DEBUG1("error"); while(true); }}
const i64 MAX = 1050;
double dp[MAX][MAX];
double cal(i64 n, i64 m)
{
if(m < 0 || n < m) return 0.0;
if(n == 0) return 1.0;
double &res = dp[n][m];
if(res != -1) return res;
res = (cal(n - 1, m) + cal(n - 1, m - 1)) * 0.5;
return res;
}
double cal2(i64 m, i64 n)
{
if(n < m) return 0.0;
if((n - m) % 2) return 0.0;
return cal(n, (n - m) / 2);
}
int main()
{
i64 n, d, x, y;
while(cin >> n >> d >> x >> y){
rep(i, MAX)rep(j, MAX) dp[i][j] = -1;
if(abs(x) % d != 0 && abs(y) % d != 0){
cout << 0 << endl;
}else{
double ans = 0.0;
for(i64 vertical = 0; vertical <= n; ++vertical){
double p = cal(n, vertical);
ans += p * cal2(abs(x) / d, vertical) * cal2(abs(y) / d, (n - vertical));
}
printf("%0.20lf\n", ans);
}
}
}
Submission Info
Submission Time |
|
Task |
D - 大ジャンプ |
User |
Komaki |
Language |
C++11 (GCC 4.8.1) |
Score |
101 |
Code Size |
4716 Byte |
Status |
AC |
Exec Time |
53 ms |
Memory |
9504 KB |
Judge Result
Set Name |
part1 |
part2 |
All |
Score / Max Score |
90 / 90 |
10 / 10 |
1 / 1 |
Status |
|
|
|
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 |
35 ms |
9384 KB |
sample_02.txt |
AC |
35 ms |
9384 KB |
sample_03.txt |
AC |
35 ms |
9380 KB |
test_1000_1000000_-500000000_500000000.txt |
AC |
50 ms |
9332 KB |
test_1000_1000000_0_-1000000000.txt |
AC |
50 ms |
9448 KB |
test_1000_1000000_1000000000_0.txt |
AC |
49 ms |
9380 KB |
test_1000_150305_97998860_-32315575.txt |
AC |
47 ms |
9376 KB |
test_1000_1_0_0.txt |
AC |
49 ms |
9504 KB |
test_1000_1_2_0.txt |
AC |
52 ms |
9376 KB |
test_1000_1_2_2.txt |
AC |
53 ms |
9376 KB |
test_1000_3308678_-800700076_-350719868.txt |
AC |
52 ms |
9396 KB |
test_1000_3608549_811923525_689232859.txt |
AC |
50 ms |
9380 KB |
test_1000_3728577_-145414503_-969430020.txt |
AC |
53 ms |
9380 KB |
test_1000_537976_11297496_224335992.txt |
AC |
51 ms |
9380 KB |
test_10_227248639_454497278_0B.txt |
AC |
35 ms |
9380 KB |
test_11_692637325_-181424149_-938839075B.txt |
AC |
36 ms |
9372 KB |
test_130_95365311_-667557177_-286095933.txt |
AC |
35 ms |
9332 KB |
test_131_18204705_-145637640_0.txt |
AC |
36 ms |
9336 KB |
test_13_260236679_-780710037_-520473358B.txt |
AC |
37 ms |
9324 KB |
test_13_269280357_807841071_269280357B.txt |
AC |
37 ms |
9388 KB |
test_13_96859935_0_-581159610B.txt |
AC |
36 ms |
9384 KB |
test_16_40374395_-40374395_-565241530B.txt |
AC |
34 ms |
9372 KB |
test_1_151403858_0_0AB.txt |
AC |
36 ms |
9332 KB |
test_1_1_0_1AB.txt |
AC |
34 ms |
9332 KB |
test_1_1_2_0AB.txt |
AC |
37 ms |
9308 KB |
test_1_200416616_-430405070_-79858930AB.txt |
AC |
35 ms |
9384 KB |
test_1_320861287_0_0AB.txt |
AC |
35 ms |
9336 KB |
test_1_445441131_0_0AB.txt |
AC |
34 ms |
9376 KB |
test_210_28974130_0_260767170.txt |
AC |
35 ms |
9504 KB |
test_217_321156_24407856_22480920.txt |
AC |
36 ms |
9380 KB |
test_21_304856339_609712678_914569017B.txt |
AC |
34 ms |
9332 KB |
test_26_214390232_-857560928_428780464B.txt |
AC |
35 ms |
9384 KB |
test_289_421462830_-487186374_-417635361.txt |
AC |
35 ms |
9376 KB |
test_2_91743015_0_183486030AB.txt |
AC |
35 ms |
9384 KB |
test_30_10000000_-300000000_0B.txt |
AC |
35 ms |
9388 KB |
test_30_10000000_0_300000000B.txt |
AC |
37 ms |
9372 KB |
test_30_10000000_150000000_-150000000B.txt |
AC |
40 ms |
9388 KB |
test_30_54228128_0_813421920B.txt |
AC |
35 ms |
9332 KB |
test_339_4475128_957677392_281933064.txt |
AC |
38 ms |
9388 KB |
test_3_165357536_496072608_0AB.txt |
AC |
37 ms |
9308 KB |
test_3_357154050_-106436394_768502001AB.txt |
AC |
36 ms |
9308 KB |
test_3_721501125_-568833455_353553641AB.txt |
AC |
35 ms |
9328 KB |
test_3_893846474_0_0AB.txt |
AC |
35 ms |
9376 KB |
test_480_402960_-131767920_-34654560.txt |
AC |
40 ms |
9388 KB |
test_4_291388018_-291388018_0AB.txt |
AC |
34 ms |
9388 KB |
test_507_3516183_-879045750_-253165176.txt |
AC |
40 ms |
9384 KB |
test_515_8606048_-25818144_8606048.txt |
AC |
39 ms |
9380 KB |
test_522_2286376_-230923976_-18291008.txt |
AC |
38 ms |
9388 KB |
test_5_318547875_955643625_-637095750AB.txt |
AC |
35 ms |
9384 KB |
test_5_704387671_-704387671_0AB.txt |
AC |
36 ms |
9388 KB |
test_5_82323965_639854915_-688317394AB.txt |
AC |
36 ms |
9376 KB |
test_676_198114948_0_792459792.txt |
AC |
44 ms |
9328 KB |
test_688_151937211_-286341114_10198771.txt |
AC |
35 ms |
9384 KB |
test_6_187422602_374845204_-374845204AB.txt |
AC |
36 ms |
9380 KB |
test_6_346164451_0_0AB.txt |
AC |
34 ms |
9320 KB |
test_6_99058019_194123640_-837769837AB.txt |
AC |
35 ms |
9500 KB |
test_71_367604060_367604060_0.txt |
AC |
37 ms |
9376 KB |
test_752_120973200_0_-725839200.txt |
AC |
42 ms |
9384 KB |
test_772_881340073_0_0.txt |
AC |
46 ms |
9376 KB |
test_777_125719576_-499451637_822057459.txt |
AC |
35 ms |
9380 KB |
test_7_166330212_166330212_-332660424AB.txt |
AC |
35 ms |
9380 KB |
test_7_89698746_448493730_-179397492AB.txt |
AC |
36 ms |
9384 KB |
test_839_166155061_0_-332310122.txt |
AC |
46 ms |
9384 KB |
test_839_923157_923157_564972084.txt |
AC |
46 ms |
9372 KB |
test_849_415705_290993500_0.txt |
AC |
51 ms |
9380 KB |
test_873_418406_2928842_322172620.txt |
AC |
48 ms |
9380 KB |
test_8_10000000_-40000000_-40000000AB.txt |
AC |
34 ms |
9376 KB |
test_8_10000000_0_80000000AB.txt |
AC |
35 ms |
9372 KB |
test_8_10000000_80000000_0AB.txt |
AC |
36 ms |
9328 KB |
test_981_159373724_-637494896_-159373724.txt |
AC |
49 ms |
9440 KB |
test_9_283198156_849594468_849594468B.txt |
AC |
35 ms |
9372 KB |