[UVA] 12406 - Help Dexter＠Morris' Blog｜PChome Online 個人新聞台

2012-05-04 20:11:23| 人氣1,837| 回應2 | 上一篇 | 下一篇

[UVA] 12406 - Help Dexter

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

 
  D

  Help Dexter

 


You know Dexter, right? He is a very talented young
scientist. He has a huge lab hidden inside his building. He made all possible
security arrangement to keep his naughty sister Dee Dee away from his lab. But
she always finds a way into the lab. One day Dee Dee came to the lab and
started her usual work, messing up Dexter's lab! Dexter was working on a very
important project, so he begged to her and said, "Please!!!
Not today. I will do anything for you, but please leave this lab today!!!"
Dee Dee was waiting for this chance, she said, "Ok, you do my homework I
won't disturb you today." What can Dexter do? He agreed. Dee Dee said, "My
teacher told me to write down 17 numbers. First one single digit number, second
one two digit number, ..., nth one n digit number. They will
consist of only digit 1 and 2 and the nth number should be divisible by 2n."
Dexter thought, "I have very little time to finish the project. I can't
waste my time for this silly problem, I have bigger problem to think!" So,
he sent the modified version of this problem to you. Hurry up, Dee Dee is
waiting.
InputInput starts with an integer T (≤ 300),
denoting the number of test cases.
Each case starts with two integers: p q (1 ≤ p, q
≤ 17).
OutputFor each case, print the case number first. Then you have to
find two integers (smallest and largest) which have p digits and is
divisible by 2q. The integers should contain only 1's and 2's.
If no result is found, print "impossible". If there is only
one integer, then print that integer. Otherwise print both integers (first the
smallest one then the largest one) separated by a single space.

 
  
  Sample Input
  
  
  Output for Sample Input
  
 

  32 22 12 3
  Case 1: 12Case 2: 12 22Case 3: impossible


#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) < (y) ? (x) : (y))
#define max(x, y) ((x) > (y) ? (x) : (y))
long long hp[2][20][20];
void dfs(int idx, long long num) {
    int i;
    for(i = 1; i <= 17; i++) {
        if(num%(1<<i) == 0) {
            hp[0][idx][i] = min(hp[0][idx][i], num);
            hp[1][idx][i] = max(hp[1][idx][i], num);
        } else {
            break;
        }
    }
    if(idx == 17)
        return;
    dfs(idx+1, num*10 + 1);
    dfs(idx+1, num*10 + 2);
}
int main() {
    memset(hp[0], 127, sizeof(hp[0]));
    memset(hp[1], 0, sizeof(hp[1]));
    dfs(0, 0);
    int t, p, q, c = 0;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &p, &q);
        printf("Case %d: ", ++c);
        if(hp[0][p][q] == hp[1][p][q])
            printf("%lld\n", hp[0][p][q]);
        else if(hp[1][p][q] == 0)
            puts("impossible");
        else
            printf("%lld %lld\n", hp[0][p][q], hp[1][p][q]);
    }
    return 0;
}

我要檢舉

#12406#Help Dexter

台長： Morris

您可能對以下文章有興趣

[UVA] 12319 - Edgetown's Traffic Jams

[UVA] 394 - Mapmaker

[ACM-ICPC] 4714 - In-circles Again

[UVA][maxflow、黑白染色] 10349 - Antenna Placement

人氣(1,837) | 回應(2)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 11398 - The Base-1 Number System
此分類上一篇:[UVA] 10063 - Knuth's Permutation

回應(2)