Advertisement
Guest User

Untitled

a guest
Aug 10th, 2014
400
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.34 KB | None | 0 0
  1. /*
  2. Author: Md. Fahim Mohiuddin
  3. AUST CSE 32 Batch
  4.  
  5. Problem: CodeForces - 118D - Caesar's Legions
  6. */
  7.  
  8. //{ ---------- C headers
  9. # include <cstdio>
  10. # include <cstring>
  11. # include <cmath>
  12. # include <cstdlib>
  13. # include <cctype>
  14. //}
  15.  
  16. //{ ---------- C++ headers
  17. # include <iostream>
  18. # include <string>
  19. # include <algorithm>
  20. # include <vector>
  21. # include <queue>
  22. # include <stack>
  23. # include <map>
  24. # include <sstream>
  25. # include <set>
  26. //}
  27. using namespace std;
  28.  
  29. //{ ---------- Movements
  30. /*int dx[]={1,-1,0,0}, dy[]={0,0,1,-1};*/ // 4 way movement
  31. /*int dx[]={1,0,-1,0,1,-1,1,-1}, dy[]={0,1,0,-1,1,1,-1,-1};*/ // 8 way movement
  32. //}
  33.  
  34. long long n[2], k[2];
  35. long long dp[2][101][101];
  36. long long call( long long clr, long long a, long long b ) {
  37.     if( a+b == n[0]+n[1] ) return 1;
  38.     if( dp[clr][a][b] != -1 ) return dp[clr][a][b];
  39.  
  40.     long long way=0;
  41.     long long lim = min( k[clr], n[clr]-( !clr? a:b ) );
  42.     for( long long i=1; i<=lim; i++ ) {
  43.         way += !clr? call( 1-clr, a+i, b ): call( 1-clr, a, b+i );
  44.         way %= 100000000;
  45.     }
  46.     return dp[clr][a][b] = way;
  47. }
  48.  
  49. int main() {
  50. //    freopen("input.txt","r",stdin);
  51. //    freopen("output.txt","w",stdout);
  52.  
  53.     cin >> n[0] >> n[1] >> k[0] >> k[1];
  54.     memset( dp, -1, sizeof dp );
  55.     cout << (call(0,0,0) + call(1,0,0))%100000000 << endl;
  56.  
  57.     return 0;
  58. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement