| Автор | Задачи по информатике (сложные) |
|---|
| 2)Во второй задаче можно не считать сумму на каждом пути заново, а вычитать из строй "лишние" слагаемые и прибавлять не достающие с нового пути. |
1. на линейке из Н еденичек(нолики в топку) нужно наити количество умещяюшихся М еденичек.ведь Н это как я понял не число а количество цифр.
это так сложно разделить к примеру Н 22 на М 4 и проверив с прибавленым количеством ноликов на 4 должно быть три нолика.и если (Н\М) * (М+(м-1))>Н то Н\М -1 (деление без остатка)
если нолики не обязательны то просто разделить Н на М без остатка. |
| (Н/М)*М+(м-1) запутался. |
вторая такой же тупизм в которой надо просто посчитать количество шагов от старта до цели. и не заморачиваться с цифрами записанными туда.
я правда не понял условий ,компьютеру что надо объяснить всё это человеческими словами или написать работающую программу. |
1
Н/М=В ,если В*М+В-1>Н то Н/М-1
2
Н(30)+М(21) -1 =50*1000,если к=3 то 49997/20102010
в обоих задачах самое сложное отделение целого части. в первой наверно есть в паскале инструмент во второй не уверен . |
блин, вот я соня да и условия не вьедешь без пол литры.
во второй кличество почти путей равно числу К ,его надо делить.предварительно предварительно проверив не больше ли оно числа реальных путей. |
1. Метод - перебор
2. Метод - поиск пути.
ЗАдачки неплохие, ну уж слишком стандартные.
Странно, что олимпиадные |
| я маразматик |
2ая.
Создаешь второй массив, куда в ячейку b[1,i] заносишь сумму а[1,i]+a[1,i-1], аналогично для b[j,1].
Выглядит так
Массив а
1 2 3
4 5 6
7 8 9
Массив б
1 3 6
5 0 0
12 0 0
Далее создаешь процедуру, которая просматривает сумму b[i,j]=b[i-1,j]+a[i,j] и b[i,j]=b[i,j-1]+a[i,j], которая сравнивает их и заливает максимум в б(и,ж).
Выводишь b[n,n];
____
Как-то так:) |
ну уж слишком стандартные.
поменьше стандартности :)
Реализуйте функцию выдающую простое число, ближайшее к задаваемому в виде
аргумента uint64. Постарайтесь сделать максимально эффективную и компактную
реализацию без использования дополнительных библиотек. Допускается
использование специфических возможность GCC для платформ i686 и AMD64.
ps реализация - c/с++ |
для SuperNapalm:
http://www.moyashkola.com это не РВС там готовые есть. зарегайся и за 30 монет будет тебе д\з |
Задачи решаются на Delphi как дважды два! а как без динамического выделения памяти решать - это не ко мне...
--- Задача 1 ---
1) Создай открытый массив типа boolean:
var b : array of array of boolean;
2) Добавляешь функцию степени (понадобится...)
function step(a, b : integer) : integer;
var i: integer;
begin
Result := 1;
for i := 1 to b do
begin
Result:= Result * a
end
end;
3) В самой программе:
3.0) var i, j, z : integer;
u, g : boolean;
3.1) Динамишь массив: SetLength(b, n, step(2, n))
3.2) Заполняешь его по шаблону (например, для n=3):
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
, где 0 - False, 1 - True.
3.3) Провобишь обработку:
for i := 0 to step(2, n)-1 do
begin
g := true;
for j := 0 to n-k-1 do
// Заметь, что здесь он не войдёт в цикл если k >= n
begin
z := 0;
u := b[j];
while u and (z < k) do
begin
inc(z);
u := u and b[j+z]
end;
if u and g then
begin
g := false;
for z := 0 to n-1 do
if b[n, i] then write('1') else write('0');
end;
end;
Предложеное тут решение не самое рациональное.
Вторую пришлю позже. |
+32 Писал прямо тут, поэтому проверь begin-end! и ещё, там в 3.3 везде где надо вместо b[<>] надо b[<>, i] (<> - это не менять.)
--- Задача 2 ---
1) var sum : array of integer;
2) У меня a: array of array of integer; массив для хранения данных чисел в координате.
4) Программа;
4.1) Динамишь массив (кол-во = кол-во вариантов (лень считать =)))
4.2) И начинаешь работать как в прошлый раз (п. 3.2), но вместо 1 - R, 2 - D.
4.3) Перебираешь варианты и складируешь результат в Sum, если количество R = N, кол-во D = M (иначе в конечную точку не попадёшь.) При этом для экономии времени в переменную max можешь складировать максимальный результат и kmax - сюда количество
for i := 0 to g do // g - это количество вариантов
begin
...
if sum[i] > max then
begin
max := sum[i];
kmax := 1;
end
else
begin
if sum[i] = max then inc(kmax);
end;
end;
write(sum); write(kmax); |
для qwertyqaz:
А теперь вопрос на засыпку (по первой задаче).
Сколько лет будет работать твоя программа, скажем при n=1000? |
для Йопсель, ваши решения:
1) не проходит по времени
2) не проходит по времени
ничего странного.
для GoalkeeperAnsar:
сам так сделал, не проходит по времени.
для Forza_Metal:
Напоминаю, это областная олимпиада. Полностью все задачи не решили даже призеры межнара. Навряд ли на сайте с ГДЗ есть рациональные решения этих задач.
для qwertyqaz:
решения не пройдут по времени. у меня почти аналогичные. вообще никакой полный перебор не подходит. |
для alden:
Лет? ~0.000000000043 лет =)
Шучу. На самом деле, Предложеное тут решение не самое рациональное. я написал не просто так... При этом соклращение я вижу в 1,5 раза, но могу ошибаться... |
для ВСЕХ:
Дело в том, что необходимы очень рациональные решения. Решения полным перебором я придумал и сам. Они либо не проходят по времени либо (1 задача) не вмещаются даже в минимальный подходящий массив (ограничение памяти 16 Мб). А чаще, и то и другое. Предлагать его (перебор) просто не имеет смысла. |
аа.. оптимизация нужна
Это самое интересное
щас помозгуем) |
Для задачи 1 мб можно попробовать 2^(n-k+1) - 1?
Нет. Результаты для (3 1) и (4 2) отличаются:
001 1100
010 0110
100 0011
101 1101
110 1011
011 1110
111 0111
??? 1111 |
для qwertyqaz:
Насколько я понимаю, тебе требуется в первой задаче никак не меньше 2^n операций. 2^1000>10^300.
Выполняя даже по 10^9 операций в секунду понадобится никак не меньше 10^200 лет. И это очень и очень грубая оценка.... |
