USACO —— ariprog

Published on 2010 / 03 / 28

事隔半个月之后，又来USACO 做题了。

这道题我开始一看蛮简单，写了50来行，结果

第一次：没写NONE，第3个点挂……

第二次：第八个点time limit execeeded。

知道了，b从 1 开始 ++ 搜第8个点要5秒多……

第三次：想了一下剪枝，就是每次寻找的d 是由两个能取的数之差，再将a，b存起来，最后一个加权排序，再输出，最大的点也只要 1.804 secs。过了Congratulations!

Arithmetic Progressions

An arithmetic progression is a sequence of the form a, a+b, a+2b, …, a+nb where n=0,1,2,3,… . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p2 + q2 (where p and q are non-negative integers).

TIME LIMIT: 5 secs

PROGRAM NAME: ariprog

INPUT FORMAT

Line 1: N (3 <= N <= 25), the length of progressions for which to search

Line 2: M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

SAMPLE INPUT (file ariprog.in)

5
7

OUTPUT FORMAT

If no sequence is found, a singe line reading `NONE’. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first.

There will be no more than 10,000 sequences.

SAMPLE OUTPUT (file ariprog.out)

1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24

我的代码

/*
ID: 这个被我删了，你猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜猜……
PROG: ariprog
LANG: C
*/

#include<stdio.h>

int N, M, T, Ans, Maxnum, Out[10000][2], Num[100000];
char Hash[125001];

int Fun(int a, int b) {
    if (a + (N - 1) * b > Maxnum) return 0;
    int var, re;
    for (re = 1, var = 1; var < N; var++)
        if (Hash[var * b + a] == 0) {
            re = 0;
            break;
        }
    return re;
}

void Qsort(int st, int en, int *line) {
    int a, b, c;
    a = st;
    b = en;
    c = line[st];
    while (a < b) {
        while (a < b) {
            if (line[b] < c) {
                line[a] = line[b];
                break;
            }
            b--;
        }
        while (a < b) {
            if (line[a] > c) {
                line[b] = line[a];
                break;
            }
            a++;
        }
    }
    line[a] = c;
    if (st < a - 1) Qsort(st, a - 1, line);
    if (a + 1 < en) Qsort(a + 1, en, line);
}

void Sort(int st, int en) {
    int a, b, c, d;
    c = st;
    d = en;
    a = Out[c][0];
    b = Out[c][1];
    while (c < d) {
        while (c < d) {
            if (Out[d][1] < b) {
                Out[c][0] = Out[d][0];
                Out[c][1] = Out[d][1];
                break;
            }
            else if (Out[d][1] == b && Out[d][0] < a) {
                Out[c][0] = Out[d][0];
                Out[c][1] = Out[d][1];
                break;
            }
            d--;
        }
        while (c < d) {
            if (Out[c][1] > b) {
                Out[d][0] = Out[c][0];
                Out[d][1] = Out[c][1];
                break;
            }
            else if (Out[c][1] == b && Out[c][0] > a) {
                Out[d][0] = Out[c][0];
                Out[d][1] = Out[c][1];
                break;
            }
            c++;
        }
    }
    Out[d][0] = a;
    Out[d][1] = b;
    if (st < d - 1) Sort(st, d - 1);
    if (d + 1 < en) Sort(d + 1, en);
}

int main() {
    FILE *fs, *fp;
    fs = fopen("ariprog.in", "r");
    fp = fopen("ariprog.out", "w");

    fscanf(fs, "%d", &N);
    fscanf(fs, "%d", &M);

    int a, b, c, d;

    Maxnum = M * M * 2;

    for (a = 0; a <= M; a++)
        for (b = a; b <= M; b++)
            if (Hash[a * a + b * b] == 0) {
                Num[T] = a * a + b * b;
                Hash[a * a + b * b] = 1;
                T++;
            }

    Qsort(0, T - 1, Num);

    for (c = 0; c < T; c++)
        for (a = Num[c], d = c + 1; d < T; d++) {
            b = Num[d] - a;
            if (Fun(a, b) == 1) {
                Out[Ans][0] = a;
                Out[Ans][1] = b;
                Ans++;
            }
        }

    if (!Ans)
        fprintf(fp, "NONE\n");
    else {
        Sort(0, Ans - 1);
        for (a = 0; a < Ans; a++)
            fprintf(fp, "%d %d\n", Out[a][0], Out[a][1]);
    }

    fclose(fs);
    fclose(fp);
    return 0;
}

测试结果

TASK: ariprog
LANG: C
Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.000 secs, 2500 KB]
Test 2: TEST OK [0.000 secs, 2500 KB]
Test 3: TEST OK [0.000 secs, 2500 KB]
Test 4: TEST OK [0.000 secs, 2500 KB]
Test 5: TEST OK [0.011 secs, 2500 KB]
Test 6: TEST OK [0.065 secs, 2500 KB]
Test 7: TEST OK [0.778 secs, 2500 KB]
Test 8: TEST OK [1.804 secs, 2500 KB]
Test 9: TEST OK [1.771 secs, 2500 KB]
All tests OK.
Your program (‘ariprog’) produced all correct answers! This is your submission #3 for this problem. Congratulations!