You are given N red pieces of candy and M blue pieces of candy. Write a program to find the number of arrangements of candy in which not more than K pieces of the same color are placed next to each other.
Sample test case-
Input format = N M K
Input = 1 1 1 (Output = 2) (Explanation = possible combinations are RB BR which satisfies above condition)
Input = 2 1 1 (Output = 1) (Explanation = possible combinations are RRB RBR BRR but only RBR satisfies above condition)
in this problem you have to use dynamic programming
when you fill red candies then the number of blue candies that will we can fill next will reset to k
same for blue candies
i use recursive dp and my code is below for better understanding
To change this license header, choose License Headers in Project Properties.
To change this template file, choose Tools | Templates
and open the template in the editor.
*/
package candies;
import java.util.Scanner;
/**
*
@author Abhinav Vijayvargiya
*/
public class Candies {
static int limit_red=0;
static int limit_blue=0;
static int getans(int total,int red,int blue,int r,int b)
{
if((red+blue)==0)
{
return 1;
}
//fill red
int x=0;
if(red>0&&r>0)
{
x=getans(total-1,red-1,blue,r-1,limit_blue);
}
// fill blue
int y=0;
if(blue>0&&b>0)
{
y=getans(total-1,red,blue-1,limit_red,b-1);
}
return x+y;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int m=sc.nextInt();
int k=sc.nextInt();
limit_blue=k;
limit_red=k;
int ans=getans(n+m, n, m, k, k);
System.out.println(ans);
If M and N both less than K ans is direct (M+N)!/ (M! * N!)
else if one of them is bigger than K ,say M ,
then consider k+1 Red candies to be together and consider them as a bunch,
now ,find the number of ways for this (Standard P & C), and subtract from total.
if both M and N are greater than K ,then bunch only K+1 reds first, subtract the number of ways from total,then only K+1 blues,subtract from total, then K+1 reds and K+1 blues together ,add to total.(Principle of inclusion and exclusion)
