Problem J

Opening Doors

21th June!! Holidays at last!!

That's what everyone in the school thought when the bell rang. It was time to leave the class and go away forever (or until September). Dima was running to the exit when he saw that paper on the wall:

Don't forget to unlock all the lockers so that we can clean them in summer.
The principal.

Oh, no! Dima forgot to unlock it! So he had to go to the corridor where lockers were. When he got there, all the lockers had been already unlocked. Some of them were open and some of them were closed. Lockers were numbered from 1 to 90 (the number of boys in the school) and he had the last one. So he walked along the long corridor. While he reached his locker, he started to think why some of the doors were open and some closed. Then he invented a method to keep some open and some closed:

Once all the lockers were unlocked, the boy with locker number 1 opened all doors. Then the boy with locker number 2 closed the doors multiple of 2. Then the boy with locker number 3 changed the status of all doors multiple of 3 (he opens doors 6,12...and he closes doors 3, 9...)...and until everyone, including Dima, had done so.

Now he wants to know whether that was what happened or not. As a first-sight method, he wants to see if the door with the biggest number that is open matches the door with the biggest number that keeps open using his method. That's where he needs your help. He could do it by hand, but he also wants to check it next year (and the number of students may change), so he asked you for a program that simulates it for any number of students.

Each line in the input will contain a single number N (1≤N≤10^100), indicating the number of boys in the school (you never know what the number of students will be if Earth population keeps growing...).

Input will be terminated by a test case with N=0. That line shouldn't be processed. For each line in the input, write a line with the number of the door with the biggest number that keeps open.

Sample Input

Sample Output

Problem author: Carlos M. Casas Cuadrado

Problem submitter: Carlos M. Casas Cuadrado

Problem solution: Carlos M. Casas Cuadrado

使用中國開方法

將之前的代碼重新修正。

// 0.068 s

#include <stdio.h>
#include <string.h>

int main() {
    char s[1024];
    while(scanf("%s", s) == 1) {
        if(!strcmp(s, "0"))
            break;
        int len = strlen(s);
        int x[100] = {}, y[100] = {};
        int i, j;
        for(i = 0, j = len-1; j >= 0; i++) {
            x[i] = s[j]-'0';
            if(j-1 >= 0)    x[i] = x[i] + (s[j-1]-'0')*10;
            if(j-2 >= 0)    x[i] = x[i] + (s[j-2]-'0')*100;
            if(j-3 >= 0)    x[i] = x[i] + (s[j-3]-'0')*1000;
            j -= 4;
        }
        int xlen = len, ylen = 0;
        long long ret[100] = {}, retidx = 0;
        while(xlen >= 0 && x[xlen] == 0) xlen--;
        for(j = (len-1)/8, i = j*2; j >= 0; j--, i -= 2) {
            ylen++;
            for(int p = ylen; p >= 1; p--)
                y[p] = y[p-1];
            y[0] = 0;
            if(xlen < j) {
                ret[retidx++] = 0;
                continue;
            }
            int l = 0, r = 9999, p;
            int z[100] = {}; // z = (y*10 + p)*p;
            while(l <= r) {
                p = (l+r)/2;
                y[0] += p;
                z[0] = 0;
                for(int q = 0; q <= ylen+5; q++) {
                    z[q] += p*y[q];
                    z[q+1] = z[q]/10000;
                    z[q] %= 10000;
                }
                int chflag = 0;
                for(int q = ylen+5; q >= 0; q--) {
                    if(z[q] > x[i+q]) {
                        chflag = 1;
                        break;
                    } else if(z[q] < x[i+q]) {
                        chflag = 0;
                        break;
                    }
                }
                y[0] -= p;
                if(chflag)
                    r = p-1;
                else
                    l = p+1;
            }
            p = l-1;
            y[0] = p;
            z[0] = 0;
            for(int q = 0; q <= ylen+5; q++) {
                z[q] += p*y[q];
                z[q+1] = z[q]/10000;
                z[q] %= 10000;
            }
            for(int q = ylen+5; q >= 0; q--)
                x[i+q] -= z[q];
            for(int q = 0; q <= ylen+5; q++) {
                while(x[i+q] < 0)
                    x[i+q] += 10000, x[i+q+1]--;
            }
            y[0] += p;
            for(int q = 0; q <= ylen+5; q++) {
                if(y[q] >= 10000) {
                    y[q+1] += y[q]/10000;
                    y[q] %= 10000;
                }
            }
            ylen += 5;
            while(ylen >= 0 && y[ylen] == 0)    ylen--;
            while(xlen >= 0 && x[xlen] == 0)    xlen--;
            ret[retidx++] = p;
        }
        long long ans[100] = {};
        int p, q;
        for(i = retidx-1, p = 0; i >= 0; i--, p++) {
            if(ret[i])
            for(j = retidx-1, q = 0; j >= 0; j--, q++) {
                ans[p+q] += ret[i]*ret[j];
            }
        }
        retidx <<= 1;
        retidx++;
        for(i = 0; i < retidx; i++) {
            if(ans[i] >= 10000) {
                ans[i+1] += ans[i]/10000;
                ans[i] %= 10000;
            }
        }
        while(ans[retidx] == 0) retidx--;
        printf("%lld", ans[retidx]);
        for(i = retidx-1; i >= 0; i--)
            printf("%04lld", ans[i]);
        puts("");
    }
    return 0;
}

我要檢舉

#10606#Opening Doors#大數開根號

台長： Morris

您可能對以下文章有興趣

[UVA][dp] 12034 - Race

[UVA] 886 - Named Extension Dialing

[UVA] 153 - Permalex

[UVA] 11210 - Chinese Mahjong

人氣(2,100) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][dp] 1096 - The Islands
此分類上一篇:[UVA][搜索] 10605 - Mines For Diamonds

回應(0)