Mobinteymoori's blog

By Mobinteymoori, 7 years ago, In English

I have problem understanding the question 158B-taxi Could someone please help me ?

 
 
 
 
  • Vote: I like it
  • -4
  • Vote: I do not like it

»
7 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

first, you should privide a link to the problem you asking for.
Problem statement is very clear. Let's suppose children=cube, group of children = glued in one line cubes (at most 4 cubes)/ You have infinite number of boxes. Each box has form of 4 glued in one line cubes. You have to minimize number of boxes. Box can include group of 4, of grpoup of 2 and one more group of 2. All possible configurations are 1+1+1+1, 1+1+2, 1+3, 2+2, 4. Try to ask someone who can speak your language.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you have issues with understanding the solution, or understanding the problem description?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't know if you've already solve this problem; Else, here is one solution. You just have to store all groups in an array. And , sort it increasingly. Then, the solution becomes more obviously.

    #include <bits/stdc++.h>
    #define in cin>>
    #define out cout<<
    #define M 100002
    #define FOR(i,k,l)   for(int i(k); i<l; i++)
    #define Si set<int>
    #define Mii map<int,int>
    #define Mss map<string,string>
    #define Vi vector<int>
    #define Di deque<int>
    
    
    
    
    
    using namespace std;
    
    int main(){
    ios_base::sync_with_stdio(false);
    int n,taxi=0;
        in(n);
        Vi v(M);
    
        FOR(i,0,n){
            in(v[i]);
        }
        sort(v.begin(),v.end());
    
            int i=v.size()-1;
            int k=0;
            while(k!= i){
                if(v[i]+ v[k]<=4){
                    v[i]+=v[k];
                    k++;
                }
                else{
                    i--;
                    taxi++;
                }
            }
        out(taxi+1);
    
    
    return 0;
    }
    
    
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

you can use greedy technique

        int[] hash = new int[5];
        for (int i = 0; i < n; i++) {
            hash[Integer.parseInt(tokenizer.nextToken())]++;
        }
        long answer = 0;
        answer += hash[4];
        int min13 = Math.min(hash[1], hash[3]);
        answer += min13;
        hash[1] -= min13;
        hash[3] -= min13;
        answer += hash[3];
        answer += hash[2] / 2;
        hash[2] %= 2;
        if (hash[2] == 1 && hash[1] >= 2) {
            answer++;
            hash[2] = 0;
            hash[1] -= 2;
        }
        answer += Math.ceil((hash[1] + hash[2]) / 4f);
        sb.append(answer);
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Oops why did we put the number 5 size for the "hash" array?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because the indices of the elements will be from 0 to 4. We use the indices 1 to 4 in the program. We can use sixe 4 but it will make the program slightly more difficult to understand.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i didn't understand. plz cau u explain more than easier way? and if u tell greedy technique its too much helful for me.

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        package Practice;

        import java.util.Scanner;

        public class Main {

        public static void main(String[] args) {
            Scanner input = new Scanner(System.in);
            int a,n,sum=0,c1=0,c2=0,c3=0,c4=0;
            n=input.nextInt();
        
            for (int i = 0; i < n; i++) {
                a=input.nextInt();
                switch (a) {
                    case 1:
                        c1++;
                        break;
                    case 2:
                        c2++;
                        break;
                    case 3:
                        c3++;
                        break;
                    default:
                        c4++;
                        break;
                }
            }
            sum=sum+c4;
            c4=0;
        
            sum=sum+(c2/2);
            c2=c2%2;
        
            if(c1>=c3){
            sum=sum+c3;
            c1=c1-c3;
            c3=0;
            sum=sum+(c1/4);
            c1=c1%4;
            if((c1+(c2*2))<=4 && (c1+(c2*2))>0){
            sum++;
            c1=0;
            c2=0;
            }else if(c1==3 && c2==1){
            sum=sum+2;
            c1=0;
            c2=0;
            }
            }
        
            else if(c1<c3){
            sum=sum+c1;
            c3=c3-c1;
            c1=0;
            sum=sum+c3+c2;
            }
        
            System.out.println(sum);
        
        
        }

        }

        Hope you will get this.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    long int n,i,j=0,tmp=0,sum=0,taxi=0;
    cin>>n;
    long int a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n);//sort elements in increasing order of magnitudes
    for(i=n-1;i>=j;i--)
    {
        if(!sum)
            sum += a[i];//calculates sum only if sum = 0;
        if(sum == 4)
        {
            taxi++;
            j=tmp;
            sum=0;
        }
        else if(sum > 4 || i==j)
        {
            taxi++;
            if(i==j)
                break;
            sum=0;
            j=tmp-1;
        }
        else
        {
            tmp=j;
            while(sum < 4 && tmp < i)
            {
                sum += a[tmp];
                tmp++;
            }
            if(i==tmp)//2 elements remaining
            {
                if(sum>4)//if sum = 5 we know 2 separte taxis are needed ex: (2,3)
                    taxi+=2;
                else
                    taxi++;//sum is less than 4 thus we can say remaining people can be shoved into 1 taxi
                break;
            }
            i++;//since decrement occurs in loop (i--), we have to keep i pointer pointing to the same value as before
        }
    }
    cout<<taxi<<endl;//print taxis
    return 0;
}