Mobinteymoori's blog

Question 158B taxi
By Mobinteymoori, 11 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

Comments Comments (8)
| Write comment?
»
11 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.

→ Reply
»
11 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?

→ Reply
»
9 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);
→ Reply
  • »
    »
    8 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?

    → Reply
    • »
      »
      »
      7 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.

      → Reply
      • »
        »
        »
        »
        6 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.

        → Reply
»
4 years 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;
}
→ Reply