Cod sursa(job #1344397)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 16 februarie 2015 18:13:09
Problema Progresie Scor 0
Compilator cpp Status done
Runda Arhiva ICPC Marime 1.4 kb
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
typedef int ull;


ull find_smallest_larger(ull n, vector<ull> & squares) {
	int index = 0;
	while (n > squares[index]) {
		index++;
	}
	return squares[index];
}



int main(int argc, char * argv[]) {

	vector<ull> squares;
	int sq = 0;
	while (sq * sq <= 1000000) {
		squares.push_back(sq * sq);
		sq++;
	}
	FILE * i = fopen("progresie.in", "r");
	FILE * o = fopen("progresie.out", "w");
	int T, N, R;
	fscanf(i, "%d\n", &T);
	while (T--) {
		fscanf(i, "%d %d\n", &N, &R);
		ull tr = 1;
		ull incr = tr;
		ull count = 0;
		ull first_square = tr;
		while (true) {
			
			ull	sq = find_smallest_larger(incr, squares);
			if (tr == incr) {
				first_square = sq;
			}
			if (incr == sq) {
				count++;
				incr += R;
				if (count >= N) {
					printf("%d\n",tr);
					fprintf(o, "%d\n", tr);
					break;
				}
			}
			else if (incr >= sq - sqrt(sq) + 1 && incr <= sq) {
				count++;
				incr += R;
				if (count >= N) {
					printf("%d\n", tr);
					fprintf(o, "%d\n", tr);
					break;
				}
			}
			else {
				if (tr == first_square) {
					ull sqr = find_smallest_larger(tr + 1, squares);
					tr = sqr - sqrt(sqr) + 1;
				}
				else {
					tr++;
				}
				incr = tr;
				count = 0;
			}
		}
	}
	return 0;
}