Blackjack BLKJK SOLUTION Code Chef

Blackjack BLKJK SOLUTION Code Chef

Chef is playing a card game called Blackjack. He starts with a deck of NN cards (numbered 11 through NN), where for each valid ii, the ii-th card has an integer AiAi written on it. Then he starts dealing the cards one by one in the order from card 11 to card NN. Chef wins if at some moment in time, the sum of all the cards dealt so far is between XX and YY inclusive; if this never happens, Chef loses.

We want Chef to win the game, so without him noticing, we will swap some pairs of cards (possibly none) before the game starts. Find the smallest number of swaps we need so that Chef would win the game, or determine that it is impossible to make Chef win.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains three space-separated integers NN, XX and YY.
  • The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.

Output

For each test case, print a single line containing one integer ― the smallest required number of swaps or −1−1 if Chef cannot win.

Constraints

  • 1≤T≤1001≤T≤100
  • 1≤N,X,Y≤1031≤N,X,Y≤103
  • X≤YX≤Y
  • 1≤Ai≤1031≤Ai≤103 for each valid ii
  • the sum of NN over all test cases does not exceed 104104

Subtasks

Subtask #1 (22 points): Chef can win if we make up to 22 swaps

Subtask #2 (34 points):

  • 1≤N,X,Y≤4001≤N,X,Y≤400
  • 1≤Ai≤4001≤Ai≤400 for each valid ii
  • the sum of NN over all test cases does not exceed 4,0004,000

Subtask #3 (44 points): original constraints

Example Input

3
3 4 5
1 2 3
3 3 4
1 2 3
2 20 30
40 10

Example Output

1
0
-1

Explanation

Example case 1: We can swap the last card with one of the first two cards.

Example case 2: No swaps are necessary, Chef wins after dealing the first two cards.

Example case 3: The order of the cards in the deck does not matter, Chef cannot win.

Solution

Program Python:

t=int(input())
for i in range(t):
    n,x,y=map(int,input().split())
    a=list(map(int,input().split()))
    def findsubset(set, n,sum):
        subset =([[False for i in range(sum + 1)] 
                for i in range(n + 1)])
        for i in range(n + 1):
            subset[i][0] = True
        for i in range(1, sum + 1):
            subset[0][i]= False
        for i in range(1, n + 1):
            for j in range(1, sum + 1):
                if j<set[i-1]:
                    subset[i][j] = subset[i-1][j]
                if j>= set[i-1]:
                    subset[i][j] = (subset[i-1][j] or
                                    subset[i - 1][j-set[i-1]])
        l=[]
        for k in range(n + 1):
            for j in range(x,sum+1):
                if(subset[k][j]==True):
                    l.append(j)
                    break
        return(l)
    u=findsubset(a,n,y)   
    if(len(u)==0):
        print(-1)
    else:
        s=0
        c=0
        for i in range(n):
            s=s+a[i]
            if(s>=x and s<=y):
                c+=1
                break
        if(c!=0):
            print(0)
        elif(x%2==0 and y%2==0) or (x%2==0 and y%2==1) or(x%2==1 and y%2==0):
            print(1)
        else:
            if(x==y):
                print(2)
            elif(x!=y):
            	print(1)    

Program Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef
{
   
    public static int get(int idx, int x, int y, int s, int[]a ,ArrayList<Integer>sw){
        if(s>=x&&s<=y){
            int ss=0;
            for(int i:sw)if(i>=sw.size())ss++;
            return ss;
        }       
        if(idx>=a.length)return (int)1e7;
            if(dp[idx][s]!=-1)return dp[idx][s];
        
        int r=(int)1e7;
        if(s+a[idx]<=y){
        sw.add(idx);
        r=Math.min(r,get(idx+1,x,y,s+a[idx],a,sw));
            sw.remove(sw.size()-1);
        }
        r=Math.min(r,get(idx+1,x,y,s,a,sw));
        
        return dp[idx][s]=r;
        
    }
    static int[][]dp;
	public static void main (String[] args) throws java.lang.Exception
	{
	    Scanner s=new Scanner(System.in);
	    int t=s.nextInt();
	    while(t-->0){
	        int n=s.nextInt();
	        int x=s.nextInt();
	        int y=s.nextInt();
	        int []a=new int[n];
	        dp=new int[n][y+1];
	        int ss=0;
	        for(int i=0;i<n;i++)Arrays.fill(dp[i],-1);
	      int min=Integer.MAX_VALUE;
	        for(int i=0;i<n;i++){a[i]=s.nextInt();ss+=a[i];min=Math.min(min,a[i]);
	         }
	            if(ss<x||min>y)System.out.println("-1");
	            else{
	            int ans=get(0,x,y,0,a,new ArrayList());
	            if(ans>=(int)1e7) System.out.println("-1");
	            else System.out.println(ans);
	            }
	            
	        }
	        
	        
	    }
	}

Program C++:

#include <bits/stdc++.h>
using namespace std;
#define ll int
        void solve()
        {
        	ll n,x,y;
        	cin>>n>>x>>y;

        	vector<ll>arr(n+1);
        	vector<ll>pre(n+1,0);
        	pre[0]=0;
        	map<ll,vector<ll> >mp;
        	for(ll i=1;i<=n;i++)
        	{
        		cin>>arr[i];
        		pre[i]=pre[i-1]+arr[i];
        		mp[arr[i]].push_back(i);
        	}

        	ll dp[n+1][y+1];
        	
        	for(ll i=0;i<=n;i++)
        	{
        		for(ll j=0;j<=y;j++)
        		{
        			if(j==0)
        			{
        				dp[i][j]=0;
        				continue;
        			}
        			if(i==0)
        			{
        				dp[i][j]=-1e5;
        				continue;
        			}
        			dp[i][j]=dp[i-1][j];
        			if(j-arr[i]>=0&&dp[i-1][j-arr[i]]>=0)
        				dp[i][j]=max(dp[i][j],dp[i-1][j-arr[i]]+1);
        		}
        	}
        	ll dp1[n+2][y+2];
        	for(ll i=n+1;i>0;i--)
        	{
        		for(ll j=0;j<=y;j++)
        		{
        			if(j==0)
        			{
        				dp1[i][j]=0;
        				continue;
        			}
        			if(i==n+1)
        			{
        				dp1[i][j]=+1e5;
        				continue;
        			}
        			dp1[i][j]=dp1[i+1][j];
        			if(j-arr[i]>=0)
        				dp1[i][j]=min(dp1[i][j],dp1[i+1][j-arr[i]]+1);
        		}
        	}        	ll ans = n+1;
        	for(ll k=x;k<=y;k++)
        	{
        		for(ll i=1;i<=n;i++)
        	        	{
        	        			for(ll j =0;j<=min(pre[i],k);j++)
        	        			{
        	        				ll occu = dp[i][j];
        	        				ll lef = i-occu;
        	        				ll rig = dp1[i+1][k-j];
        	        				ans= min(ans,max(lef,rig));
        	        		    }
        	        	}
        	    }
        	    if(ans>=n)
        	    	ans=-1;
        	    cout<<ans<<endl;
        }

        int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
         
        int TESTS = 1;
         cin>>TESTS;
         while(TESTS--){
              solve();
               }
         
            return 0;
        }

January Long Challenge 2021

Leave a Comment