• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            uva 107 - The Cat in the Hat

               這是一個很神的數學題吧。基本上過這個題的很多都會wa10多次,而且這個題好像簡單的枚舉其中的一個指數值都能過,可能是
            數據量比較小。
               但是,這個題還是有數學的解法的。但是,即使找到了這個正確的解法,過題的話,也是一件很困難的事情。題意大致如下:一只貓,
            高度為H,戴了一個帽子,帽子里面有N只貓(N是常數,且未知),同樣帽子里面的貓也戴了帽子,但是這些貓的高度變成了H / (N + 1),
            會向下取整。以此遞歸下去,直到最后的貓的高度都為1為止。現在,給出H和高度為1的貓的數量。要求的是高度大于1的貓的數量,
            以及所有貓的高度之和。
               很別扭吧。通過上面的信息,得出2個式子。假設one代表為高度為1的貓的數量。one = N的n次。H >= (N + 1)的n次。注意第
            二個式子不一定取等號,因為很多時候都是不能整除的。現在要求N和n。2個方程解2個未知數,應該能解出來。但是,注意的是其中
            一個還是不等式。。。
               指數關系很多時候會轉換為對數的關系。所以,繼續求對數,有lgH >= n * lg(N + 1)。其中,由第一個式子可以得到n = lg(one)
            / lg(N)。那么最終轉換為:lgH >= (lg(one) / lgN) * lg(N + 1)。換個形式就是lgH / lg(One) >= lg(N + 1) / lgN。現在,已經很
            清晰了。因為,函數lg(N + 1) / lg(N) 是單調遞減的。看到單調的函數,馬上就會知道可以二分了。意思是,我們可以二分出一個N讓
             lg(N + 1) / lgN 最接近lgH / lg(One),而且是小于lgH / lg(One)的。剩下的工作就只是求和而已了。
               寫二分的時候,有一個地方可以注意一下。因為 lg(N + 1) / lgN 可能會出現除數為0的情況,所以可以進一步轉換為lgH * lgN >=
            lg(N + 1) * lg(one)
            。 也是求一個N讓上面那個不等式2邊的值最接近,而且右邊小于左邊。
               能很快寫對這個題真不是件容易的事情。。。

               代碼如下:
            #include <stdio.h>
            #include <math.h>

            int main()
            {
                int nInitH, nOnes;
                int nN, n;

                while (scanf("%d%d", &nInitH, &nOnes), nInitH + nOnes)
                {
                    int nBeg = 1;
                    int nEnd = nOnes;
                    int nMid;
                
                    while (nBeg <= nEnd)
                    {
                        nMid = (nBeg + nEnd) / 2;
                        
                        double fRes = log10(nInitH) * log10(nMid);
                        double fTemp = log10(nMid + 1) * log10(nOnes);
                        if (fabs(fRes - fTemp) < 1e-10)
                        {
                            //printf("Find nN:%d\n", nMid);
                            nN = nMid;
                            break;
                        }
                        else if (fTemp > fRes)
                        {
                            nBeg = nMid + 1;
                        }
                        else
                        {
                            nEnd = nMid - 1;
                        }
                    }
                    
                    n = floor(log10(nInitH) / log10(nN + 1) + 1e-9);
                    //printf("nN:%d, n:%d\n", nN, n);

                    int nSum = 0;
                    int nLazy = 0;
                    int nNum = 1;
                    for (int i = 0; i <= n; ++i)
                    {
                        nSum += nNum * nInitH;
                        nLazy += nNum;
                        nNum *= nN;
                        nInitH /= (nN + 1);
                    }
                    
                    printf("%d %d\n", nLazy - nOnes, nSum);
                }

                return 0;
            }

               

            posted on 2012-05-07 16:54 yx 閱讀(1695) 評論(0)  編輯 收藏 引用 所屬分類: 數學題

            <2012年3月>
            26272829123
            45678910
            11121314151617
            18192021222324
            25262728293031
            1234567

            導航

            統計

            公告

            常用鏈接

            留言簿(3)

            隨筆分類

            隨筆檔案

            me

            好友

            同學

            網友

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            国产午夜免费高清久久影院 | 亚洲国产成人久久精品影视| 久久人人爽人人爽人人片av麻烦| 狠狠综合久久综合88亚洲| 伊人久久大香线蕉无码麻豆| 久久人妻少妇嫩草AV无码专区| 久久电影网一区| 久久久国产打桩机| 精品国产一区二区三区久久蜜臀| 久久一区二区三区免费| 久久亚洲精品中文字幕| 9999国产精品欧美久久久久久| 久久天天躁狠狠躁夜夜avapp| 人人狠狠综合久久亚洲婷婷| 久久久久久精品久久久久| 中文字幕一区二区三区久久网站 | 久久精品国产清自在天天线| 66精品综合久久久久久久| 日韩精品久久无码人妻中文字幕| 久久天天躁狠狠躁夜夜不卡| 久久精品国产亚洲AV高清热| 久久久久se色偷偷亚洲精品av| 精品免费久久久久国产一区| AV狠狠色丁香婷婷综合久久| 77777亚洲午夜久久多人| 无夜精品久久久久久| 国内精品欧美久久精品| 久久青青草原国产精品免费 | 狠狠人妻久久久久久综合蜜桃| 久久综合给合久久狠狠狠97色 | 精品国产福利久久久| 国产婷婷成人久久Av免费高清| 亚洲AV无码久久寂寞少妇| 亚洲精品综合久久| 亚洲欧美精品一区久久中文字幕| 久久久久黑人强伦姧人妻| 国产精品久久久久乳精品爆| 99久久精品费精品国产 | 久久久久久久波多野结衣高潮| 人妻少妇精品久久| 成人久久免费网站|