Army Problem – Dynamic Programming Solutions

This is a C++ Program that Solves Army Problem using Dynamic Programming technique.

Problem Description

The Berland Armed Forces System consists of n ranks that are numbered using natural numbers from 1 to n, where 1 is the lowest rank and n is the highest rank.

One needs exactly d[i] years to rise from rank i to rank i + 1. Reaching a certain rank i having not reached all the previous i - 1 ranks is impossible.

Vasya has just reached a new rank of a, but he dreams of holding the rank of b. Find for how many more years Vasya should serve in the army until he can finally realize his dream.

Problem Solution

In this problem, we will simply find total number of years required to reach rank a from rank 1, then total number of years required to rise from rank 1 to rank b. For this we will maintain a commulative array sum, where sum[i]=total number of years required to rise from rank 1 to rank i. Once we have initialized this array, the answer to our question will be the difference of these two values.

Expected Input and Output

Case-1:

advertisement
advertisement
Number of ranks in the army= 3
Number of years required to rise from previous rank to next rank for every rank= {5, 6}
Initial rank=1  
Targer rank=2
Number of years required to rise from rank 1 to rank 2 are = 5
Program/Source Code

Here is source code of the C++ Program to Solve Army Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int i,j;
  8.     int n;
  9.     int x,y;
  10.     cout<<"Enter the number of ranks in the army ";
  11.     cin>>n;
  12.     vector<int> sum(n);
  13.     sum[0]=0;
  14.  
  15.     cout<<"Enter the number of years required to rise from previous rank to next rank for every rank"<<endl;
  16.     for(i=0;i<n-1;i++)
  17.     {
  18.         cin>>x;
  19.         sum[i+1]=sum[i]+x;
  20.     }
  21.  
  22.     cout<<"Enter the initial rank  ";
  23.     cin>>x;
  24.     cout<<"Enter the targer rank ";
  25.     cin>>y;
  26.     cout<<"Number of years required to rise from rank "<<x<<" to rank "<<y<<"are"<<endl;
  27.     cout<<sum[y-1]-sum[x-1]<<endl;
  28.  
  29.     return 0;
  30. }
Program Explanation

In the main function, we ask user to input the values for number of ranks, and years required for transition. We prepare a commulative array sum[i] based on this data. Then we ask the ask the user for its initial and final rank. Then, the corresponding result is displayed.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Runtime Test Cases
 
Case-1:
$ g++ army.cpp
$ ./a.out
Enter the number of ranks in the army 3
Enter the number of years required to rise from previous rank to next rank for every rank
5 6
Enter the initial rank  1  
Enter the targer rank 2
Number of years required to rise from rank 1 to rank 2are
5

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

advertisement

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.