118D.md (1726B)
1 Source: https://codeforces.com/problemset/problem/118/D 2 3 D. Caesar's Legions 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Gaius Julius Caesar, a famous general, loved to line up his soldiers. Overall the army had *n*1 footmen and *n*2 horsemen. Caesar thought that an arrangement is not beautiful if somewhere in the line there are strictly more that *k*1 footmen standing successively one after another, or there are strictly more than *k*2 horsemen standing successively one after another. Find the number of beautiful arrangements of the soldiers. 22 23 Note that all *n*1 + *n*2 warriors should be present at each arrangement. All footmen are considered indistinguishable among themselves. Similarly, all horsemen are considered indistinguishable among themselves. 24 25 Input 26 27 The only line contains four space-separated integers *n*1, *n*2, *k*1, *k*2 (1 ≤ *n*1, *n*2 ≤ 100, 1 ≤ *k*1, *k*2 ≤ 10) which represent how many footmen and horsemen there are and the largest acceptable number of footmen and horsemen standing in succession, correspondingly. 28 29 Output 30 31 Print the number of beautiful arrangements of the army modulo 100000000 (108). That is, print the number of such ways to line up the soldiers, that no more than *k*1 footmen stand successively, and no more than *k*2 horsemen stand successively. 32 33 Examples 34 35 Input 36 37 ``` 38 2 1 1 10 39 ``` 40 41 Output 42 43 ``` 44 1 45 ``` 46 47 Input 48 49 ``` 50 2 3 1 2 51 ``` 52 53 Output 54 55 ``` 56 5 57 ``` 58 59 Input 60 61 ``` 62 2 4 1 1 63 ``` 64 65 Output 66 67 ``` 68 0 69 ``` 70 71 Note 72 73 Let's mark a footman as 1, and a horseman as 2. 74 75 In the first sample the only beautiful line-up is: 121 76 77 In the second sample 5 beautiful line-ups exist: 12122, 12212, 21212, 21221, 22121