Ограничение по времени: 2 секунды.
Ограничение по памяти: 512 Мб.
Условие:
Даны две дроби a
/b
< c
/d
с целыми неотрицательными числителями и целыми положительными
знаменателями, а также выбрано некоторое целое положительное N
. Рассмотрим все несократимые дроби e
/f
с целыми положительными числителями и знаменателями, не превосходящими N, лежащие
между этими двумя дробями: a
/b
<
e
/f
<
c
/d
. Выпишем их в конечную последовательность в порядке
возрастания сначала знаменателей, а потом числителей: дробь e1
/f1
будет в этом списке раньше e2
/f2
,
либо если f1
< f2
, либо если f1
= f2
и e1
< e2
. Ваша цель — вывести n первых дробей в этой
последовательности (или всю последовательность, если в ней менее n
дробей).
Формат входных данных:
В первой строке находятся шесть целых чисел a
, b
, c
, d
, N
, n
— две данные дроби, ограничение
на числители и знаменатели и количество дробей, которые необходимо вывести (0 6 a 6 1018
,
1 <= b
, c
, d
, N
<= 1018
, 1 <= n
<= 200 000). Гарантируется, что a
b
<
c
d
.
Формат выходных данных:
В первой строке выведите целое число n'
— количество дробей, которые вы выведете. В следующих n'
строках выведите сами дроби в нужном порядке: в i
-й строке должны быть целые ei
и
fi
, разделённые пробелом — взаимно простые числитель и знаменатель i
-й дроби (1 <= ei
, fi
<= N).
Число n'
должно либо равняться n
, либо лежать в пределах от 0 до n − 1 и равняться количеству
несократимых дробей между a
b
и
c
d
, у которых числители и знаменатели целые положительные и не
превосходят N
.
Примеры:
Ввод:
0 1 1 1 5 10
Вывод:
9
1 2
1 3
2 3
1 4
3 4
1 5
2 5
3 5
4 5
Ввод:
55 34 68 42 90 1
Вывод:
1
89 55
Ввод:
49 33 45 30 50 239
Вывод:
0
Моё решение
Я использовал Дерево Штерна-Броко
для генерации дробей.
Почему-то на большинстве тестов даёт Wrong Answer
, на некоторых Time Limit
.
#include <iostream>
#include <set>
using namespace std;
class fraction {
public:
long long numerator, denominator;
fraction() : numerator(0), denominator(0) {}
fraction(long long numerator, long long denominator) : numerator(numerator), denominator(denominator) {}
bool operator==(const fraction & fr) {
return numerator == fr.numerator && denominator == fr.denominator;
}
bool operator!=(const fraction & fr) {
return numerator != fr.numerator || denominator != fr.denominator;
}
};
bool compare(const fraction& fr1, const fraction& fr2) { // для set
if (fr1.denominator != fr2.denominator)
return fr1.denominator < fr2.denominator;
return fr1.numerator < fr2.numerator;
}
bool operator>(const fraction& fr1, const fraction& fr2) {
if (fr1.denominator != fr2.denominator)
return (double)fr1.numerator * fr2.denominator > (double)fr2.numerator * fr1.denominator;
return fr1.numerator > fr2.numerator;
}
bool operator<(const fraction& fr1, const fraction& fr2) {
if (fr1.denominator != fr2.denominator)
return (double)fr1.numerator * fr2.denominator < (double)fr2.numerator* fr1.denominator;
return fr1.numerator < fr2.numerator;
}
ostream& operator<<(ostream& str, const fraction& fr) {
str << fr.numerator << ' ' << fr.denominator;
return str;
}
long long gcd(long long a, long long b) {
while (b != 0) {
long long tmp = a;
a = b;
b = tmp % b;
}
return a;
}
int main() {
long long a, b, c, d, N; int n;
cin >> a >> b >> c >> d >> N >> n;
{
long long gcd1 = gcd(a, b), gcd2 = gcd(c, d);
a /= gcd1, b /= gcd1;
c /= gcd2, d /= gcd2;
}
set<fraction, decltype(&compare)> fractionSet(&compare);
// два массива для генерации дерева
fraction* arr1 = new fraction[262144];
fraction* arr2 = new fraction[262144];
int len1 = 3, i2 = 0; // индексы 1 и 2 показывают отношение к arr1 и arr2
arr1[0] = fraction(0, 1), arr1[1] = fraction(1, 1), arr1[2] = fraction(1, 0);
{
// по окончании этого блока в arr1 остаётся две или больше дробей, причём первая дробь минимальна и больше a/b, вторая максимальна и меньше c/d, и все дроби между ними правильно сгенерированы
fraction sample1 = fraction(a, b), sample2 = fraction(c, d);
label:
if (sample1 > arr1[1]) {
arr1[0] = arr1[1];
arr1[1] = fraction(arr1[0].numerator + arr1[2].numerator, arr1[0].denominator + arr1[2].denominator);
goto label;
}
if (sample2 < arr1[len1-2]) {
arr1[len1-1] = arr1[len1-2];
arr1[len1-2] = fraction(arr1[len1-3].numerator + arr1[len1-1].numerator, arr1[len1-3].denominator + arr1[len1-1].denominator);
goto label;
}
if (arr1[0] != sample1)
if (arr1[1] != sample1)
while (true) {
fraction fr = fraction(arr1[0].numerator + arr1[1].numerator, arr1[0].denominator + arr1[1].denominator);
if (fr.numerator > N || fr.denominator > N) {
len1--;
for (int i = 0; i < len1; i++)
arr1[i] = arr1[i+1];
break;
}
if (fr < sample1)
arr1[0] = fr;
else if (fr > sample1) {
for (int i = len1; i > 1; i--)
arr1[i] = arr1[i - 1];
len1++;
arr1[1] = fr;
} else {
arr1[0] = fr;
break;
}
} else {
arr1[0] = arr1[1];
arr1[1] = arr1[2];
len1--;
}
int tmp = len1 - 2;
if (arr1[tmp] != sample2) {
while (true) {
fraction fr = fraction(arr1[tmp].numerator + arr1[tmp+1].numerator, arr1[tmp].denominator + arr1[tmp+1].denominator);
if (fr.numerator > N || fr.denominator > N) {
len1--;
break;
}
if (fr > sample2)
arr1[tmp + 1] = fr;
else if (fr < sample2) {
arr1[len1] = arr1[len1 - 1];
len1++;
arr1[++tmp] = fr;
} else {
arr1[++tmp] = fr;
break;
}
}
} else
len1--;
}
if (len1 < 2) {
cout << 0 << endl;
exit(0);
}
/*
indexForRemove убирает дроби, после генерации которых получится дробь с числителем или знаменателем больше, чем N.
Например, при N = 5 в последовательности 1/2 2/3 1/1 он уберёт только первую дробь.
Возможно, не самое лучшее решение по производительности.
*/
for (int i = 0, prevLen = 0, indexForRemove = 0;; i++) {
for (int i1 = 0;; i1++) {
arr2[i2] = arr1[i1];
i2++;
if (i1 + 1 == len1)
break;
long long numerator = arr1[i1].numerator + arr1[i1+1].numerator;
if (numerator > N) {
if (indexForRemove == i2 - 1)
indexForRemove++;
continue;
}
long long denominator = arr1[i1].denominator + arr1[i1+1].denominator;
if (denominator > N) {
if (indexForRemove == i2 - 1)
indexForRemove++;
continue;
}
fraction fr = fraction(numerator, denominator);
arr2[i2] = fr;
fractionSet.insert(fr);
i2++;
}
if (indexForRemove != 0)
memcpy(arr2, arr2 + indexForRemove, i2 -= indexForRemove);
if (i2 < 2)
break;
fraction* tmp = arr1;
arr1 = arr2;
arr2 = tmp;
len1 = i2;
i2 = 0;
prevLen = len1;
indexForRemove = 0;
}
int limit = fractionSet.size() < n ? fractionSet.size() : n;
cout << limit;
set<fraction, decltype(&compare)>::iterator it = fractionSet.begin();
for (int i = 0; i < limit; i++, it++)
cout << '\n' << *it;
cout << endl;
}
Вот вариант с перебором дробей. Практически все тесты опять WA, некоторые TL, правда, правильных ответов стало больше)
Может быть, я что-то упускаю?
int main() {
long long a, b, c, d, N; int n;
cin >> a >> b >> c >> d >> N >> n;
long long* r = new long long[400'000];
int pos = 0, i = a + 1, j = b;
double f = (double)a / b, s = (double)c / d;
while (n && j <= N) {
int lim = min(N + 1, (long long)ceil(s * j));
while (i < lim) {
if (gcd(i, j) == 1) {
r[pos++] = i;
r[pos++] = j;
if (--n == 0)
break;
}
i++;
}
i = ceil(f * ++j);
}
cout << pos / 2 << '\n';
for (int i = 0; i < pos; i++) {
cout << r[i] << ' ';
cout << r[++i] << '\n';
}
}
b
. Для1 100 2 1 1000 10
первая дробь1 1
а не3 100