I was trying to figure this out on my own for some time but i could not so I need your help.↵
↵
[problem:2072E]↵
↵
So the question wants you to find pairs where either |deltax| or |deltay| is zero. At first, i tried to find two numbers a and b such that a(a-1) / 2 + b(b-1) / 2 = k but there are numbers that are not a sum of two triangular numbers. Famously gauss proved that any number can be expressed as a sum of upto 3 triangular numbers a, b, c.↵
↵
So this question boils down to find non-negative integers a, b, c such that a(a-1)/2 + b(b-1)/2 + c(c-1)/2 = k and a+b+c <= 500.↵
↵
Since, k <= 10^5, a + b + c will be less than 500, because if we solve a(a-1) / 2 <= 10^5, we get a = 12 and following my code b will be 23 and c will be 447, hence 447 + 23 + 12 is 482 which is <= 500.↵
↵
I implemented this below:↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define peace "\n"↵
#define ll long long↵
#define vi vector<int>↵
#define vl vector<long long>↵
#define vvi vector<vector<int>>↵
#define vvl vector<vector<long long>>↵
↵
using namespace std;↵
↵
const int MAXN = 1e5;↵
↵
vi Tri;↵
↵
vi bestl(MAXN+1, -1);↵
vi bestr(MAXN+1, -1);↵
vector<bool> hasrep(MAXN+1, false);↵
↵
void precompute() {↵
for (int i = 0; (i*(i-1)/2) <= MAXN; i++) {↵
Tri.push_back(i*(i-1) / 2);↵
}↵
↵
for (int l = 0; l < Tri.size(); l++) {↵
for (int r = l; r < Tri.size(); r++) ↵
{↵
int s = Tri[l] + Tri[r];↵
if (s > MAXN) break;↵
if (!hasrep[s] || (l+r) < (bestl[s]+bestr[s])) {↵
hasrep[s] = true;↵
bestl[s] = l;↵
bestr[s] = r;↵
}↵
}↵
}↵
}↵
↵
int main()↵
{↵
precompute();↵
↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
while(t--)↵
{↵
int k; cin >> k;↵
↵
int a = -1, b = -1, c = -1;↵
bool found = false;↵
↵
for (int i = 0; i < Tri.size(); i++) ↵
{↵
if (Tri[i] > k) break;↵
int target = k - Tri[i];↵
↵
if (!hasrep[target]) continue;↵
↵
int l = bestl[target];↵
int r = bestr[target];↵
↵
if (i + l + r <= 500) { ↵
a = i;↵
b = l;↵
c = r;↵
break; ↵
}↵
}↵
↵
cout << a + b + c << peace;↵
↵
for (int i = 0; i < a; i++) cout << (int)1e8 << " " << i << peace;↵
for (int i = 0; i < b; i++) cout << (int)4e7 << " " << i + (int)1e4 << peace;↵
for (int i = 0; i < c; i++) cout << i + (int)-1e4 << " " << (int)-1e8 << peace; ↵
}↵
return 0;↵
}↵
~~~~~↵
↵
Its getting wrong answer on test case 5 with verdict _wrong answer Integer parameter [name=n] equals to -3, violates the range [0, 500] (test case 11)_ Test Case 11 — k = 99011↵
↵
Link to the submission — ↵
[submission:378264114]↵
↵
[problem:2072E]↵
↵
So the question wants you to find pairs where either |deltax| or |deltay| is zero. At first, i tried to find two numbers a and b such that a(a-1) / 2 + b(b-1) / 2 = k but there are numbers that are not a sum of two triangular numbers. Famously gauss proved that any number can be expressed as a sum of upto 3 triangular numbers a, b, c.↵
↵
So this question boils down to find non-negative integers a, b, c such that a(a-1)/2 + b(b-1)/2 + c(c-1)/2 = k and a+b+c <= 500.↵
↵
Since, k <= 10^5, a + b + c will be less than 500, because if we solve a(a-1) / 2 <= 10^5, we get a = 12 and following my code b will be 23 and c will be 447, hence 447 + 23 + 12 is 482 which is <= 500.↵
↵
I implemented this below:↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
#define peace "\n"↵
#define ll long long↵
#define vi vector<int>↵
#define vl vector<long long>↵
#define vvi vector<vector<int>>↵
#define vvl vector<vector<long long>>↵
↵
using namespace std;↵
↵
const int MAXN = 1e5;↵
↵
vi Tri;↵
↵
vi bestl(MAXN+1, -1);↵
vi bestr(MAXN+1, -1);↵
vector<bool> hasrep(MAXN+1, false);↵
↵
void precompute() {↵
for (int i = 0; (i*(i-1)/2) <= MAXN; i++) {↵
Tri.push_back(i*(i-1) / 2);↵
}↵
↵
for (int l = 0; l < Tri.size(); l++) {↵
for (int r = l; r < Tri.size(); r++) ↵
{↵
int s = Tri[l] + Tri[r];↵
if (s > MAXN) break;↵
if (!hasrep[s] || (l+r) < (bestl[s]+bestr[s])) {↵
hasrep[s] = true;↵
bestl[s] = l;↵
bestr[s] = r;↵
}↵
}↵
}↵
}↵
↵
int main()↵
{↵
precompute();↵
↵
ios_base::sync_with_stdio(false);↵
cin.tie(NULL);↵
↵
int t;↵
cin >> t;↵
while(t--)↵
{↵
int k; cin >> k;↵
↵
int a = -1, b = -1, c = -1;↵
bool found = false;↵
↵
for (int i = 0; i < Tri.size(); i++) ↵
{↵
if (Tri[i] > k) break;↵
int target = k - Tri[i];↵
↵
if (!hasrep[target]) continue;↵
↵
int l = bestl[target];↵
int r = bestr[target];↵
↵
if (i + l + r <= 500) { ↵
a = i;↵
b = l;↵
c = r;↵
break; ↵
}↵
}↵
↵
cout << a + b + c << peace;↵
↵
for (int i = 0; i < a; i++) cout << (int)1e8 << " " << i << peace;↵
for (int i = 0; i < b; i++) cout << (int)4e7 << " " << i + (int)1e4 << peace;↵
for (int i = 0; i < c; i++) cout << i + (int)-1e4 << " " << (int)-1e8 << peace; ↵
}↵
return 0;↵
}↵
~~~~~↵
↵
Its getting wrong answer on test case 5 with verdict _wrong answer Integer parameter [name=n] equals to -3, violates the range [0, 500] (test case 11)_ Test Case 11 — k = 99011↵
↵
Link to the submission — ↵
[submission:378264114]↵
