### Mobinteymoori's blog

By Mobinteymoori, 7 years ago,  158b, Comments (13)
 » 7 years ago, # | ← Rev. 3 →   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.
•  » » thanks,useful comment :)
 » Do you have issues with understanding the solution, or understanding the problem description?
•  » » 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 #define in cin>> #define out cout<< #define M 100002 #define FOR(i,k,l) for(int i(k); i #define Mii map #define Mss map #define Vi vector #define Di deque 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; } 
•  » » » Nice Solution :)
 » you can use greedy technique  int[] hash = new int; for (int i = 0; i < n; i++) { hash[Integer.parseInt(tokenizer.nextToken())]++; } long answer = 0; answer += hash; int min13 = Math.min(hash, hash); answer += min13; hash -= min13; hash -= min13; answer += hash; answer += hash / 2; hash %= 2; if (hash == 1 && hash >= 2) { answer++; hash = 0; hash -= 2; } answer += Math.ceil((hash + hash) / 4f); sb.append(answer); 
•  » » 3 years ago, # ^ | ← Rev. 2 →   Oops why did we put the number 5 size for the "hash" array?
•  » » » 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.
•  » » » » i didn't understand. plz cau u explain more than easier way?
•  » » » i didn't understand. plz cau u explain more than easier way? and if u tell greedy technique its too much helful for me.
• »
»
»
»

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.

 » #include #include 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>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<
•  » » who wanted this?