საახალწლო თოვლის ბაბუები



ალექსანდრე აკეთებს თოვლის ბაბუებს. თითოეული თოვლის ბაბუა კეთდება ზუსტად 3 თოვლის გუნდისაგან: დიდი, საშუალო და პატარა. თითოეულ ნაკეთობაში არ უნდა გვხვდებოდეს ერთნაირი რადიუსის გუნდები , ანუ სამივე გუნდის რადიუსები წყვილ-წყვილად განსხვავებულებია . მაგალითად , გუნდებით , რომელთა რადიუსებია 1 , 2 და 3 შეგვიძლია თოვლის ბაბუის გაკეთება, მაგრამ 2 ,2 3 -ით ან 2 2 2 -ით არა . დაეხმარეთ ალექსანდრეს, გაიგოს რა მაქსიმალური რაოდენობის თოვლის ბაბუების გაკეთება შეუძლია მოცემული გუნდებით.


შემომავალი ინფორმაცია:
პირველ ხაზზე შემოდის 1 რიცხვი n (1<= n <=105)- თოვლის გუნდათა რაოდენობა .
შემდეგი ხაზზე შემოდის n ცალი რიცხვი (r)- გუნდათა რადიუსები (1<= r <= 109). რადიუსები შეიძლება განმეორდეს .


პასუხი :
პირველ ხაზზე გამოიტანეთ რიცხვი k - გაკეთებული თოვლის ბაბუების მაქსიმალური რაოდენობა , შემდეგ k ხაზზე კი თითოეული თოვლის ბაბუის აღწერა - დიდი, საშუალო და პატარა გუნდათა რადიუსები, რომლითაც ეს თოვლის ბაბუა გაკეთდა. თუ ამოხსნის რამოდენიმე ვარიანტია , დაბეჭდეთ ნებისმიერი .


მაგალითი 1 :
Input :
7
1 2 3 4 5 6 7
Output :
2
1 2 3
4 5 6


მაგალითი 2 :
Input :
3
4  4   3

Output
0


 

დავითვალოთ რამდენჯერ გვხვდება თითოეული რადიუსი და ჩავყაროთ priority-queue ში, ამის შემდეგ ყოველ ჯერზე , იქამდე სანამ რიგის ზომა 3 ან მეტია, ამოვიღოთ, ზედა სამი რადიუსი,  გავაკეთოთ თოვლის ბაბუა, დავაკლოთ რაოდენობებს 1 და რომელი რადიუსებიც ისევ დაგვრჩება უკან დავაბრუნოთ რიგში შეცვლილი რაოდენობით.

 

ამოხსნის კოდი 

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n  , big[40000] ,medium[40000] ,small[40000]  , x ,nums[110000] ,counter= 0  ;
    cin >> n; 
    priority_queue<pair<int, int > > pq; 
    map<int, int> m; 
    for(int i = 0; i < n; i++) { 
        cin>>x; m[x] += 1; 
        if(m[x] == 1) { 
            nums[counter] = x; 
            counter++; 
        }
    }
    for(int i = 0; i < counter; i++) { 
         pair<int, int> k;
         k.first = m[nums[i]];
         k.second = nums[i];
         pq.push(k);  
    }
    int res = 0, b[3];
    while(pq.size() > 2) { 
        pair<int,int> v1=pq.top(); pq.pop(); b[0]=v1.second;
	    pair<int,int> v2=pq.top(); pq.pop(); b[1]=v2.second;
		pair<int,int> v3=pq.top(); pq.pop(); b[2]=v3.second;
		sort(b,b+3);
        big[res] = b[2];
        medium[res] = b[1]; 
        small[res] = b[0];
        res++;    
        if(v1.first != 1)  {
            v1.first--; 
            pq.push(v1);    
        }
        if(v2.first != 1)  {
            v2.first--;
            pq.push(v2);    
        }
        if(v3.first != 1)  {
            v3.first--;
            pq.push(v3);    
        }
    } 
    cout << res << endl; 
    for(int i = 0; i < res; i++) { 
        cout << big[i] << " " << medium[i] << " " << small[i] << endl;   
    } 
    return 0;
}