QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #704137 | #151. Nice Lines | TheZone | 100 ✓ | 6ms | 4004kb | C++20 | 35.2kb | 2024-11-02 19:23:15 | 2024-11-02 19:23:15 |
Judging History
answer
#include "nice_lines.h"
#include<bits/stdc++.h>
#define ll long long
#define db long double
#define ull unsigned long long
#define pb push_back
#define pii pair<int, int>
#define FR first
#define SE second
using namespace std;
const int X = 100000, lim = 10000;
const db eps = 1e-5;
vector<int> ans1, ans2;
struct Line {db k, b;};
Line calc(int id) {
db sx = (id - 1) * X + lim + lim;
db tx = id * X - lim - lim;
db sy = query(X, sx), ty = query(X, tx);
// cout << sx << ' ' << tx << endl;
db k = (sy - ty) / (sx - tx), b = (ty * sx - sy * tx) / (sx - tx);
assert(fabs(k * sx + b - sy) < eps);
// cout << k << ' ' << b << endl;
return {k, b};
}
void solve(int l, int r, Line vl, Line vr) {
if(fabs(vl.k - vr.k) < eps)return ;
db x = -(vr.b - vl.b) / (vr.k - vl.k);
db y = (vr.k * vl.b - vl.k * vr.b) / (vr.k - vl.k);
db z = query(X, x);
if(fabs(y - z) < eps) {
int a = round(x / X);
int b = round(x - a * X);
ans1.pb(a); ans2.pb(b);
return ;
}
if(r - l == 1)return ;
int mid = max(min((int)ceil(x / X), r - 1), l + 1);
Line vm = calc(mid);
solve(l, mid, vl, vm); solve(mid, r, vm, vr);
return ;
}
void solve(int subtask_id, int N) {
solve(-lim, lim + 1, calc(-lim), calc(lim + 1));
the_lines_are(ans1, ans2);
}
/*00 0
1 2 3
4 5 6
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
0
0
0
0
1
1
1
1#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
const int MAXV = 10000000;
int val[MAXV], stepp[MAXV];
int dist[MAXV];
const int MAXV2 = 30010;
vector<int> g_lol[MAXV2];
void solve() {
int n, m; cin >> n >> m;
int curv = n;
map<pair<int, int>, int> pos;
int p0, p1;
for (int i = 0; i < m; i++) {
int b, g; cin >> b >> g;
if (i == 0) p0 = b;
if (i == 1) p1 = b;
if (pos.find({b % g, g}) != pos.end()) {
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
continue;
}
pos[{b % g, g}] = curv;
int step = (b - b % g) / g;
g_lol[b].pb(pos[{b % g, g}] + step);
for (int j = b % g; j < n; j += g) {
val[curv] = j;
stepp[curv] = g;
curv++;
}
}
for (int i = 0; i < curv; i++) dist[i] = 1e9;
dist[p0] = 0;
deque<int> q;
q.push_back(p0);
while (!q.empty()) {
int v = q.front();
q.pop_front();
if (v < n) {
for (int el : g_lol[v]) {
if (dist[el] > dist[v]) {
dist[el] = dist[v];
q.push_front(el);
}
}
} else {
if (val[v] - stepp[v] >= 0 && dist[v - 1] > dist[v] + 1) {
dist[v - 1] = dist[v] + 1;
q.push_back(v - 1);
}
if (val[v] + stepp[v] < n && dist[v + 1] > dist[v] + 1) {
dist[v + 1] = dist[v] + 1;
q.push_back(v + 1);
}
if (dist[val[v]] > dist[v]) {
dist[val[v]] = dist[v];
q.push_front(val[v]);
}
}
}
cout << (dist[p1] == 1e9 ? -1 : dist[p1]) << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}
11010101
1
1
1
1
11
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 1ms
memory: 3868kb
input:
1 1 1000019998.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000079998.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000080002.0000000000000000000000000000000000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #2:
score: 11
Accepted
time: 0ms
memory: 3844kb
input:
1 1 447133094.8166999693494290113449096679687500000000000000000000000000000000000000000000000000000000000000000000 447159927.6324299668194726109504699707031250000000000000000000000000000000000000000000000000000000000000000000 447338817.5427659050037618726491928100585937500000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #3:
score: 11
Accepted
time: 1ms
memory: 3876kb
input:
1 1 196218113.5672945362457539886236190795898437500000000000000000000000000000000000000000000000000000000000000000 196229880.5354028272849973291158676147460937500000000000000000000000000000000000000000000000000000000000000000 196033768.3225873460178263485431671142578125000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #4:
score: 11
Accepted
time: 1ms
memory: 3860kb
input:
1 1 3723236.0617002560486525908345356583595275878906250000000000000000000000000000000000000000000000000000000000 3723453.4515777163771872437791898846626281738281250000000000000000000000000000000000000000000000000000000000 3523455.5034397974411604081979021430015563964843750000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Subtask #2:
score: 13
Accepted
Test #5:
score: 13
Accepted
time: 1ms
memory: 3804kb
input:
2 2 1707070202.5019169768784195184707641601562500000000000000000000000000000000000000000000000000000000000000000000 1707172628.9087881697341799736022949218750000000000000000000000000000000000000000000000000000000000000000000000 1707314070.5492967267055064439773559570312500000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #6:
score: 13
Accepted
time: 1ms
memory: 4000kb
input:
2 2 512357329.4850924344791565090417861938476562500000000000000000000000000000000000000000000000000000000000000000 512388070.1191617358126677572727203369140625000000000000000000000000000000000000000000000000000000000000000000 512381707.2150669979746453464031219482421875000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #7:
score: 13
Accepted
time: 0ms
memory: 3852kb
input:
2 2 903409756.0528658205876126885414123535156250000000000000000000000000000000000000000000000000000000000000000000 903463949.4278453044826164841651916503906250000000000000000000000000000000000000000000000000000000000000000000 903126398.8882297652307897806167602539062500000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #8:
score: 13
Accepted
time: 1ms
memory: 3900kb
input:
2 2 12127728.4281626416641302057541906833648681640625000000000000000000000000000000000000000000000000000000000000 12128456.0778645174950725049711763858795166015625000000000000000000000000000000000000000000000000000000000000 12128474.3838682038685874431394040584564208984375000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Subtask #3:
score: 7
Accepted
Test #9:
score: 7
Accepted
time: 0ms
memory: 3848kb
input:
3 3 1903288315.0518272203626111149787902832031250000000000000000000000000000000000000000000000000000000000000000000 1903402508.4268067042576149106025695800781250000000000000000000000000000000000000000000000000000000000000000000 1903347839.8892683654557913541793823242187500000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #10:
score: 7
Accepted
time: 1ms
memory: 3856kb
input:
3 3 1480660143.5606229153927415609359741210937500000000000000000000000000000000000000000000000000000000000000000000 1480748981.1658222470432519912719726562500000000000000000000000000000000000000000000000000000000000000000000000 1480741425.7590997483348473906517028808593750000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #11:
score: 7
Accepted
time: 1ms
memory: 4004kb
input:
3 3 31807858.5372746505690884077921509742736816406250000000000000000000000000000000000000000000000000000000000000 31809772.9705261906747182365506887435913085937500000000000000000000000000000000000000000000000000000000000000 32009773.9028147871867986395955085754394531250000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #12:
score: 7
Accepted
time: 0ms
memory: 4000kb
input:
3 3 35705670.5172322128892119508236646652221679687500000000000000000000000000000000000000000000000000000000000000 35707818.8134877826742012985050678253173828125000000000000000000000000000000000000000000000000000000000000000 35907785.1621865699707996100187301635742187500000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Subtask #4:
score: 19
Accepted
Test #13:
score: 19
Accepted
time: 0ms
memory: 3820kb
input:
4 100 1459451395.6183866153005510568618774414062500000000000000000000000000000000000000000000000000000000000000000000 1459538960.9880406495649367570877075195312500000000000000000000000000000000000000000000000000000000000000000000 1459540201.79884782107546925544738769531250000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #14:
score: 19
Accepted
time: 2ms
memory: 3872kb
input:
4 100 903328517.8003400497836992144584655761718750000000000000000000000000000000000000000000000000000000000000000000 903382704.3736624867306090891361236572265625000000000000000000000000000000000000000000000000000000000000000000 902980903.90309617179445922374725341796875000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #15:
score: 19
Accepted
time: 2ms
memory: 3804kb
input:
4 100 743114901.6849288578378036618232727050781250000000000000000000000000000000000000000000000000000000000000000000 743159403.6964254997437819838523864746093750000000000000000000000000000000000000000000000000000000000000000000 740359651.55562907340936362743377685546875000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #16:
score: 19
Accepted
time: 6ms
memory: 3860kb
input:
4 100 1972237014.5949568373616784811019897460937500000000000000000000000000000000000000000000000000000000000000000000 1972355359.9988712784834206104278564453125000000000000000000000000000000000000000000000000000000000000000000000 1972807024.89293875871226191520690917968750000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Subtask #5:
score: 23
Accepted
Test #17:
score: 23
Accepted
time: 2ms
memory: 3988kb
input:
5 30 9338929.3899659770868311170488595962524414062500000000000000000000000000000000000000000000000000000000000000 9339489.7143115701637725578621029853820800781250000000000000000000000000000000000000000000000000000000000000 9339482.670379260934168996755033731460571289062500000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #18:
score: 23
Accepted
time: 1ms
memory: 3864kb
input:
5 30 13142692.2956719952189814648590981960296630859375000000000000000000000000000000000000000000000000000000000000 13143468.8420136675522371660917997360229492187500000000000000000000000000000000000000000000000000000000000000 12743480.003975233302298875059932470321655273437500000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #19:
score: 23
Accepted
time: 0ms
memory: 3836kb
input:
5 30 7633333.8245709494140101014636456966400146484375000000000000000000000000000000000000000000000000000000000000 7633815.8143539212028372276108711957931518554687500000000000000000000000000000000000000000000000000000000000 8433795.590793634041801851708441972732543945312500000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #20:
score: 23
Accepted
time: 2ms
memory: 3992kb
input:
5 30 19920991.7301424915913230506703257560729980468750000000000000000000000000000000000000000000000000000000000000 19922234.9659035542099445592612028121948242187500000000000000000000000000000000000000000000000000000000000000 21522272.364879897650098428130149841308593750000000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Subtask #6:
score: 27
Accepted
Test #21:
score: 27
Accepted
time: 4ms
memory: 4000kb
input:
6 100 58169077.4378382915674592368304729461669921875000000000000000000000000000000000000000000000000000000000000000 58172495.5240921279364556539803743362426757812500000000000000000000000000000000000000000000000000000000000000 55772827.83379706428604549728333950042724609375000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #22:
score: 27
Accepted
time: 6ms
memory: 3864kb
input:
6 100 62787304.9730666611940250732004642486572265625000000000000000000000000000000000000000000000000000000000000000 62791120.1332033205144398380070924758911132812500000000000000000000000000000000000000000000000000000000000000 64391058.18247175901706214062869548797607421875000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #23:
score: 27
Accepted
time: 0ms
memory: 3856kb
input:
6 100 40980353.1513914409515564329922199249267578125000000000000000000000000000000000000000000000000000000000000000 40982859.9221737429725180845707654953002929687500000000000000000000000000000000000000000000000000000000000000 42582850.87664641441006097011268138885498046875000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct
Test #24:
score: 27
Accepted
time: 6ms
memory: 3864kb
input:
6 100 93493103.2283658328160527162253856658935546875000000000000000000000000000000000000000000000000000000000000000 93498664.7161339776648674160242080688476562500000000000000000000000000000000000000000000000000000000000000000 91899091.52274280654091853648424148559570312500000000000000000000000000000...
output:
1 100000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1000020000.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 1 100000.000000000000000000000000000000000000000000000000000000000000000000000...
result:
points 1.0 points 1.0 correct