Skip to content
{{ message }}

Instantly share code, notes, and snippets.

# vlad-shatskyi/e75.cpp

Created Aug 10, 2012
Problem 75
 #include #include #include #include #include #include #include using namespace std; const long limit = 1500000; mutex mtx; vector squares; map used_perimeters; void InitializeSquares(){ for (long i = 0; i <= limit; ++i) { squares.push_back(i*i); } } void FindTriangles(long start_position, long stop_position){ /*Seeks right triangles whose sides are integers and add their perimeters to the map. Perimeter must be less or equal to 'limit'. Searches hypotenuse and longer catet in the vector of squares and checks if the second catet is there too. */ auto start = begin(squares) + start_position; auto stop = begin(squares) + stop_position; //c (hypotenuse) can't be longer than half of perimeter, so we have to search only up to squares[limit/2] for (auto c = start; c < stop; ++c) { //Print every thousandth index to estimate running time. if ((c - begin(squares))%1000==0){ mtx.lock(); cout << "Debug: " << c - begin(squares) << endl; mtx.unlock(); } //b must be less than c. for (auto b = begin(squares) + 1; b < c; ++b) { //And a less than b. if (binary_search(begin(squares)+1, b, *c - *b)) { auto a = find(begin(squares)+1, b, *c - *b); //Sum indexes if ((a-begin(squares)) + (b - begin(squares)) + (c - begin(squares)) <= limit) { mtx.lock(); ++used_perimeters[(a-begin(squares)) + (b - begin(squares)) + (c - begin(squares))]; mtx.unlock(); } } } } } int main(){ InitializeSquares(); thread t1(FindTriangles,1,340000); thread t2(FindTriangles,340000,530000); thread t3(FindTriangles,530000,690000); thread t4(FindTriangles,690000,750000); t1.join(); t2.join(); t3.join(); t4.join(); long answer = 0; for (auto i = begin(used_perimeters); i != end(used_perimeters); ++i) { if (i->second==1) { ++answer; } //Print perimeters along with quantity of possible triangles for debugging purposes. cout << i->first << ": " << i->second << endl; } cout << answer << endl; return 0; }
to join this conversation on GitHub. Already have an account? Sign in to comment