Why so serious? --[NKU]schindlerlee

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

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

sgu154:非常好的數(shù)論+二分題目
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的個數(shù)至于2和5的個數(shù)有關(guān)，又因為2的個數(shù)已經(jīng)多余5，所以階乘末尾
0的個數(shù)完全等價于所有數(shù)中5的個數(shù)
所以階乘末尾0的個數(shù)可以用如下函數(shù)計算
int count(int x) //count the num of 0s in x!
{
    int res = 0;
    while(x > 0) {
        res += x / 5;
        x /= 5;
    }
    return res;
}
然后題目要求末尾個數(shù)有n個0的x!中，x為多少
因為哦count函數(shù)具有單調(diào)增加的性質(zhì)，所以完全可以二分尋找符合條件的x
trick 1.n == 0 ,時答案是1
trick 2.二分出來的結(jié)果有可能應(yīng)該輸出No Solution !(具體原因自己考慮一下)

sgu175:經(jīng)典
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

讀完題之后，直覺的想法就是遞歸模擬，復(fù)雜度也對，也沒問題，但是就是很容易錯，編碼困難.
要跟據(jù)level的奇偶性，分別討論,有興趣可以嘗試一下,我沒成功......

google 了以下發(fā)現(xiàn)了一個很好的想法,以下是我跟據(jù)那個想法寫的遞歸版本
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 閱讀(1295) 評論(0) 編輯收藏引用所屬分類: 解題報告

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: zju2589 不重合的n個圓形成的區(qū)域 pku3334 二分+求多邊形面積 hdu3264 二分+求兩圓交的面積 zoj2107 最近點對，分治 pku1819 幾何+模擬不難，但是不容易寫對 codeforces contest 16 problem E 比較容易的狀態(tài)壓縮動態(tài)規(guī)劃。 2010-06-21 20:10:05 關(guān)于Aho-Corasick (AC) 自動機的三道題目 2010-06-16 12:04:40 pku3528 三維凸包 2010-06-11 00:40 spoj1182 ,dp, number theory, binary search 數(shù)位類統(tǒng)計問題 2010-06-08 23:24:36.ural1057 number theory and dp

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

Why so serious? --[NKU]schindlerlee

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

導(dǎo)航

統(tǒng)計信息

News

留言簿(5)

隨筆分類(90)

隨筆檔案(105)

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜