Morris' Blog

2011-05-29 22:37:34Morris

d923. 規律

留言 1 收藏 0 推薦 0

內容：

請觀察下列規律(此為部分數據，請自行延伸)

現在給兩正整數I、J

請輸出第I(直)行第J(橫)列之數字

(避免有網友看不到圖，提供三個空間:1 2 3)

輸入說明：

每筆測資共輸入一行

此行包含兩正整數I J(1<=I、J<=2^30)

輸出說明：

請輸出第I(直)行第J(橫)列之數字

範例輸入：

2 3

範例輸出：

提示：

出處：

(管理：B88000005)

作法 : 模擬
說真的，我不太會找規律，用暴力法慢慢切吧
大概是O(logN)

/**********************************************************************************/
/* Problem: d923 "規律" from                                                   */
/* Language: C                                                                   */
/* Result: AC (3ms, 270KB) on ZeroJudge                                          */
/* Author: morris1028 at 2011-05-29 22:22:01                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
main() {
   int i, j;
   while(scanf("%d %d", &i, &j) == 2) {
       long long t, Ans = 0;
       while(1) {
           t = 2;
           while(t < i || t < j) {
               t *= 2;
           }
           if(i == 1 && j == 1) {Ans++;break;}
           if(t / 2 >= i && t / 2 < j)
               Ans += t*t / 2, j -= t / 2;
           else if(t / 2 < i && t / 2 < j)
               Ans += t*t / 4, i -= t / 2, j -= t / 2;
           else
               Ans += t*t / 4 * 3, i -= t / 2;
       }
       printf("%lld\n", Ans);
   }
   return 0;
}

上一篇：d925. 平均高度

下一篇：d624. 燈泡問題