USACO : Arithmetic Progressions



/*
ID: tausiq11
PROG: ariprog
LANG: C++
*/

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#define INT_MAX 2147483647
#define INT_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL unsigned long long
using namespace std;

bool biSquare [4 * (251 * 251)];
int q_val [4 * (251 * 251)];

struct output {
	int start;
	int differnce;
} o [10000 + 5];

int in = 0;

bool cmp (output a, output b)
{
	if ( a.differnce < b.differnce ) return true;
	if ( a.differnce == b.differnce && a.start < b.start ) return true;
	return false;
}

int main(int argc, char **argv) {
	freopen ("ariprog.in", "r", stdin);
	freopen ("ariprog.out", "w", stdout);

	memset (biSquare, false, sizeof (biSquare));
	for ( int i = 0; i < 4 * (251 * 251); i++ )
		q_val [i] = N;
	// generate all biSquare
	for ( int p = 0; p <= 250; p++ ) {
		for ( int q = p; q <= 250; q++ ) {
			biSquare [p * p + q * q] = true;
			if ( q_val [p * p + q * q] > q ) q_val [p * p + q * q] = q;
		}
	}

	int n, m;
	scanf ("%d %d", &n, &m);

	int limit = 2 * m * m;

	for ( int a = 0; a <= limit; a++ ) {
		if ( !biSquare [a] ) continue;
		for ( int diff = 1; a + diff * (n - 1) <= limit; diff++  ) {
			int next = a + diff;
			int len = 1;
			while ( biSquare [next] && len < n && q_val [next] <= m ) {
				len++;
				next += diff;
			}
			if ( len == n ) {
				o [in].start = a;
				o [in].differnce = diff;
				in++;
			}
		}
	}

	sort (o, o + in, cmp);

	for ( int i = 0; i < in; i++ ) {
		printf ("%d %d\n", o [i].start, o [i].differnce);
	}

	if ( in == 0 ) printf ("NONE\n");

	return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

5 thoughts on “USACO : Arithmetic Progressions

  1. USER: [tausiq11]
    TASK: ariprog
    LANG: C++
    
    Compiling...
    Compile: OK
    
    Executing...
       Test 1: TEST OK [0.000 secs, 4196 KB]
       Test 2: TEST OK [0.000 secs, 4196 KB]
       Test 3: TEST OK [0.022 secs, 4196 KB]
       Test 4: TEST OK [0.011 secs, 4196 KB]
       Test 5: TEST OK [0.022 secs, 4196 KB]
       Test 6: TEST OK [0.086 secs, 4196 KB]
       Test 7: TEST OK [0.940 secs, 4196 KB]
       Test 8: TEST OK [1.847 secs, 4196 KB]
       Test 9: TEST OK [1.598 secs, 4196 KB]
    
    All tests OK.
    Your program ('ariprog') produced all correct answers!  This is your
    submission #4 for this problem.  Congratulations!
    
  2. Hi, excuse me but I have one really basic question:

    in the test data n=3, m=2 why 1 2 isn’t included in the answer?

  3. For n = 5 and m = 7 why 1 24 isn’t a valid answer. (1 = 1*1 + 0, 25=5*5+0, 49 = 7*7 + 0, 73 = 8*8 + 3*3, 97 = 9*9 + 4*4)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s