Comments 15
Хотелось бы задачку посложнее и интереснее)
Перенесите в блог «Алгоритмы» или «Спортивное программирование».
Перенесите в блог «Алгоритмы» или «Спортивное программирование».
еще кармы нету, это мой первый топик
Хотите задачку посложнее? Задаю.
У нас есть N-мерное пространство. На сколько подпространств оно разобьется, если провести K (N-1)-мерных непараллельных пространств?
К примеру, для прямой N = 2, K точек разбивают её на K + 1 часть.
Задача достаточно распространённая, так что не лезьте в интернет. Хотя, честно говоря, строгого обощения решения этой задачи на N-мерное пространство и я не знаю, но по образу и подобию случаев для N = 1, 2, 3 можно догадаться.
P.S. Да, формула есть, но она на столь очевидна, как предыдущая.
У нас есть N-мерное пространство. На сколько подпространств оно разобьется, если провести K (N-1)-мерных непараллельных пространств?
К примеру, для прямой N = 2, K точек разбивают её на K + 1 часть.
Задача достаточно распространённая, так что не лезьте в интернет. Хотя, честно говоря, строгого обощения решения этой задачи на N-мерное пространство и я не знаю, но по образу и подобию случаев для N = 1, 2, 3 можно догадаться.
P.S. Да, формула есть, но она на столь очевидна, как предыдущая.
Это, должно быть, 1+C(K,1)+C(K,2)+...+C(K,N)?
В Интернете не искал, считал в уме.
В Интернете не искал, считал в уме.
P.S. А я думал, для прямой N=1…
что-то я раз 5 перечитал условие, но не понял его до конца:
проводить K N-1-мерных пространств можно по разному, в задаче нужно указать на какое наибольшее количество подпространств оно разобьется? если минимум = это значит они будут параллельны, но это указано в условии.
простейший пример:
N — некая двухмерная плоскость
N-1 — линия
1-а линия — 2 подпространства
2-е линии — 3(паралельно) — 4(пересечение) подпространства
3-и линии — 4(паралельно) — 6(пересечение в 1 точке) — 7(пересечение в 3 разных точках) подпространства
и т.д.
проводить K N-1-мерных пространств можно по разному, в задаче нужно указать на какое наибольшее количество подпространств оно разобьется? если минимум = это значит они будут параллельны, но это указано в условии.
простейший пример:
N — некая двухмерная плоскость
N-1 — линия
1-а линия — 2 подпространства
2-е линии — 3(паралельно) — 4(пересечение) подпространства
3-и линии — 4(паралельно) — 6(пересечение в 1 точке) — 7(пересечение в 3 разных точках) подпространства
и т.д.
и я думаю, что максимум будет достигаться когда все (N-1)-мерные пространства будут пересекаться каждый с каждым и в тоже время в одном месте не будет одновременно пересечения больше 2 пространств
Почти правильно. Любые N подпространств должны иметь ровно одну общую точку, и при этом никакие N+1 подпространства общей точки иметь не могут. Если N<K — то пересечение всех подпространств должно быть непустым и иметь размерность K-N. В этом случае (называется «в общем положении») число частей будет максимальным.
и еще, не знаешь где эту задачу можно найти на неком портале что бы попробовать сдать? или найти тесты к ней, так как я своим решениям без проверки не доверяю :)
Более или менее первая попавшаяся эвристика выглядит так:
Интересно, когда она в первый раз ошибется.
static int NCube(int n) {
int c1=(int)(Math.Pow(n,1.0/3)+0.5);
int c2=(int)(Math.Sqrt(n/c1)+0.5);
int c3=n/(c1*c2);
int S=3*c1*c2*c3+2*(c1*c2+c1*c3+c2*c3)+(c1+c2+c3);
int h=n-c1*c2*c3;
if(h!=0) {
int d1=(int)(Math.Sqrt(h)+0.5);
if(d1*d1>h) d1--;
int d2=h/d1;
S+=3*d1*d2+2*(d1+d2)+1;
h-=d1*d2;
if(h!=0) S+=3*h+2;
}
return S;
}
Интересно, когда она в первый раз ошибется.
в принципе, ты написал как раз формулу для 3D случая с учетом корректировок, c1 — количество полных кубов, с2 — количество полных квадратов с корректировкой и т.д.
Да, но ответ сильно зависит от конфигурации — сколько в модели внутренних ребер и внутренних вершин. Чем их больше, тем меньше спичек в модели. Поэтому задача эвристики — угадать, как надо строить модель: сколько полных двумерных рядов и какого они размера, сколько одномерных рядов и какой они длины, сколько кубиков осталось в неполном одномерном ряду. Если не угадает, то ответ может оказаться неправильным.
Спасибо, люблю подобный материал по спортивному программированию.
Sign up to leave a comment.
Динамическое программирование. Спичечная модель