周公解囊

今天带来的是SPOJ 第302题，在cantor枚举中求给定位置的值，难度排名倒数第十一，共有2328人参与，4543个程序被提交，正确率为62.2%

原题

One of the famous proofs of modern mathematics is Georg Cantor's demonstration that the set of rational numbers is enumerable. The proof works by using an explicit enumeration of rational numbers as shown in the diagram below.

1/1 1/2 1/3 1/4 1/5 ...
2/1 2/2 2/3 2/4
3/1 3/2 3/3
4/1 4/2
5/1

In the above diagram, the first term is 1/1, the second term is 1/2, the third term is 2/1, the fourth term is 3/1, the fifth term is 2/2, and so on.

Input

The input starts with a line containing a single integer t <= 20, the number of test cases. t test cases follow.

Then, it contains a single number per line.

Output

You are to write a program that will read a list of numbers in the range from 1 to 10^7 and will print for each number the corresponding term in Cantor's enumeration as given below.

Example

Input:
3
3
14
7

Output:
TERM 3 IS 2/1
TERM 14 IS 2/4
TERM 7 IS 1/4

此题十分之简单，首先我们需要找到n所处斜线的位置，注意到第K条斜线上共有k个数，因此前K条斜线上共有1+2+3+。。。+k=k(k+1)/2个数，因此给定标号n，它大致应该在第sqrt（2n）附近的斜线上，假定为第p条斜线

设n对应的分数为i/j, 则i+j=p+1，而视p的奇偶性，i或j中的一个应等于n-p(p-1)/2，如此即可求得i,j

以下是C的实现：

#include <math.h>

int main()
    {
    int t;
    long n,possible,sum,i,j;
    scanf("%d", &t);
    while (t--)
        {
        scanf("%d", &n);
        possible=sqrt(n*2.0);
        while (possible*(possible+1)>=2*n)
            {
            possible--;
            }
        sum=possible*(possible+1)/2;
        if (possible%2)
            {
            i=n-sum;
            j=possible+2-i;
            }
        else
            {
            j=n-sum;
            i=possible+2-j;
            }
        printf("TERM %d IS %d/%d\n", n, i, j);
        }
    }

今天带来的是SPOJ 第74题，求一个数的所有约数之和，难度排名倒数第十，共有2481人参与，18178个程序被提交，正确率为21.6%

原题

Given a natural number n (1 <= n <= 500000), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

Example

Sample Input:
3
2
10
20

Sample Output:
1
8
22

不论求约数还是分解质因数，复杂度都很高，且在多个录入数据间需要重复计算，因此我们可以逆向思考该问题，假定n的约数只和为f（n），则我们从1开始，对数p的所有倍数pk，将f（pk）+=p，这样遍历一次，即为结果

以下是一个C实现

int main()
    {
    long result[500000]={0};
    long i, j, p, t, n;
    for (i=0;i<500000;i++)
        {
        p=i+1;
        for (j=2*p; j<=500000; j+=p)
            {
            result[j-1]+=p;
            }
        }
    scanf("%d", &t);
    while (t--)
        {
        scanf("%d", &n);
        printf("%d\n", result[n-1]);
        }
    return 0;
    }

今天带来的是SPOJ 第1112题，给定一条由离散点组成的折线，根据坐标求序号，难度排名倒数第九，共有2502人参与，6076个程序被提交，正确率为55.6%

原题

Starting from point (0,0) on a plane, we have written all non-negative integers 0, 1, 2,... as shown in the figure. For example, 1, 2, and 3 has been written at points (1,1), (2,0), and (3, 1) respectively and this pattern has continued.

 

You are to write a program that reads the coordinates of a point (x, y), and writes the number (if any) that has been written at that point. (x, y) coordinates in the input are in the range 0...10000.

 

Input

The first line of the input is N, the number of test cases for this problem. In each of the N following lines, there is x, and y representing the coordinates (x, y) of a point.

 

Output

For each point in the input, write the number written at that point or write No Number if there is none.

 

Example

Input:
3
4 2
6 6
3 4

Output:
6
12
No Number

其实就是找规律

首先我们注意到这是两条折线，所以给定的坐标必须满足直线方程才有序号，直线方程为y=x以及y=x-2；

其次我们把每4个点看成一个组，则每增加1个组，y增加2；因此4*（y/2）即为当前组之前共有多少个点，而当前组中给定点的序号取决于y的奇偶性机器与x的差值。

以下是c的实现：

int main()
    {
    int n,x,y,diff,result;
    scanf("%d", &n);
    while (n--)
        {
        scanf("%d %d", &x, &y);
        diff=x-y;
        if (diff==0 || diff==2)
            {
            result=diff+4*(y/2)+y%2;
            printf("%d\n", result);
            }
        else
            {
            printf("No Number\n");           
            }           
        }
    return 0;
    }

 

今天带来的是SPOJ 第5题，找出给定范围内的最小回文数，难度排名倒数第八，共有2663人参与，25321个程序被提交，正确率为17.0%

原题

A positive integer is called a palindrome if its representation in the decimal system is the same when read from left to right and from right to left. For a given positive integer K of not more than 1000000 digits, write the value of the smallest palindrome larger than K to output. Numbers are always displayed without leading zeros.

Input

The first line contains integer t, the number of test cases. Integers K are given in the next t lines.

Output

For each K, output the smallest palindrome larger than K.

Example

Input:
2
808
2133

Output:
818
2222

这是一道很恶心的题，它让我联想起了一些高中时代的，充满了各种分情况讨论，复杂，繁琐，毫无美感的数学练习题。

首先在给定位数下最大的10进制回文数为9999......因此，只有在给定9999....的情况下需要升位至100....01，否则我们总可以增大到回文数9999....

其次，在所有情况下最简单的是个位数，只需要直接+1即可

最后，我们把给定数K的左半边复制到右半边，得到新数P,如果P已然大于K，那么P必定是大于K的最小回文数；如若P小于K，则我们增加P至下一回文数，并与K比较，由回文数的性质可知，从该数的中间开始增加是正确的做法。这里我们需要分别考虑lgP的奇偶性以及某一位的数字为9需要进位的情况。。。。。

以下是python的实现，基本不忍卒读。。。

t=input()
while t:
    k=raw_input()
    digits=len(k)
    i=0
    while i<digits and k[i]=='9':
        i+=1
    if i==digits:
        print long(k)+2
    else:
        if digits==1:
            print int(k)+1
        else:
            k=list(k)
            left=digits/2-1
            right=digits-digits/2
            p=k[:right]+k[left::-1]
            if p>k:
                print ''.join(p)
            else:
                if right-left==2 and p[left+1]!='9':
                    p[left+1]=str(int(p[left+1])+1)
                    print ''.join(p)
                else:
                    if right-left==2:
                        p[left+1]='0'
                    while p[right]=='9':
                        p[right]='0'
                        p[left]='0'
                        right+=1
                        left-=1
                    p[right]=str(int(p[right])+1)
                    p[left]=p[right]
                    print ''.join(p)
    t-=1

 

 

今天带来的是SPOJ 第400题，把一个扭来扭去的字符串恢复成原样，难度排名倒数第七，共有2963人参与，5939个程序被提交，正确率为60.0%

原题

Mo and Larry have devised a way of encrypting messages. They first decide secretly on the number of columns and write the message (letters only) down the columns, padding with extra random letters so as to make a rectangular array of letters. For example, if the message is “There’s no place like home on a snowy night” and there are five columns, Mo would write down

t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x

Note that Mo includes only letters and writes them all in lower case. In this example, Mo used the character ‘x’ to pad the message out to make a rectangle, although he could have used any letter. Mo then sends the message to Larry by writing the letters in each row, alternating left-to-right and right-to-left. So, the above would be encrypted as

toioynnkpheleaigshareconhtomesnlewx

Your job is to recover for Larry the original message (along with any extra padding letters) from the encrypted one.

Input

There will be multiple input sets. Input for each set will consist of two lines. The first line will contain an integer in the range 2...20 indicating the number of columns used. The next line is a string of up to 200 lower case letters. The last input set is followed by a line containing a single 0, indicating end of input.

Output

Each input set should generate one line of output, giving the original plaintext message, with no spaces.

Example

Input:

5
toioynnkpheleaigshareconhtomesnlewx
3
ttyohhieneesiaabss
0

Output:

theresnoplacelikehomeonasnowynightx
thisistheeasyoneab

把给定的字符串想象成二维字符数组，假定共col列，则数组中的(i,j), 即字符串中的col*(i-1)+j,我们可以直接根据所给的字符串写出原串；原串为从上至下书写，所以我们按列来扫描；由于偶数列在加密时为从右至左书写，因此我们以每2行为单位，注意从奇数行到偶数行，以及从偶数行都奇数行的变幻方式的区别即可

以下是python的实现：

col=int(raw_input())
while col:
    line=raw_input()
    result=[]
    step=0
    while step<col:
        cur=step
        while cur<len(line):
            result.append(line[cur])
            cur=cur+(2*col-1)-step*2
            if cur<len(line):
                result.append(line[cur])
            cur=cur+step*2+1
        step+=1
    print ''.join(result)
    col=int(raw_input())