Exact Capacity Booking
Fed up of overbooking in airlines industry, the government has ordered that airlines cannot book more than the capacity C of an aeroplane. To optimize their revenue, the airlines must confirm booking exactly for C passengers only. The ticket may be booked for just a single passenger or for a group of passengers ranging from 2 to N. (Like 2 tickers for a couple going on a honey moon or 4 tickets for a family of husband, wife and two kids).
Given the capacity C and N, print the number of ways W to fill the C seats using ticket bookings with single passengers or group booking count of 2 to N.
Input Format:
The first line contains the values of C.
The second line contains the values of N.
Given the capacity C and N, print the number of ways W to fill the C seats using ticket bookings with single passengers or group booking count of 2 to N.
Input Format:
The first line contains the values of C.
The second line contains the values of N.
Output Format:
The first line contains the number of ways W.
Boundary Conditions:
1 <= C <= 500
2 <= N <= 10
Example Input/Output 1:
Input:
5
4
Output:
6
Explanation:
The ways to fill 5 seats using booking count of 1,2,3,4 are (1,1,1,1,1) (1,1,1,2) (1,2,2) (1,1,3) (1,4) (2,3)
Please note that 1,1,3 is same as the combination of 1,3,1 or 3,1,1 and hence not counted as additional ways.
Code:The first line contains the number of ways W.
Boundary Conditions:
1 <= C <= 500
2 <= N <= 10
Example Input/Output 1:
Input:
5
4
Output:
6
Explanation:
The ways to fill 5 seats using booking count of 1,2,3,4 are (1,1,1,1,1) (1,1,1,2) (1,2,2) (1,1,3) (1,4) (2,3)
Please note that 1,1,3 is same as the combination of 1,3,1 or 3,1,1 and hence not counted as additional ways.
#include
<iostream>
using
namespace std;
int
main(int argc, char** argv)
{
int
i,j,n,m;
cin>>n>>m;
int
a[n+1] = {0};
a[0]
= 1;
for(i=1;i<m+1;i++)
for(j=i;j<n+1;j++)
a[j] += a[j-i];
cout<<a[n];
}
Please do comment If u have any Queries!
//RMK
ReplyDeleteimport java.util.*;
public class Hello {
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int C = sc.nextInt();
int N = sc.nextInt();
ArrayList> results = new ArrayList>();
ArrayList list ;
for(int i = 1;i<=N;i++)
{
list = new ArrayList();
compute(results,list,0,i,C,true);
}
System.out.println(results.size());
}
public static void compute(ArrayList> results,ArrayList list,int sum,int last,int target,boolean isFirst)
{
if(sum==target)
{
results.add(list);
return;
}
while(sum+last>target)
{
last--;
}
int less = last-1;
if(!isFirst&&less>0 && less+last < target)
{
ArrayList copy = new ArrayList(list);
compute(results,copy,sum,less,target,false);
}
sum = sum + last;
list.add(last);
compute(results,list,sum,last,target,false);
}
}
with one test case time limit fails
//ONLY 5 testcases passing remaining 3 getting failed
ReplyDelete#include
#include
#include
#include
#include
using namespace std;
int main() {
long n,c,i,temp,j;
unsigned long long x=0,temp1;
cin>>c>>n;
for(i=2;i<=n;i++){
if(i==2){
x+=c/2;
}else {
temp=i;
while((c-temp)>=0){
x++;
temp1=c-temp;
for(j=i-1;j>1;j--){
x+=temp1/j;
}
temp+=i;
}
}
}
cout<<x+1;
return 0;
}
#include
ReplyDelete#include
int main()
{
int n,c,i,j,a[500];
scanf("%d%d",&c,&n);
memset(a,0,sizeof(a));
a[0]=1;
for(i=1;i<=n;i++)
{
for(j=i;j<=c;j++)
{
a[j]+=a[j-i];
}
}
printf("%d",a[c]);
return 0;
}