24h購物| | PChome| 登入
2013-06-18 07:51:15| 人氣1,854| 回應0 | 上一篇 | 下一篇

[UVA][math] 10493 - Cats, with or without Hats

推薦 0 收藏 0 轉貼0 訂閱站台

Problem B

Cats, with or without Hats
 Time Limit: 2 seconds

Input: standard input
Output: standard output

A cat wears a hat if and only if it has N cats in it's hat. There is exactly one cat that is not inside any other cat's hat. If there are M cats without hats, how many cats are there?

Input

Input consists of several test cases. For each case, there would be two integers, N and M, where 1<=N<100000 and 1<=M<100000. The input ends with a case where N=0. You must not process this test case.

Output

For each test case, print N and M. Then if the total number of cats can be expressible uniquely in an integer, print the number. If the case is impossible print the word "Impossible" without quotes. If there are multiple answers, print the word "Multiple" without the quotes.

Sample Input

 
2 5
3 4
3 3
0 0

 

Sample Output

 
2 5 9
3 4 Impossible
3 3 4

Problemsetter: K M Hasan, Member of Elite Problemsetters' Panel

 


題目描述：

如果一隻貓有戴帽子，則帽子裡面會有 N 隻小貓，類推下去，會有一堆小小貓。

然後整個只會有 M 隻沒有戴帽子，問有幾隻貓。

題目解法：

當作一棵 N way tree(就是每個節點的分支 N)

設答案有 S 隻貓，葉節點有 M 個，推到內節點有 S-M 個

則由於是個長滿的樹，邊的個數會等於 (S-M)*N。

由於樹的節點個數 = 邊的個數+1，S = (S-M)*N+1

S = (M*N-1)/(N-1)

當 M = 1, N = 1 多組解


#include <stdio.h>

int main() {
    long long n, m;
    while(scanf("%lld %lld", &n, &m) == 2) {
        if(n == 0)  break;
        printf("%lld %lld ", n, m);
        if(n == 1 && m == 1)
            puts("Multiple");
        else if(n == 1 || (n*m-1)%(n-1))
            puts("Impossible");
        else
            printf("%lld\n", (n*m-1)/(n-1));
    }
    return 0;
}

我要檢舉
#10493#Cats#with or without Hats#math
台長： Morris

您可能對以下文章有興趣

人氣(1,854) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][格式] 10698 - Football Sort
此分類上一篇:[UVA][模擬] 10443 - Rock

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文