Digital Friends

Description
Two positive integers are called friends if they consist of the same decimal digits. So 123 and 32331313323213 are friends, but 123 and 22121221 are not.

Two positive integers (that are not friends) are called almost friends if a single neighbour exchange in one of them results in a pair of friends. A neighbour exchanges two neighbouring digits a and b into a-1 and b+1, or into a+1 and b-1, provided that these new digits are still in the range 0...9, and that no leading zero is generated. So 123 and 2223042 are almost friends(let 04->13), and 137 and 470 are neither friends nor almost friends(note that 13 -> 04 is not allowd).
The problem is to determine if two given integers are friends or almost friends.

Input
The frist line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
One line with two integer x and y, separated by a single space, with 0 < x, y < 10¹⁰⁰.Both integers start with a non-zero digit.

Output
For every test case in the input, the output should contain a single line with the string "friends" or "almost friends" or "nothing", reflecting the property of the two given integers

Sample Input

4
123 32331313323213
123 22121221
123 223042
137 470

Sample Output

friends
almost friends
almost friends
nothing

Source
////  北大上过了，， 湖大上暂时没过

更新：

/*   感谢湖大的网友 xnby , 本题是因为他提供的测试用例：    

  97963074775118  613404734019809401557638041615194224

使我找到了算法的缺陷，没考虑两个数字相等并且连续的情况，现在已经彻底解决了。

解题报告：

首先用一个数组，统计两个数字串中每个数字出现的次数，如果这两个数组数字的出现情况一样，即要么出现要么不出现，那么这两个串是相同的（friends）; 否则，取第一个串，从第一个数字开始每次取两个相邻的数字进行+-,-+变换，如果该变换可以改变数字的出现情况，即使某些数字消失，或者使某些数字出现，我们就认为这个变换有效并进行变换，变换之后再比较，如果这时数字的出现情况相同即为(almost friends),否则恢复变换前的状态，取下一个相邻的数字对，直到结束，如果最后都没有出现almost friends情况则，对另一个串做同样的处理，如果两个串的尝试都没有almost friends则是 nothing。开始主要是因为没有考虑两个数字相同并相邻的情况，某些有效的变换被认为是无效的，所以北大上AC湖大上WA的尴尬情况就出现了，再次感谢 xnby..

举例：

97963074775118 613404734019809401557638041615194224

扫描两个串得到A串的数字出现情况：1201111412  (0-9, 0 出现1次，1出现2次……)            

扫描B串得到数字出现情况为：5623733223, 一比较我们发现数字2再A串中出现0次，而在B串中出现了两次，所以不是friends，对A串进行变换,第一对相邻数字为 97, +-变换不能进行因为9+1=10>9, -+变换，产生88，8已经在A串中出现过，7,9的出现情况各减一次，都没有变为0，即该变换没有增加也没有减少组成的数字，因此变换是无效的，最初对有效的判断是：if(a[str[i]]==1 || a[str[i]-1]==0 || a[str[i+1]]==1 || a[str[i+1]+1]==0) 则有效，else 无效..这种判断在串B中对22做判断时会得出无效的结果，实际上是有效的，因为做-+,或者+-变换都可以使B串的数字2的出现次数由2变为0，这也就是为什么在湖大上WA的原因了； 更正后对-+变换判断语句是：if(a[str[i]]==1 || a[str[i]-1]==0 ||a[str[i+1]]==1 || a[str[i+1]+1]==0||str[i]==str[i+1]) 则有效 else 无效,呵呵其实str[i]==str[i+1]也并不一定是有效的，除非str[i]对应数字的出现次数为2。但是因为： 在一个串中对相邻数字 ab, 做-+,或者+-变换之后，再遇到相邻数字 ab,或者 ba 是不用判断的，不管它有效或者无效，最终的效果都和第一次出现 ab时的情况一样，因为只有十个数字，最多我们做20次无用功而已（两个串每个10），这些无用功是可以通过简单的判断代替精确判断而得回的。后面的不说了，看代码就可以了，自己感觉代码很清楚了。。。。。。
*/

#include <stdio.h>
#include <string.h>
/// 测试组成的数字是否相同
int test(char a[],char b[]){  
    int i;
    for(i=0; i<10; i++)
        if((a[i]&&!b[i])||(!a[i]&&b[i]))
            return 0;
    return 1;
}

/// +- 测试
int addTest(char str[],char a[],char b[],int i){
    char save[10];
 /// 必须引入或减少组成的数字，否则不处理
    if(a[str[i]]==1 || a[str[i]+1]==0 ||
        a[str[i+1]]==1 || a[str[i+1]-1]==0||str[i]==str[i+1]){
        memcpy(save,a,sizeof(char)*10);
        a[str[i]]--;
        a[str[i+1]]--;
        a[str[i]+1]++;
        a[str[i+1]-1]++;
        if(test(a,b))
            return 1;
        memcpy(a,save,sizeof(char)*10);
    }
    return 0;
}
/// -+ 测试
int subTest(char str[],char a[],char b[],int i){
    char save[10];
    /// 必须引入或减少组成的数字，否则不处理
    if(a[str[i]]==1 || a[str[i]-1]==0 ||
        a[str[i+1]]==1 || a[str[i+1]+1]==0||str[i]==str[i+1]){
        memcpy(save,a,sizeof(char)*10);
        a[str[i]]--;
        a[str[i+1]]--;
        a[str[i]-1]++;
        a[str[i+1]+1]++;
        if(test(a,b))
            return 1;
        memcpy(a,save,sizeof(char)*10);
    }
    return 0;
}

int change(char str[],char a[],char b[]){
    char stat[10][10]={0};  
    int i=1;
    if(str[1]==1){
        if(str[2]!=0 && str[0]>1 && addTest(str,a,b,1))
            return 1;
        i=2;
    }
    /// stat记录测试过的数对 ，对 ij测试+-则stat[i][j]=1
    /// 测试-+则stat[j][i]=1,此后不需要测试 ij,ji
    for(; i<str[0]; i++){
        if(str[i]<9 && str[i+1]>0 && !stat[str[i]][str[i+1]]){
            if(addTest(str,a,b,i))
                return 1;
            stat[str[i]][str[i+1]] = 1;
        }
        if(str[i]>0 && str[i+1]<9 && !stat[str[i+1]][str[i]]){
            if(subTest(str,a,b,i))
                return 1;
            stat[str[i+1]][str[i]] = 1;
        }
    }
    return 0;
}

int main(){
    int n,i,j;
    char diga[110],digb[110],a[10],b[10];
    scanf("%d",&n);
    for(i=0; i<n; i++){
        memset(a,0,sizeof(char)*10);
        memset(b,0,sizeof(char)*10);
        scanf("%s %s",&diga[1],&digb[1]);
        for(diga[0]=strlen(&diga[1]),j=1; j<=diga[0]; j++){
            diga[j] -= '0';
            a[diga[j]]++;
        }
        for(digb[0]=strlen(&digb[1]),j=1; j<=digb[0]; j++){
            digb[j] -= '0';
            b[digb[j]]++;
        }
        if(test(a,b))
            printf("friends\n");
        else if(change(diga,a,b)||change(digb,b,a))
            printf("almost friends\n"); 
        else
            printf("nothing\n");
    }
    return 0;
}

评论