Разложить число на сумму двух членов разных последовательностей
16.03.2015, 23:16. Показов 638. Ответов 0
Есть задача, условия сформулированы так:
После игры в "бинго" пушечные ядра нужно сложить в две непустые пирамиды. При этом одна пирамида должна иметь квадратное основание, а другая – треугольное. В самом верхнем слое первой пирамиды 1 ядро, во 2-м слое – 4 ядра, в 3-м слое – 9 ядер, в i-м слое – i2 ядер. Таким образом, первая пирамида в зависимости от числа слоев будет содержать 1, 5, 14, 30, 55, 91 и т. д. ядер. В самом верхнем слое второй пирамиды 1 ядро, во 2-м слое – 3 ядра, в 3-м слое – 6 ядер, в i-м слое – на i ядер больше, чем в предыдущем. Вторая пирамида в зависимости от числа слоев будет содержать 1, 4, 10, 20, 35, 56, 84 и т. д. ядер.
Напишите программу, которая рассчитает, каким должно быть количество слоев в первой и второй пирамиде, чтобы минимизировать количество ядер, оставшихся лишними при собирании ядер в пирамиды.
Ввод содержит от 1 до 100 000 строк, каждая из которых содержит одно целое число N (2 ≤ N ≤ 108) – количество ядер, которые нужно собрать в пирамиды. Последняя строка ввода, содержащая число 0, сигнализирует о завершении ввода и не должна обрабатываться.
Для каждого числа из ввода, кроме 0, вывести строку, содержащую два числа – количество слоев в первой пирамиде и количество слоев во второй пирамиде, при котором количество ядер, оставшихся лишними, минимально. Если существует несколько минимальных вариантов, вывести тот из них, в котором количество слоев в первой пирамиде меньше.
Тема - бинарный поиск, быстрая сортировка, Time Limit - 1 s, Memory Limit - 32 MB
Самый эффективный алгоритм который пришёл в голову - это вычислить наименьшее количество слоёв в первой пирамиде, при котором количество шаров в ней превосходит введённое число. Затем, начиная с 0 и заканчивая этим числом слоёв подбирать наименьшее количество слоёв по второй пирамиде, которое превосходит N-P1[i], где N - введённое число, а P1[i] - количество шаров в первой пирамиде с i слоёв.
Проблема - Time Limit на 4 тестах, после некоторой оптимизации TL на 3 тестах.
Код:
| C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| #include <iostream>
#include <vector>
#include <map>
#include <ctime>
using namespace std;
vector<int> a, a1, a2;
vector<pair<int, int>> ans;
const int MAXF = 670, MAXG = 844;
int p1(int n){ return (n*(n + 1)*(2 * n + 1)) / 6; }
int p2(int n){ return (n*(n + 1)*(n + 2)) / 6; }
bool g0(int n, int i){ return a2[n] >= i; }
bool f0(int n, int i){ return a1[n] >= i; }
int bsrch(int a, int b, int d, bool(*f)(int, int))
{
int c;
while (a<b)
{
c = (b + a) / 2;
if (f(c, d)) b = c;
else a = c + 1;
}
return b;
}
int main(){
int n = 1, kf, kg, b, c, min = 99999999;
//cout << f(415) + g(769);
pair<int, int> anst;
for (int i = 0; i < 671; i++){
a1.push_back(p1(i));
}
for (int i = 0; i < 846; i++){
a2.push_back(p2(i));
}
while (n != 0){
cin >> n;
if (n != 0)
a.push_back(n);
}
int lastm;
for (int i = 0; i<a.size(); i++){
kf = bsrch(1, MAXF, a[i] + 1, f0) - 1;
int max2 = bsrch(1, MAXG, a[i] + 1, g0) - 1;
int tmp2 = max2 + 1;
int tmp1 = 1;
int z = clock();
for (int j = 1; j <= kf; j++){
tmp2 = bsrch(1, tmp2, a[i] - a1[j] + 1, g0) - 1;
tmp1 = bsrch(tmp1, kf + 1, a[i] - a2[tmp2] + 1, f0) - 1;
if (tmp2 == 0 || tmp1 == 0) continue;
cout << tmp1 <<" " <<tmp2<< endl;
int c = a[i] - a1[tmp1] - a2[tmp2];
if (c < min){
min = c;
anst.first = tmp1;
anst.second = tmp2;
}
if (c == min && tmp1 < anst.first){
anst.first = tmp1;
anst.second = tmp2;
}
if (min == 0) break;
if (j != kf)
j = tmp1;
}
cout<<"Time: " << clock()-z << endl;
min = 99999999;
ans.push_back(anst);
}
for (pair<int, int> &z : ans)
cout << z.first << " " << z.second << endl;
return 0;
} |
|
Помогите пожалуйста, второй день голову ломаю 
Добавлено через 3 часа 56 минут
Актуально.
0
|
(
