Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
MAXimal :: φορυμ » Problems » Змейка
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Помогите, пожалуйста, с задачей.
В треугольной сетке записаны числа следующим образом:
7
4 8
2 5 9
1 3 6 10
(a[1][1] = 1, a[1][2] = 2, a[2][1] = 3, и т.д.).
Необходимо по числу найти координаты в таком массиве. Можно ли это сделать чем-нибудь кроме перебора ?
Числа в нижней строке имеют вид n*(n+1)/2
т.е мы за O(sqrt(n)) можем найти диагональ, ну а потом уже и все остальное за O(1)
На первой диагонали у нас 1 число, на второй 2, на третьей 3 и т.д.. Значит мы можем найти номер диагонали на которой находится наше число(по формуле суммы членов арифм прогрессии). Так же мы можем найти первое число на нашей диагонали. Значит, мы знаем номер нашего числа в диагонали считая от левого верхнего. У первого числа на диагонали i координаты (1,i), у j-го (1+j-1,i+j-1).
Числа в нижней строке имеют вид n*(n+1)/2
т.е мы за O(sqrt(n)) можем найти диагональ, ну а потом уже и все остальное за O(1)
Зачем за O(sqrt(n))?
Как минимум, тут можно бинпоиском с проверкой за O(1).
Но вообще, зная количество чисел на каждой диагонали(1,2,3,...), т.е. нам надо найти последнюю полную диагональ(такую которая лежит перед нашим числом). Получаем:
n*(n+1)<=a*2
n^2+n-a*2<=0Решаем это неравенство и получаем номер диагонали за O(1).
Идея в том что нижняя строка постоянно увеличивается на число которое увеличивается на единицу
то есть
1 3 6 10 15 21 ...
+2 +3 +4 +5 +6 ....
вот этот возрастающий ряд сравниваю с введенным n, как только элемент ряда становится равным или больше n значит можно теперь высчитать координаты.
#include <iostream>
using namespace std;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n = 0;
scanf("%d",&n);
if(n == 1){ printf("x = 1 y = 1"); return 0;}
int iter = 1;
for(int i = 2; ;i++){
iter += i;
if(iter >= n){
int d = iter - n;
printf("х = %d y = %d",i-d,d+1);//высчитываю координаты
return 0;
}
}
return 0;
}
это решение за O(sqrt(n)), и тут где-то ошибка.
Номер диагонали можно не циклом вычислять как у меня а решив уравнение
KADR:
n*(n+1)<=a*2
n^2+n-a*2<=0
тогда цикл вообще не нужен, решение будет за O(1).
Спасибо всем!
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
MAXimal :: φορυμ » Problems » Змейка