2013-12-05 15:49:36Morris
[UVA] 12643 - Tennis Rounds
SampleInput
3 2 5
3 5 7
2 1 2
2 2 1
SampleOutput
3
2
1
1
找兩個節點的最小共同祖先，計算第幾回合會對戰到。
藉由 k, 2*k, 2*k+1 的編號方式，除 2 即可得到共同祖先。
#include <stdio.h>
int main() {
int n, i, j, k;
while(scanf("%d %d %d", &n, &i, &j) == 3) {
i += (1<<n)-1;
j += (1<<n)-1;
for(k = 0; k <= n; k++)
if((i>>k) == (j>>k))
printf("%d\n", k), k = n;
}
return 0;
}
3 2 5
3 5 7
2 1 2
2 2 1
SampleOutput
3
2
1
1
找兩個節點的最小共同祖先，計算第幾回合會對戰到。
藉由 k, 2*k, 2*k+1 的編號方式，除 2 即可得到共同祖先。
#include <stdio.h>
int main() {
int n, i, j, k;
while(scanf("%d %d %d", &n, &i, &j) == 3) {
i += (1<<n)-1;
j += (1<<n)-1;
for(k = 0; k <= n; k++)
if((i>>k) == (j>>k))
printf("%d\n", k), k = n;
}
return 0;
}