حل مسئله پرفسور جان ( نامساوی ها ) - Professor John Inequalities Solotion

سلام دوستان

قبلا یک سوال از مسابقه DM Contest ShareCode به اسم حل مسئله کابل های در هم - Tangled in Cables Solotion را حل کرده بودیم در این مسابقه واقعا سوال های خوبی انتخاب شده بود و همه سوالها در واقع کاربرد یکی از الگوریتم ها بود.

خب سوال امروز مسئله نا مساوی هاست منبع اصلی سوال سایت ZOJ میباشد.

این سوال با دادن یک سری نامساوی از ما میخواهد که نامساوی های دیگری که نتیجه می دهد را پیدا کنیم . اشتباهی که زمان خواندن این سوال کردم باعث شد که برای چندین بار پشت سر هم Wrong Answer از سایت بگیرم . اما در آخر از دو روش مختلف از سایت ZOJ و Sharecode توانستم Accept بگیرم هر دو روش رو در ادامه به همراه کد توضیح میدهم ابتدا سوال را مطالعه کنید.

Professor John _ Inequalities

Professor John is investigating a math problem. He has obtained some relations among several variables. Now he would like to know if there are any other relations that can be deduced from these obtained ones. Since he has been working for too long, Professor John decides to grant himself a vacation while assigning you to do the job. Are you ready?

Input

The first line of input contains an integer N, which is the number of test cases. Then N test cases follow.
For each test case:
the 1st line contains a positive integer m (<= 100) which is the number of given relations;
the following m lines each contains a given relation, in the format
Variable1<Variable2
or
Variable1>Variable2
A "Variable" is represented by a capital character. There will not be conflicting relations given.

Output

For each test case, first print in one line "Case d:" where d is the number of the test case, start counting from 1.
Then output all the relations which can be deduced from the given relations in alphabetical order, in the format Variable1<Variable2. Each relation occupies one line. No extra space shall be printed. The given relations must NOT be included.
If no new relation is found, output "NONE" in one line.

Sample Input

2
3
A<B
C>B
C<D
2
A<B
C<D

Sample Output

Case 1:
A<C
A<D
B<D
Case 2:
NONE

روش اول:

در این روش ما درواقع همان کاری که کتاب ریاضی راهنمایی میگفت انجام داده ایم تک تک رابطه ها را اضافه کردیم به لیست رابطه ها و اینکار را تا زمانی که رابطه جدیدی به وجود می آمد ادامه دادیم و در پایان رابطه های جدید را چاپ کردیم.

روش دوم:

گفته شده بود که فقط از حروف بزرگ انگلیسی در ورودی ها استفاده میشه خب ما کل رابطه ها رو به یک ماتریس بولی وارد کردیم و بعد با الگوریتم فلوید وارشال Floyd Warshall algorithm ماتریس تعدی را بدست آوردیم و رابطه های جدید را چاپ کردیم. در ضمن چون در این کد نیازی به C++ lib احساس نمی شد به زبان C نوشته شده است.

خب در مقایسه این دو روش کاملا مشخص است که روش دوم سریعتر است و مقدار کمتری از حافظه استفاده میکند اما روش اول هم در محدوده زمانی ممکن به جواب رسیده و کاملا صحیح میباشد . در واقع چیزی که در مسابفات ACM مهم میباشد سریع پیدا کردن جواب و زمان ارسال جواب میباشد . پس لازم نیست وقتی میتوان از این روش Accept گرفت ما به دنبال روش های پیچیده تر باشیم. در واقع یک جمله معروف در این مورد میگوید : احمقانه ترین راهی را انتخاب کن که مطمئنی درست است.

موفق باشید

کد روش اول به زبان ++C

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n;
string p[10000];
void F1(int i){
    if(p[i][1]=='>'){
        char t;
        t=p[i][0];
        p[i][0]=p[i][2];
        p[i][2]=t;       
        p[i][1]='<';
    }
}
int cd(int i,int j){
    string mia,mib,maa,mab;
              mia=p[i][0];
              maa=p[i][2];
              mib=p[j][0];
              mab=p[j][2];
       if(mia==mab){
              p[n]=mib+"<"+maa;
              return 1;
       }else if(mib==maa){
              p[n]=mia+"<"+mab;
              return 1;
       }
       return 0;
}
int doit(){
       int i,j,k,count=0;
       for(i=0;i<n;i++)
              for(j=0;j<i;j++){
                     if(cd(i,j)){
                           for(k=0;k<n;k++){
                                  if(p[k]==p[n])break;
                           }      
                           if(k==n){
                                  n++;
                                  count++;
                           }
                     }
              }
       return count;
}
int main(){
       int T,i,Z=1,fn;
       for(cin>>T;Z<=T;Z++){
              cin>>n;
              fn=n;
              for(i=0;i<n;i++){
                  cin>>p[i];
                  F1(i);
              }
              while(doit());
              sort(p+fn,p+n);
              cout<<"Case "<<Z<<":\n";
              if(n==fn)
                     cout<<"NONE\n";
              for(i=fn;i<n;i++)
                     cout<<p[i]<<"\n";
       }
       return 0;
}

کد روش دوم به زبان C

#include<stdio.h>
#include<string.h>
int R[30][30],nu;
void f(){
    int i,j,k;
    for(k=0;k<30;k++)
        for(i=0;i<30;i++)
            for(j=0;j<30;j++)
                if(R[i][k]&&R[k][j]&&!R[i][j]){        
                    R[i][j]=2;
                    if(nu)nu=0;      
                }
}
int main(){
    int T,Z,n,j,i;
    char s[4];
    scanf("%d",&T);
    for(Z=1;Z<=T;Z++){
        nu=1;
        memset(R,0,sizeof(R));
        scanf("%d",&n);
        while(n--){
            scanf("%s",s);
            if(s[1]=='<'){
                 R[s[0]-'A'][s[2]-'A']=1;
            }else{
                 R[s[2]-'A'][s[0]-'A']=1;
            }
        }
        f();
        printf("Case %d:\n",Z);
        if(nu){
             printf("NONE\n");
        }else{
            for(i=0;i<30;i++){
            for(j=0;j<30;j++){          
            if(R[i][j]==2)printf("%c<%c\n",i+'A',j+'A');
            }
            }
        }
    }
}