Добрый день, такая задача возникла:

Дана геометрическая прогрессия(последовательность) с основанием 2, и первым членом 1:

1 2 4 8 16 32 64 128 ...

входные данные дается одно число, например: 74

это число состоит из членов последовательности, 2 + 8 + 64

и нужно найти из каких членов состоит входное число.

Хотел бы узнать если какие то формулы или хорошие алгоритмы? или жадный перебор всевозможных вариантов?

членов последовательности может быть до 30, думаю слишком затратно будет перебор делать..

Может кто знает где можно почитать про решение задач на ДП? Примеры задач, способы решения, алгоритмы и т.п.

В книгах Окулова(Программирование в алгоритмах) и Кормена(Алгоритмы, построение и анализ) поискал, не нашел такого раздела.

Всем привет, вот дана такая задача: Lines

Я ее решил через обычный волновой алгоритм, представив лабиринт как матрицу NxN.

Но т.к. задача в разделе "Теория графов", значит ее нужно как-то через графы решить. Так вот, хотел бы спросить, а как?

Каким образом представить граф, и какая идея решения будет?

Спасибо.

Добрый день, на acmp.ru есть такая задача: Подарки

Я пытался решить таким образом:

Если входные данные:

5 10
4 7 4 3 10

Сначало сортировал массив по неубыванию,

3 4 4 7 10

А далее делал так:

while(M > 0)
	{
		int t = A[1] - A[0];
		if(M > t)
		{
			M -= (t + 1);
			A[0] += (t + 1);
		}
		else
		{
			A[0] += M;
			M = 0;
		}
		
		i = 0;
		while(A[i] > A[i + 1] && i < N - 1)
			swap(A[i], A[i + 1]), i++;
	}

А — отсортированный массив

N — кол. элементов массива

M — кол. конфет

Надеюсь по алгоритму, идея решения ясна.. В конце работы алгоритма первый элемент массива и будет ответом.

Но такое решени не эффективное на больших входных данных и получаю TL на 10 тесте.

Теперь хочу попробовать решить через двоичные деревья, т.к. это у меня работает за O(N)

while(A[i] > A[i + 1] && i < N - 1)
			swap(A[i], A[i + 1]), i++;

А если сделать через min heap, то будет за O(log N).

У меня возникло 2 вопроса:

1) Как можно реализовать этот min heap самому, что бы там были методы добавления, и удаления корневого элемента? Если у кого есть пример, буду благодарен. В сети не нашел хороших примеров, а сам реализовал совсем не правильно.

2) Как тоже самое сделать через priority_queue? Проблема в том, что по умолчанию этот контейнер в С++ в корневом элементе хранит максимальный элемент, т.е. max heap. А мне нужно наоборот.

Я в справочнике читал, что там ему можно параметр передавать компатор(не знаю как правильно называется). В сети нашел несколько примеров, только там этот "компатор" был классом у которого много разных методов и перегруженных операторов. Тупо copy/paste не стал делать, хотел бы разобраться что и зачем.

Если кто знает, подкажите пожалуйста как сделать так, что бы в этом контейнере сортировка была по неубыванию.

Буду благодарен.

Господа кодфорцесеры, вот задачка: Расследование

Решаю самым банальным алгоритмом так:

#include <fstream>

#define LL long long
#define MAXN 1e6 + 1

using namespace std;

fstream in("input.txt"), 
		out("output.txt", std::ios::out);

int G[101][101], N, t, i, k;

int Parent(int u)
{
	if(u-- == 1)
		return 1;
	int _t = 0;
	for(; !G[u][_t]; _t++);
	return _t + 1;
}

int Depth(int u)
{
	int k = 0;
	while(u != 1) 
		u = Parent(u), k++;
	return k;
}

int main()
{
	for(in >> N >> _a >> _b; in >> t; i++)
		G[t - 1][i + 1] = G[i + 1][t - 1] = 1;
	
	int ha = Depth(_a), hb = Depth(_b);

	while(ha != hb)
		if(ha > hb)
			_a = Parent(_a), ha--;
		else
			_b = Parent(_b), hb--;
	
	while(_a != _b)
		_a = Parent(_a), _b = Parent(_b);

	out << _a;

	return 0;
}

Сложность O(h)

но получаю TL в 11 тесте, хотя максимальное значение h 29999

вроде не должно TL давать. Подскажите пожалуйста в чем проблема?

Господа, есть отсортированный вектор V из 10^7 элементов.

Например:

0 0 1 1 1 2 3 4 4 5 ...

Далее первый элемент вектора увеличивается на K, после чего вектор должен быть отсортирован.

Хотел бы узнать, какой из следующий методов является быстрее:

1)

V[0] += K;
sort(V.begin(), V.end());

2)

V[0] += K; i = 0;
while(A[i] > A[i + 1] && i < N - 1)
        swap(A[i], A[i + 1]), i++;

3)

V[0] += K;
Через модифицированный бинарный поиск найти индекс **ind** куда можно вставить наш элемент
V.insert(ind, V[0]);
V.erase(V.begin());

4) Ваш вариант.

Буду благодарен.

Всем привет, у меня вопрос по очень простой задаче из acmp.ru ( Преобразование последовательности — 2 )

Вот таким образом я ее пытался решить:

#include <fstream>
#include <algorithm>
#include <map>
 
#define LL long long
 
using namespace std;
 
fstream in("input.txt"), out("output.txt", ios::out);
 
int B[105], N, k, mi, mv, i;
map<int, int> A;
 
int main()
{
    in >> N;
    for(; in >> k; A[k]++, B[i++] = k)
        if(A[k] > mv)
            mv = A[k], mi = k;
        else
            if(A[k] == mv)
                mi = min(mi, k);
                 
    for(i = 0; i < N; i++)
        if(B[i] != mi)
            out << B[i] << " ";
    if(mv) 
      for(i = 0; i <= mv; i++)
        out << mi << " ";
    return 0;
}

Когда у себя на компе тестирую тесты, то выходные данные правильные, а как задачу отправляю на проверку, то сразу ошибка на первом тесте пишет. Не могу понять в чем ошибка.

Может кто-то из вас догадается? Я подозреваю, что где-то за пределы массивы выходу и т.п.

Переписал тот же алгоритм, только еще более извращенее, которое прошла все тесты:

#include <fstream>
#include <algorithm>
#include <map>
  
#define LL long long
  
using namespace std;
  
fstream in("input.txt"), out("output.txt", ios::out);
 
class Q
{
public:
    int value;
    int count;
} B[105];
 
int C[105], N, k, q, i;
map<int, int> A;
 
int CMP(const Q &a, const Q &b)
{
    return a.count > b.count;
}
 
int CMP_(const Q &a, const Q &b)
{
    return a.value < b.value;
}
 
int main()
{
    in >> N;
    for(; in >> k; A[k]++, C[i++] = k);
 
    for(i= 0; i < N; i++)
        B[i].value = C[i], B[i].count = A[C[i]];
     
    sort(B, B + N, CMP);
    sort(B, B + B[0].count, CMP_);
     
    for(i = 0; i < N; i++)
        if(C[i] != B[0].value)
            out << C[i] << " ";
             
    for(i = 0; i < B[0].count; i++)
       out << B[0].value << " ";
        
    return 0;
}

Добрый вечер, вот задача из acmp.ru ( Lines )

У меня возникло 2 вопроса.

1) Хотел бы, что бы помогли разобраться с разбором решения этой задачи, только теоритически. Каким бы образом вы ее решили через графы?

2) Если эту задачу решать через обычный волновой алгоритм, то какие есть методы заполнения матрицы числовыми коэффициентами для нахождения пути?

Например:

.  .  .  .  .
.  0  0  0  .
.  1  .  .  .
.  .  0  0  .
.  .  .  99 .

.   - это свободный путь
0   - стена
1   - нач. точка
99  - конеч. точка

результат заполнения должен быть таким:

4  5  6  7  6
3  0  0  0  5
2  1  2  3  4
3  2  0  0  5
4  3  4  99 6

Может кто-то знает рациональное решение(алгоритм) ?

Спасибо.

Good day my pen friends :)

Why don't make single contest, which joint div1 and div2, only ten problems different complexity, and limitation 5 hours ?

It will interestingly..

P.S. excuse for illiteracy

Подскажите пожалуйста пример реализации dfs без рекурсии. Вот попробовал реализовать через стэк, но как-то криво работает..

int G[N][N]; // Матрица смежностей
...
void dfs(int p)
{
	stack<int> S;
	vector<int> v(N);
	int t;
	S.push(p);
	v[p]++;
	cout << p  + 1 << " ";
	while(!S.empty())
	{
		t = S.top();
		S.pop();
		for(int i = N - 1; i > 0; i--)
			if(G[t][i] && !v[i])
			{
				S.push(i);
				v[i]++;
				cout << i + 1 << " ";
			}
	}
}

Добрый вечер, у меня есть такая задача:

Вам дана стопка посадочных карточек на различные виды транспорта, которые доставят вас из точки A в точку B. Карточки перепутаны, и вы не знаете,где начинается и где заканчивается ваше путешествие. Каждая карточка содержит информацию о том, откуда и куда вы едете на данном отрезке маршрута, а также о типе транспорта (номер рейса, номер места и прочее). Предоставьте JavaScript API, который отсортирует такой список карточек и вернет словесное описание, как проделать ваше путешествие. API должен принимать на вход несортированный список карточек в формате придуманном вами и возвращать, например, такое описание: (a) Take train 78A from Madrid to Barcelona. Seat 45B. (b) Take the airport bus from Barcelona to Gerona Airport. No seat assignment. (c) From Gerona Airport, take flight SK455 to Stockholm. Gate 45B. Seat 3A. Baggage drop at ticket counter 344. (d) From Stockholm, take flight SK22 to New York JFK. Gate 22. Seat 7B. Baggage will be automatically transferred from your last leg.

Сам до конца не представляю ситуацию в задаче. Объясните пожалуйста этапы решения данной задачи. Я не прошу написать за меня код, а просто объяснить, что и зачем нужно делать.

Буду очень благодарен.