Bit mask-г хэрэглэх жишээ

За сайн байцгаана уу. Бит маскыг яаж ашиглах талаар дараах бодлогон дээр тайлбарлая. Зөвлөгөө: Энэ постыг бүтэн уншихаасаа өмнө дараах бодлогыг өөрөө бодож үз. Баглалт (1995 оны Олон Улсын Мэдээлэл Зүйн Олимпиадад бодогдсон бодлого) Танд дөрвөн ширхэг тэгш өнцөгт өргөн болон урттайгаа (урт <=50, өргөн <= 50) өгөгдсөн бол эдгээр тэгш өнцөгтүүдээ хооронд нь давхарлалгүйгээр өрж дахин шинэ тэгш өнцөгтөд багтаах ба шинээр үүсэх тэгш өнцөгтийн талбайг хамгийн бага байлгах ёстой. Дөрвөн тэгш өнцөгтөө доорх зургаан янзын байрлалаар л байрлуулж болохыг тогтоосон ба өөр байрлалын загвар байж болох ч энэ зургаан загварт тэгш өнцөгтүүдээ 90-н градус эргүүлэх зэргээр үүсгэсэн байгаа.

Тэгэхээр бусад байрлалын загварыг тооцох шаардлагагүй. Дээрх өгүүлбэрээс харахад бодлогын хариуг гаргаж авахын тулд тэгш өнцөгтүүдээ 90-н градус эргүүлж болно. Мөн үүссэн хамгийн бага талбайтай тэгш өнцөгт олон байж болох тул бүх хариуг хэвлэж харуул. Гаралтын формат нь эхний мөрөнд хамгийн бага тэгш өнцөгтийн талбай, дараагийн мөрүүдэд хамгийн бага талбайтай тэгш өнцөгтүүдийг эрэмбэлж гаргана. Жишээ оролт:

1 2

2 3

3 4

4 5

Жишээ гаралт:

40

4 10

5 8

Бодолт: За энэ бодлогыг оролдож үзсэн бол бодлогын х ариуг гаргахын тулд 4-н тэгш өнцөгтөө бүх боломжит байрлалаар шалгахаас өөр аргагүй юм. Тэгш өнцөгтүүдээ a b c d гэж дугаарлая.

 

Дээрх 6-н загвар тус бүр дээр 4-н тэгш өнцөгтөө тавин үүсэх тэгш өнцөгтийг тооцох болно. 4-н тэгш өнцөгтөө нийт 4! янзаар байрлуулж болох ба м өн байрлуулах бүрт дахин 4-н тэгш өнцөгтөө 90-н градус эргүүлж (энд цагийн зүүний эсрэг, дагуу эргүүлэх хамаагүй!) үүсэх тэгш өнцөгтийг тооцох юм. Жишээ нь 1-р загвараас үүсч болох хэдхээн тэгш өнцөгтийг үзүүлье:

Эндээс яагаад бүх 4! сэлгэх чухал болохыг харах хэрэгтэй...

харин энд эргүүлэлтийг сэлгэмэл болгон дээр хийж үүсэх тэгш өнцөгтийг тооцох ёстойг харсан байх. Энд d болон c-г эргүүлсэн байна. d гэсэн тэгш өнцөгтийг a b-н дунд эргүүлэхгүй тавих, мөн эргүүлсний дараа үүсэг тэгш өнцөгт гээд бүгдийг шалгах хэрэгтэй. Бусад тэгш өнцөгтийн хувьд ч адил. Одоо яагаад 4! янзаар байрлуулах Одоо Бит маскыг юун дээр ашиглахыг тайлбарлая: Магадгүй аль хэдийн ойлгочихсон байх. Мэдээж энд Бит маскыг тэгш өнцөгтүүдийг эргүүлэх, эргүүлсэн эсэхийг шалгахад ашиглах юм. 4-н тэгш өнцөгт байгаа. Тэгш өнцөгт бүрийг эргүүлсэн, эргүүлээгүй төлөв байдал 2^4 = 16 ширхэг байгаа. Өмнөх постонд бичсэнчлэн 0-15 хүртлэх тоо бүр нэг төлөв байдлыг заах ба 0-15 тоо бүрийн i-р бит нь 1 болон эргүүлсэн 0 бол эргүүлэгүй. Дараагийн гарч ирэх асуудал нь үүссэн тэгш өнцөгтүүдээс яаж хамгийн багыг нь олох вэ? Миний бодолт бол өгөгдөх тэгш өнцөгтүүдийн талууд 50-аас хэтрэхгүй тул үүсэж хамгийн том хариу нь (50+50)*2 болохоор 1-ээс (50+50)*2 тоотой тэнцүү талбайтай бүх тэгш өнцөгтүүдийг талбайгаар нь map-лаад 2тын модон хийх. Ингэх нь сүүлд хариугаа эрэмбэлэх шаардлагагүй юм. Сүүлийн өгүүлбэрийг сайн ойлгохын тулд C++-н map, set сангуудыг ашиглаж сураарай. source code::

/*
AUTHOR: Dunno
PROB: Packing Rectangles
LANG: C++
*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<queue>
#include<utility>
#include<stack>
#include<vector>
#include<cstring>
#include<string>
#include<map>
#include<cctype>
#include<set>
using namespace std;
#define rect pair<int, int>
#define h first
#define w second
#define mk make_pair
map< int, set< rect > >rectangles;
//************UNDSEN 6-n zagvariig bichij baina***
rect layout1( rect a, rect b, rect c, rect d  ){
    int width = a.w + b.w + c.w + d.w;
    int height = max( max(a.h, b.h), max(c.h, d.h) );
    return mk(width, height);
}
rect layout2( rect a, rect b, rect c, rect d  ){
    int width = max( (a.w+b.w+c.w), d.w );
    int height = max( max(a.h, b.h), c.h ) + d.h ;
    return mk(width, height);
}
rect layout3( rect a, rect b, rect c, rect d  ){
    int width = max( (a.w + b.w + c.w), (d.w + c.w));
    int height = max( c.h, max( a.h+d.h, b.h+d.h ) ) ;
    return mk(width, height);
}
//SAIN BODOH YUM BOL 4 BOLON 5-r zagvaruud adilhan
rect layout4( rect a, rect b, rect c, rect d  ){
    int width = a.w + c.w + max(b.w, d.w);
    int height =  max( max(a.h, c.h), b.h+d.h );
    return mk(width, height);
}
rect layout6( rect a, rect b, rect c, rect d  ){
    int height = max( a.h+c.h, d.h+b.h );
    int width = a.w + b.w;
    if(a.h<b.h)
      width = max(width, c.w+b.w);
    if(a.h+c.h>b.h)
      width = max(width, c.w+d.w);
    if(b.h<a.h)
       width = max(width, a.w+d.w);
    width = max(width, c.w);
    width = max(width, d.w);
    return mk(width, height);
}
rect rotate(rect a){
   return mk(a.w, a.h);
}
int area(rect a){
   return a.w*a.h;
}
int main(){//----------------------------------------------------------
    rect a[4];
    int permute[4]= {0, 1, 2, 3};//Selgemel hadgalah
    int binary[4];
    int ret = 10001;
    for(int i=0; i<4; i++)
       scanf("%d%d", &a[i].h, &a[i].w);
    do{//SELGEMEL uusgej baina
 s     // SELGEMEL bolgon deer bit mask bichij tegsh ontsogtuudiig uusgej baina
       for(int i=0; i<(1<<4); i++){
          for(int j=0; j<=3; j++)binary[j]=0;
            for(int j=0; j<4; j++){
                if((1<<j)&i)
                   binary[j] = 1;
            }

            for(int j=0; j<=3; j++)if(binary[j]) a[ permute[j] ] = rotate(a[ permute[j] ]);   
            rect temp = layout1(a[permute[0]], a[permute[1]], a[permute[2]], a[permute[3]]);
            if(area(temp)<=ret){
               if(temp.w<temp.h)temp = rotate(temp);
               ret = area(temp);
               rectangles[ret].insert(temp);
            }

            temp = layout2(a[permute[0]], a[permute[1]], a[permute[2]], a[permute[3]]);
            if(area(temp)<=ret){
                if(temp.w<temp.h)temp = rotate(temp);
                ret = area(temp);
                rectangles[ret].insert(temp);
            }
 
            temp = layout3(a[permute[0]], a[permute[1]], a[permute[2]], a[permute[3]]);
            if(area(temp)<=ret){
                if(temp.w<temp.h)temp = rotate(temp);
                ret = area(temp);
                rectangles[ret].insert(temp);
            }

            temp = layout4(a[permute[0]], a[permute[1]], a[permute[2]], a[permute[3]]);
            if(area(temp)<=ret){
                if(temp.w<temp.h)temp = rotate(temp);
                ret = area(temp);
                rectangles[ret].insert(temp);
            }
           
            temp = layout6(a[permute[0]], a[permute[1]], a[permute[2]], a[permute[3]]);
            if(area(temp)<=ret){
               if(temp.w<temp.h)temp = rotate(temp);
               ret = area(temp);
               rectangles[ret].insert(temp);
            }

            for(int j=0; j<=3; j++)if(binary[j]) a[ permute[j] ] = rotate(a[ permute[j] ]); 
           
       }
    }while(next_permutation(permute, permute+4));
   
           cout<<ret<<endl;
           for(set< rect >::iterator it=rectangles[ret].begin(); it!=rectangles[ret].end(); it++)
              cout<<it->first<<" "<<it->second<<endl;
   
return 0;}