در مطالب گذشته سوال کارت های برابر را حل کردیم حل اول کارت های برابر

حل قدیمی از چند جهت اشکال داشت ... اول اینکه بسیار ناخوانا بود و رفع عیب های احتمالی بوجود آمده سخت بود.

دوم اینکه دارای پیچیدگی زمانی O(N2M4) بود که با توجه به N کمتر از 100 و M=5 این کد Accept شد اما برای مسئله مشابه با M های بزرگتر ، برای مثال M=100 برنامه ما در محدوده زمانی مورد نظر به جواب نمیرسید و نتیجه ارسال کد Time Limit Executed میشد.

برای حل این سوال اینبار از یکی از Data Structure های C++ Standard Library به نام Bitset استفاده میکنیم که میتوان از این Solution به عنوان مثالی برای یادگیری Bitset نیز استفاده کرد.

میشود Bitset را به عنوان یک آرایه ای از متغیر Boolean تعریف کرد، اما این تعریف بسیار ناقص میباشد زیرا برای یک آرایه Boolean توابعی مانند شیفت به چپ ، شیفت به راست ، نقیض ، مساوی بودن ، OR , AND , XOR با یک آرایه Boolean دیگر وجود ندارد و برای پیاده سازی هریک نیاز به تابع نویسی داریم. اما در Bitset تمام این امکانات گنجانده شده است.

خب بار دیگر سوال را مرور میکنیم لینک سوال


  Bingo is a game played on a 5 by 5 board called a card. There are many variations, but Bob's Bingo uses the following rules:

    Each card will have the 25 positive integers, where each value is less than or equal to 75.
    No value will appear in more than one position on a card.
    During the game, numbers are selected and if they are on a card, they are covered.
    To be a winner, all the numbers on a card in a given pattern must be covered. The pattern can change from game to game. Some sample patterns (marked by the Xs) include:

Two different cards may both be winners for a given pattern. Consider the cards and pattern below:

Both of these cards are winners when the numbers 1, 2, 7, 8, 13, 14, 19, 20, and 25 are selected. These are considered to be equivalent cards.

Bob's Bingo players get mad when they have two equivalent cards (since it reduces their chance to win) or when one of their cards is equivalent to a card of another player (since they have to share the prize). Bob wants you to write a program to go through his stack of cards and identify the equivalent cards.

صورت ساده شده سوال این است که ما میخواهیم بررسی کنیم که آیا دو مجموعه از اعداد با هم برابر هستند یا خیر. این اعداد بدون تکرار و از 1 تا 75 هستند. دقت کنید که در مجموعه ها جایگاه یک عضو معنایی ندارد و {A,B}={B,A} میباشد.

برای حل ما به تعداد حداکثر مجموعه ها ( یعنی 100 در این سوال ) Bitset به طول 75 در نظر میگیریم.

هر عددی که جزو مجموعه بود بیت متناظر با همان عدد را True قرار میدهیم.

در انتها در دو حلقه Bitset های ساخته شده را باهم مقایسه میکنیم.

این حل دارای پیچیدگی زمانی O(N2+NM2) میباشد که برای ورودی هایی به بزرگی N=100 و M=500 جوابگو است.

همچنین نکته ای که برای حل تمامی سوالات ACM میتوانید مد نظر قرار دهید ، دو خط ای میباشد که در کد نمونه به صورت Comment در آمده اند.

این سوال ورودی نمونه طولانی ای داشت. برای هر مرحله Test کردن کد در حالت عادی شما کل ورودی را باید در Console بنویسید.

اینکار بسیار زمان بر میباشند. و همچنین ممکن است خطا به وجود بیاید زبان C و C++ به ورودی و خروجی Console به صورت دو فایل به نام stdin و stdout نگاه میکنند.

تابع freopen همانطور که از اسمش مشخص است File Re Open یک فایل را دوباره از مسیر دیگری میخواند.

نتیجه این است که ما میتوانیم ورودی را بجای Console درون یک فایل Text قرار داده و با فرمان freopen مسیر ورودی را عوض کنیم.

همچنین میتوانیم برای دقیق بررسی کردن خروجی ، خروجی را نیز در فایل Text دیگری قرار دهیم.

فقط باید توجه کنیم که در زمان ارسال کد برای Judge این دو خط را حذف کرده یا تبدیل به Comment کنیم. وگرنه بررسی کد دچار اشکال میشود ممکن است Time Limit Executed یا Wrong Answer بگیرید.

برای استفاده از freopen در کامپایلر های GCC میبایست Header File این تابع یعنی cstdio را فراخانی کنیم اما در Microsoft Visual Studio نیاز به اینکار نیست و این تابع در Header File اصلی یعنی iostream وجود دارد.


#include<iostream>
#include<bitset>
using namespace std;
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	char m[5][6];
	bitset<75> cards[100];
	int G=0,i,j,k,n,T;
	while(1){
		for(i=0;i<5;i++)cin>>m[i];
		cin>>n;
		if(!n)break;
		if(G++)cout<<endl;
		cout<<"Game "<<G<<endl;
		for(k=0;k<n;k++){
			cards[k]=0;
			for(j=0;j<5;j++)
				for(i=0;i<5;i++){
					cin>>T;
					if(m[j][i]=='X')
						cards[k][T-1]=1;
				}
		}
		for(j=0;j<n;j++)
		for(i=0;i<j;i++)
			if(cards[i]==cards[j]){
				cout<<"Card "<<j+1<<" is equivalent to card "<<i+1<<endl;
				break;
			}
	}
	
	return 0;
}