USACO Training>My Training>Section 1.4>Arithmetic Progressions

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

Solution (Me)


/*
ID: sgospod1
PROG: ariprog
LANG: C++
*/
#include <stdio.h>
#include <string.h> 
#include <time.h> 
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <vector>

/*#define STANDARD_INPUT*/
/*#define PRINT_DEBUG*/

#define MAX_NUMBER 125001 /* (250 pow 2) * 2 */

using namespace std;

int N; /* 3 <= N <= 25 */
int M; /* 1 <= M <= 250 */
bool found = false;
char Map[MAX_NUMBER];
int Set[21047];
int MaxNum = 0;
int SetCount = 0;

#ifdef PRINT_DEBUG
#include <sys/timeb.h>
/*ofstream log ("log.out");*/
#endif    


int CompareNum (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

void GenerateSet()
{
    for(int x=0; x<=M; x++)
    {
        for(int y=x; y<=M; y++)
        {
            int num = x*x + y*y;
            if(Map[num]) continue;
            Map[num] = 1;
            Set[SetCount++] = num;
        }
    }
    qsort(Set, SetCount,sizeof(int),CompareNum);

    MaxNum = M*M*2;
}

int main()
{
#ifdef PRINT_DEBUG
    struct _timeb timebuf;
    char currtime[26];
    _ftime_s(&timebuf); 
    ctime_s( currtime, 26, &(timebuf.time));
    cerr << "Start time: " << setw(19) << currtime <<  "." << timebuf.millitm << endl;
#endif
#ifdef STANDARD_INPUT
    istream &fin = cin;
    ostream &fout = cout;
#else
    ofstream fout ("ariprog.out");
    ifstream fin ("ariprog.in");
#endif
    assert(fin != NULL && fout != NULL);

    memset(Map, 0, MAX_NUMBER);

    fin >> N >> M;

    GenerateSet();

#ifdef PRINT_DEBUG
    /*for(int i=0; i<=MaxNum; i++)
        if(Set[i]==1) log << i << endl;*/
#endif    

    int n, count, base, end;

    for(int step=1; step<=MaxNum; step++)
    {
        int limit = MaxNum - (N-1)*step;
        if(limit<0) break;
        for(int num = 0; num<SetCount; num++)
        {
            base = Set[num];
            if(base>limit) break;
            count = 1;
            end = base + (N-1)*step;
            if(!Map[end]) continue;
            count++;
            n = base + step;

            while(n<=MaxNum)
            {
                if(!Map[n]) break;
                count++;
                if(count==N) 
                { 
                    fout << base << " " << step << endl;
                    found=true;
                    break; 
                }
                n += step;
            }
        }
    }


    if(!found) fout << "NONE" << endl;

#ifdef PRINT_DEBUG
    _ftime_s(&timebuf); 
    ctime_s( currtime, 26, &(timebuf.time));
    cerr << "End time  : " << setw(19) << currtime <<  "." << timebuf.millitm << endl;
#endif
    return 0;
}

All solutions

Tests
Input Output