Wataru

Наверное, можно и константами ограничиться. Вот только выписывать 768 констант никому не охота. Что-то простое брать, вроде подряд идущих чисел - плохой хеш будет. Надо реально 700 разных псевдослучайных чисел.

Главное приемущество: независимость процессов. Потоки делят между собой одну память и ресурсы системы (всякие хандлеры в винде, например).

Если один из процессов завершится или, что чаще происходит, упадет - остальные не будут затронуты. Плюс эта независимость позволяет делать песочницы для безопасности. Так, все современные браузеры запускают js и вообще каждую вкладку в отдельном процессе. Даже если куллхацкер полностью взломает браузер через специальный сайт, он окажется в процессе, который особо прав никаких не имеет, библиотеки особо интересные туда не загружены, а все общение с внешним миром - через жестко прописанные протоколы ipc (inter-process communication). Так что злодею придется взламывать еще и их.

Эта же независимость позволяет выполнять работу даже после завершения основного процесса. Так, если вы хотите сделать автообновятор программы, то после скачки/установки нового приложения, надо будет перезапустить основное приложение, чтобы перезаписать исполняемый файл (по крайней мере в винде). Но поток завершится вместе с программой и кто же тогда потом будет ее запускать? А вот процесс останется работать.

Недостатки тут - ресурсоемкость. С точки зрения системы поднять и поддерживать процесс гораздо больше работы чем сделать это с потоком. Плюс упомянутое выше ipc - это лишняя работа на каждый чих.

Вообще, дерево и список не изоморфны друг другу. В дереве же есть иерархия. Дерево нельзя реализовать с помощью списка (одного).

Возможно, вам надо хранить детей каждой вершины в виде связного списка (тогда у вас будет куча списков). Еще, популярный подход (фактически делающий то же самое) - это хранить в каждой вершине ссылку/указатель на первого ребенка и на следующего брата. Так все списки будут перемешаны в одну большую структуру. Но тут, правда, в отличии от связного списка, все равно есть 2 типа ссылок.

а весом рёбер будет выступать расстояние между этими полями. для того чтобы после построения этого графа выбрать в нём 2 вершины и найти между ними кратчайший путь ... Двигаться по карте можно только по горизонтали и по вертикали.

Это какой-то бред. Начало фразы подразумевает, что ребра есть между всеми парами вершин, продолжение говорит, что все ребра длины 1 между соседними клетками. Я предполагаю что тут именно второй вариант.

Во-первых, занумеруйте все клетки. Подойдет простая формула вроде i+m*j

Вот у вас уже есть n*m вершин в графе. Теперь добавьте ребра. Для каждой клетки (два цикла) посмотрите 4 соседние клетки. Если обе клетки - ., то добавьте из текущей клетки ребро в соседнюю.

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

const int dx[4]= {1, 0, -1, 0};
const int dy[4]= {0, 1, 0, -1};

Тогда для клетки (i, j) можно перебрать всех соседей одним циклом на 4 итерации - (i+dx[k], j+dy[k]). Надо только не забыть проверить на выход за границы матрицы.

Ну и вам надо написать функцию типа AddEdge(int u, int v) которая будет в удобную для вас структуру данных добавлять ребра. Граф удобно хранить в виде списков смежности. На C++ это можно сделать просто std::vector<std::vector<int>> и добавлять соседей через vector::push_back. Это на практике работает быстрее всяких связных списков.

И у вас будет три вложенных цикла - внешние по всем клеткам, а внутренний по четырем направлениям. Внутри вы проверяете, что сосед по этому направлению есть и между клетками можно пройти. В этом случае вызывайте AddEdge.

А можно вообще граф не строить. Берете ваш алгоритм поиска кратчайшего пути (BFS, Dijkstra или A*) и там везде, где перебираются соседи одной вершины, вставляете код проверки четырех направлений через dx/dy. Вершины можно или нумеровать их координатами, и тогда все массивы пометок будут двумерными, или можно использовать формулу u = i+j*m, (i,j) = (u%m, u/m) для преобразования координат в номер вершины и назад.

А еще есть всякие алгоритмы, которые работают сильно быстрее за счет использования того факта, что у вас не произвольный граф, а сетка в матрице. Jump Point Search - один из таких алгоритмов. В нем граф умышленно не строится и работа идет непосредственно в матрице.

Раз у вас есть переменные и списки, берите код дейкстры из википедии, переведите его в эти ваши блоки, вот и ваша дейкстра.

Граф задается очень просто: введите систему координат - каждой вершине соответствует 2 числа - номер стороки (горизонтальная линия, где она находится) и номер в строке (какая она по порядку там). На нечетных строках будет n вершин, на четных - n-1.

В списках ребер для каждой вершины добавьте ребра влево и вправо (на (x, y+1) и (x, y-1)). Наклонные ребра надо по разному создавать для вершин с четным x и нечетным x. В первом случае это будут (x+-1, y-1), (x+-1, y); во втором - (x+-1, y), (x+-1, y+1);

В достаточно большом проекте - это просто невозможно. Ни один человек в мире не может понимать целиком, например, хром.

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

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

Самое простое решение для понимания - полный перебор. Тупо 3 цикла - сколько монет с номиналом 2 взяли, сколько монет с номиналом 3 и сколько монет с номиналом 5. Каждый цикл от 0 до <Сколько осталось набрать> / номинал. Потом проверяем, что сумма сошлась. Более того, можно последний цикл пропустить и просто проверить, что оставшееся можно набрать пятаками.

bool CanExchange(int n, int have2, int have3, int have5) {
  for(int take2 = 0; take2 <= min(have2, n/2); ++take2) {
    int left2 = n - 2*take2;
    for (int take3 = 0; take3 < min(have3, left2/3); ++take3) {
      int left23 = left2 - take3*3;
      if (left23 % 5 == 0 && left23 / 5 <= have5) {
        return true;
      }
    }
  }
  return false;
}

Но это для данной конкретной задачи, где всего 3 типа монет. В общем случае нужно писать рекурсивную функцию вместо вложенных циклов, которая будет принимать сколько осталось собрать и какой тип монет перебирать.

Самое быстрое решение - динамическое программирование.

F(n,k) - можно ли набрать число n первыми k типами монет.

F(0.0) = 1
F(*, 0) = 0
F(n,k) = Sum(i = 0..have[k]) F(n-i*value[k], k-1)

Фактически, это тот же рекурсивный перебор, только с мемоизацией. Можно переписать это двумя циклами и соптимизировать по памяти до O(n).

Это задача на придумывание паттерна и доказывание его. Тут надо рисовать всякие случаи на бумажке и обобщать.

Во-первых, когда встает вопрос о можно-нельзя ли какими-то операциями получить что-то, первая мысль должна быть - придумать инвариант. Какое-то свойство, которое не меняется при применении операции. С опытом наберетесь идей для инвариантов. Тут сразу приходит в голову такой: Обозначим цвета цифрами от 0 до 2. Тогда при любом перекрашивании сумма всех чисел по модулю 3 не меняется. Если столбы одинаковые - сами числа не меняются, если 01 перекрасить в 22, 02 в 11 и 12 в 00, то сумма остается с таким же остатком от деления на 3.

Отсюда можно сразу сделать вывод, что при N делящемся на 3 ответа нет. Потому что в конце мы должны получить все цвета одинаковые, а значит сумма будет 0, N или 2N - делится на N. Раз N делится на 3, то и итоговая сумма дает остаток 0 (по модулю 3). Но изначальная раскраска может иметь любой остаток (например, 00..0001). Значит решения для таких N нет.

Далее, можно легко придумать, как "удваивать" решение. Пусть мы умеем получать какой-то N, то можно получить алгоритм для 2N. Сначала перекрашиваем первую половину по известному плану. Потом вторую половину. Потом попарно столбы из двух половин. Надеюсь, очевидно, почему это работает?

Так можно получить ответ для 2,4,8,16, но этого мало.

Следующая мысль, как можно построить универсальный план покраски - это воспользоваться тем, что если мы сделаем все столбы одинаковыми, то все последующие действия ничего не испортят. Т.е. можно взять конкретную раскраску столбов, составить план для нее. Потом взять следующий вариант входных данных, прогнать его через уже составленный план. Если результат не одноцветный - дополнить план так чтобы раскрасить все в один цвет и для этого варианта изначальной раскраски. Повторить со всеми возможными входными данными. Использовать эту идею для всех вариантов N раскрасок слишком медленно (их же 3^N). Вернемся к ней попозже.

Следующая идея должна быть - раз для существования решения важно неделимость на 3, то возможно мы сможем к группе одинаковых столбов добавить 3 столба?

После разбора нескольких случаев на бумаге я понял, что надо отдельно рассматривать случаи N%3=1 и N%3=2.

Рассмотрим первый случай. У нас есть 3k столбов цвета А, и в конце еще 4 столба - AXYC (один из N и 3 новых). Задача - получить в конце 4 одинаковых цвета. У нас уже есть решение для N=4 в примере. Просто примените его к 4-м последним столбцам. Теперь у нас есть ...AAAZZZZ. Если A=Z, то все наши операции ничего не сделают. Рассмотрим только случай A!=Z. Красим A+Z, получаем AAYYZ..Z на конце Красим 2 раза A+Y. Т.е. за 3 операции мы перекрасили 3 последние A в Z. Повторяем операцию, пока все A не перекрасим (их же 3k, напоминаю).

Теперь случай N=3k+2. У нас есть 3k A, и в конце AAXYC. Если у вас есть решение для 5, то получаете на конце 5 Z и аналогично предыдущему случаю перекрашиваете 3 последних A в цвет последних столбов.

Т.е. отдельно рассматриваете случай разных остатков N%3. Потом решаете задачу для N=4 или 5 первых столбцов, потом добавляете по 3 столба: решаете задачу для 4/5 последних столбов и итеративно перекрашиваете по 3 столба из предыдущих.

Это решение потребует максимум N/3*(F(5)+N) шагов, где F(5) - сколько нужно операций для решения N=5.

Теперь решение для N=5. Тут и надо будет воспользоваться наблюдением о дополнении плана для разных входных данных. Вот есть 5 столбов. Покрасим 1+2 и 3+4. Теперь у нас есть AABBC. Возможно какие-то цвета одинаковые. Но сначала допустим, что они все три разные. Красим попарно A+B(1+3 и 2+4). Все. Но что, если B=C, B!=A? У нас было AABBB. Мы покрасили 1+3 и 2+4 - получили ССССA. Красим 4+5 - CCCBB. Теперь, как раньше, перекрасим 3С в B: 3+4 (CCAAB), 1+3(BCBAB), 2+4 (BBBBB).
Теперь надо рассмотреть случай B=A, C!=A: AAAAC. Надо аккуратно повторить все операции выше - получим BBBBB. План для этого случая работает, ничего дописывать не надо. Остался случай A=C, C!=B. Т.е. дано AABBA. Применяем шаги выше и получим (перепроверьте!) AAAAA.

Т.е весь план для N=5 1+2, 3+4, 1+3, 2+4, 4+5, 3+4, 1+3, 2+4.

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

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

Возьмите максимальную степень двойки, помещающуюся в N. Пусть это k (2k > N, k <= N). Примените план для первых k. потом для последних k. Итого вы получите N-k столбов одного цвета и k столбов (возможно) другого цвета в конце. Если N-k делиться на 3 то, по известному плану "перекрашивания по тройкам" перекрасьте первые N-k в цвет последних k. Если же N-k не делиться на 3, то покрасьте попарно столбы цвета первых N-k и цвета вторых N-k. Потом останутся какие-то столбы в конце другого цвета, но их количество точно будет делиться на 3 (доказательство этого факта придумайте сами. Рассмотрите какие могут быть остатки от деления на 3 у k и N-k). Раз у нас группа другого цвета состоящая из троек, то мы умеем ее перекрашивать.

Этот вариант будет требовать не квадратичное, а O(n log n) количество операций.

Если клетка может иметь 13 различных состояния, то надо log_2(13)=3.7004... бит. Т.е. если хранить каждую клетку отдельно, то она будет 4 бита.

Дополнительный цвет клетки удвоит количество возможных вариантов. Будет нужно на 1 бит больше (log2(13*2)=log2(13) + log2(2) = log2(13)+1).

Запомните, количество бит = логарифм от количества вохможных вариантов. Потому что каждый бит, имея 2 значения, умножает количество возможных вариантов значений на 2.

Единственный надежный способ - это использовать мастер пароль. Если пароля нет, то любой способ шифрования можно отреверс-инженирить и расшифровать все сохраненные данные точно так же, как это делает сам продукт. Иногда даже разбираться не надо - можно просто выдрать нужные куски кода из продукта и запустить.

А с поролем - надо какой-то криптографически стойкой kdf-функцией преобразовать его в ключ шифрования и дальше применять хоть AES, хоть какой-то другой алгоритм шифрования.

Главное самостоятельно ничего криптографического не велосипедить. Берите популярные крипто-библиотеки и используйте стандратные и современные криптографические приметивы.

Тут, правда, есть проблема - если пользователь мастер пароль забудет - то сохраненные локально данные уже никак не достать. Можно полученный из пароля через KDF ключ как-то простенько зашифровать (или вообще в плейн тексте) и дополнительно выдать пользователю для сохранения на флешке и использовать для восставления пароля: если нет пароля, то ключ из файла применяется, потом данные шифруются с новым ключем, полученным из нового пользовательского пароля. Важно только убедить пользователя не хранить этот файл на том же компьютере. Если видите этот файл в папке с программой, на рабочем столе или в "моих документах" стоит отругать пользователя за пренебрижение к безопасности.

Для проверки, что пароль правильный, данные надо снабдить какой то контрольной суммой (до шифрования).

Все остальное - это security through obscurity. Не работает в долгой перспективе.

г) не правильно подсчитано.

Составьте уравнение. Вот есть у вас функция времени для n входных данных f(n) на компе B. На компе A время выполнения будет - f(n)/100, ведь он в 100 раз быстрее.

Теперь обозначьте за x объем данных на компе A, который надо найти. Тогда у вас f(x)/100 = f(n). Подставьте нужную функцию вместо f() и найдите x. Спойлер, будет похоже, но не то, что у вас в вопросе указано.