Why so serious? --[NKU]schindlerlee

2009年11月22日星期日.sgu154 sgu175

2009年11月22日星期日.sgu154 sgu175

sgu154:非常好的数论+二分题目
You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you know N! = 1*2*...*N. For example, 5! = 120, 120 contains one zero on the trail.

Input
One number Q written in the input (0<=Q<=10^8).

Output
Write "No solution", if there is no such number N, and N otherwise.

Sample test(s)
Input
2
Output
10

首先要明白一件事x!末尾的0的个数至于2和5的个数有关，又因为2的个数已经多余5，所以阶乘末尾
0的个数完全等价于所有数中5的个数
所以阶乘末尾0的个数可以用如下函数计算
int count(int x) //count the num of 0s in x!
{
    int res = 0;
    while(x > 0) {
        res += x / 5;
        x /= 5;
    }
    return res;
}
然后题目要求末尾个数有n个0的x!中，x为多少
因为哦count函数具有单调增加的性质，所以完全可以二分寻找符合条件的x
trick 1.n == 0 ,时答案是1
trick 2.二分出来的结果有可能应该输出No Solution !(具体原因自己考虑一下)

sgu175:经典
Let phi(W) is the result of encoding for algorithm:
1. If the length of W is 1 then phi(W) is W;
2. Let coded word is W = w1w2...wN and K = N / 2 (rounded down);
3. phi(W) = phi(wNwN-1...wK+1) + phi(wKwK-1...w1).
For example, phi('Ok') = 'kO', phi('abcd') = 'cdab'.
Your task is to find position of letter wq in encoded word phi(W).

Input
Given integers N, q (1 <= N <= 10^9; 1<= q <= N), where N is the length of word W.

Output
Write position of letter wq in encoded word phi(W).

Input
9 4

Output
8

读完题之后，直觉的想法就是递归模拟，复杂度也对，也没问题，但是就是很容易错，编码困难.
要跟据level的奇偶性，分别讨论,有兴趣可以尝试一下,我没成功......

google 了以下发现了一个很好的想法,以下是我跟据那个想法写的递归版本
LL n, q;
int bin(LL n, LL q)
{
    if(n <= 1) return 1;
    LL k = n / 2;
    if (q > k) {
        return bin(n - k, n - q + 1);
    } else {
        return n - k + bin(k, k - q + 1);
    }
}

以如下为例，解释以下算法
     分裂  abcdefghi  时
               /\                                                              
              /  \                                                             
           ihgfe dcba                                                          
   对于一个n,k = n / 2:
   如果 q <= k,这时abcd被倒置，如果要在dcba中找d，等价于在abcd中找a
        也就是k到q的距离成为了新的q
   如果 q >  k,如果要在ihgfe中找h等价于在efghi中寻找f
        也就是k到n的距离成为了新的q

然后在体会一下上边的算法                  
                                                                               

posted on 2009-11-23 00:24 schindlerlee 阅读(1279) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理