树数学公式UVA

Question

猫戴帽子的当且仅当它的帽子里有N只猫。只有一只猫不在其他猫的帽子里。如果有M猫没有帽子，有多少猫？

我尝试了这个问题，下面是我的代码片段。

LL dfs(int n,int m,LL sum){
    if(m<n){
        return -1; // If not possible
    }
    if(m==n){
        return sum+n+1;
    }
    return  dfs(n,(m/n)+m%n,sum+n*(LL)floor(m*1.0/n));
}

我显式地处理了案例n==1和m==1。

在我出错的地方找不到它。

链接：猫问题

Answer 1

你的计算是不必要的复杂--答案有一个直截了当的公式，不需要你的递归。

如果N=1 (每顶帽子有一只猫)那么M=1 (只能有一只猫没有帽子)，那么猫的总数是未知的，这是正确的。

在一般情况下，N>1，如果没有带帽子的猫，那么肯定只有“一只猫”没有帽子。所以在一开始，这就使得一只猫没有帽子。每当我们在一只猫上增加一顶帽子时，就会在这顶帽子里增加N只新的无帽子猫，但把那只老猫从没有帽子的地方移除，所以每一顶帽子都会给那些没有帽子的猫增加一个N-1的数目。因此，如果H是带帽子的猫的数量，则没有帽子的猫的数量是

M = 1 + H * (N - 1)

解决H的问题，

H = (M - 1) / (N - 1)

所以猫的总数是

T = M + H
  = M + (M - 1) / (N - 1)

请注意，这并不取决于猫树的结构。如果最后一个表达式是整数，否则是不可行的，则这是一个可行的答案。

下面是简单的Python3.x代码，打印猫的总数--我将把解析和其他打印留给您。如果您不喜欢if的双层，那么我的代码可以很容易地被重构成更平坦的代码。

def print_total_cats(n, m):
    if n == 1:
        if m == 1:
            print('Multiple')
        else:
            print('Impossible')
    else:
        if (m - 1) % (n - 1) != 0:
            print('Impossible')
        else:
            print(m + (m - 1) // (n - 1))

Answer 2

我错过的一个例子是，如果m==1答案应该是1，我会显式地处理它。

LL dfs(int n,int m,LL sum){
if(m<n){
    return -1;
}
if(m==n){
    return sum+n+1;
}
return  dfs(n,(m/n)+m%n,sum+n*(LL)floor(m*1.0/n));}

int main(){
int n,m;
LL a;
while(scanf("%d%d",&n,&m)&&(n||m)){
    cout<<n<<" "<<m<<" ";
if(n==1 && m==1){
    cout<<"Multiple\n";
    continue;
}
if(n==1 && m>=2){
    cout<<"Impossible\n";
    continue;
}
 if(m==1)
     a=1;
 else
    a=dfs(n,m,0);
 if(a==-1){
     cout<<"Impossible\n";
 }  else
    cout<<a<<"\n";
}
return 0;}