Форумы-->Форум для внеигровых тем-->
1|2|3
| Автор | Задачи по информатике (сложные) |
|---|
Доброго времени суток. Хотелось бы узнать идею решения нескольких задач по информатике(программирование). Сразу говорю, задачи с областной олимпиады за 10-11 класс, поэтому многим могут показаться сложными.
Сами задачи(дословно условия переписывать не буду, передам суть).
Задача 1.
Есть двоичные числа из N (не превышает 100 000) цифр (могут начинаться с одного или нескольких нулей). Сколько среди них таких, в которых есть хотя бы К подряд идущих единиц?
Входные данные - собственно N и K, через пробел. Вывести единственное число - количество таких бинарных чисел.
Примеры данных (ответ): 3 2 (3), 5 1 (31), 7 10 (0)
Задача 2.
Есть таблица М на N (в пределах от 2 до 300), заполненная натуральными числами от 1 до 100. В начале мы находимся в клетке (1,1). Задача добраться до правой нижней клетки собрав максимально возможную сумму чисел. Двигаться можем только вправо и вниз.
Далее наша задача посчитать, сколько существует с левой верхней клетке в правую нижнюю (правила движения те же), что сумма собранных чисел будет отличаться от максимальной не более, чем на К (в пределах от 0 до 100).
Входные данные:
M N K
*таблица*
Вывести: максимальную сумму чисел и количество возможных вариантов в столбец.
Пример:
2 3 0
1 1 1
1 0 1
Вывод:
4
1
В следующем посте комментарии к задачам. | | это что,матрица? | Комментарии:
Прежде всего: язык Pascal, максимальная целочисленная переменная хранит значения до 2^20. Максимальное время работы программы - 100 миллисекунд.
Задача 1.
Во-первых, ответ не зависит от N-K, точнее зависит не только от этого числа.
Во-вторых, пусть существует функция от n и k, которая указывает ответ на вопрос задачи, тогда f(n,k) - либо задается рекуррентно, либо это система из функций.
Задача 2.
Максимальное возможное значение суммы чисел на пути находится "жадным алгоритмом", это ясно. Но как найти количество путей с разницой не более K? Я на олимпиаде сделал полный перебор рекурсией, абсолютное большинство не прошло по таймлимиту. | | Ну и последнее. просьба в теме: не флудить, не тролить, высказываться по сути, советы типа ".. для чтения используй функцию read(), а для вывода данных используй write()" не давать. | Ссылки на задачи:
Задача 1:
http://s28.zp.ua/olymp/?service=olymp&mid=100&olymp=9&problem=1049
Задача 2:
http://s28.zp.ua/olymp/?service=olymp&mid=100&olymp=9&problem=1051
Кому интересно, на все задачи олимпиады:
http://s28.zp.ua/olymp/?service=olymp&mid=100&olymp=9 | Пример:
2 3 0
1 1 1
1 0 1
Вывод:
Почему у меня 8,1 получилось? | Почему у меня 8,1 получилось?
2 3 0 это M, N, K соответственно. Имеем таблицу 2х3:
1 1 1
1 0 1
Пройдя таким образом, получим 4:
* * *
1 0 *(4) | В первой задаче проверяй по маске. Например длина двоичного числа 10, k = 7. Проверяешь маски 0001111111, 0011111110, 0111111100 и 1111111000. Маску проверяешь с помощью and. Пример. Есть 1001111111. Проверяем первую маску:
1001111111 and
0001111111 =
0001111111. Соответственно условию удовлетворяет.
1001111110 and
0001111111 =
0001111110. Соответственно условию не удовлетворяет.
Вторую задачу решай поиском в ширину сразу фильтруя ветки.
Pascal не знаю, говорю сразу. Но я бы делал так. | для FireSwarm:
По первой задаче. Ты не совсем понял, мне не дается само числ. задача комбинаторная, необходимо указать сколько существует Н-значных двоичных последовательностей, в которые есть хотя-бы К подряд идущих единиц.
По второй задаче: я сам так сделал, алгоритм не прошел по времени. | | Неужели даже идей нет? | По задаче 1.
Цикл от i=1 to i<=n-k+1
В каждом считаем перестановки.
Например n=6 k=3
Тогда решение будет сведено к перебору от 1 до 3
000111 - при i=1
001110 i=2
011100 i=3
111000 i=4
Считаем в каждом случае перестановки циферок, где я написал 0.
Также пригодится длинная арифметика. | Тогда решение будет сведено к перебору от 1 до 3
До 4 точнее.
Ночное очепятко.
И да, вроде банально. | Хотя, черт возьми, я делаю
(n-k)!*(n-k+1)
И это неправильно, извиняюсь=) | для CAHECHER:
Если надо я могу написать свои решения. | Задача 1.
Основная часть:
function ton(n:int64):int64;
begin
ton:=round(exp(n*ln(2)));
end;
function sum(k,n:int64):int64;
var
i,count:int64;
begin
count:=0;
i:=k;
while i<=n do
begin
count:=count+ton(n-i); if (n<>i) then count:=count+sum(1,n-i-1); i:=i+1;
end;
sum:=count;
end;
Сум соответственно вычисляет ответ. Тон - 2 в степени н. | Задача 2. Первая процедура вычисляет максимальное значение, вторая ищет варианты.
procedure maxfound;
var
i,j:integer;
begin
for i:=2 to n do b[i,1]:=b[i,1]+b[i-1,1];
for i:=2 to m do b[1,i]:=b[1,i]+b[1,i-1];
for i:=2 to n do
for j:=2 to m do
if b[i,j-1]<b[i-1,j] then b[i,j]:=b[i,j]+b[i-1,j] else b[i,j]:=b[i,j]+b[i,j-1];
max:=b[n,m];
end;
procedure obhod (x,y,sum:int64);
var
mysum:int64;
begin
mysum:=sum+a[x,y];
if x>1 then obhod(x-1,y,mysum);
if y>1 then obhod(x,y-1,mysum);
if (x=1) and (y=1) and (abs(mysum-max)<=k) then count:=count+1;
end; | Для задачи 1 мб можно попробовать 2^(n-k+1) - 1?
Или это и было здесь?
function ton(n:int64):int64;
begin
ton:=round(exp(n*ln(2)));
end;
Просто не знаю, что туда передавалось.) | По первой задаче. Ты не совсем понял, мне не дается само числ. задача комбинаторная, необходимо указать сколько существует Н-значных двоичных последовательностей, в которые есть хотя-бы К подряд идущих единиц.
Комбинаторные задачи решают на бумажке, а не в паскале. Я, честно говоря, не особо понял, что ты написал в своём варианте, но вот тебе мой, на ломаном с, но думаю разберёшься:
N = 2^(n-1), n - длина повторяющихся единичек.
k = 0;
r = 0; счётчик решений
пока (N < max){
k = N; ставим единички в начало
пока (k < max){
k *= 2; сдвигаем единички, пока не вылезем за пределы.
r++;}
N *= 2;
N +=1;} увеличиваем число единичек на 1
Как-то так.
А во второй задаче ясен пень, что не успевает. Это не поиск в ширину и даже не жадный алгоритм, это полный перебор. Ищи в ширину, так быстрее будет. | 1)На уровне идей.
Считаем количество таких чисел рекурентно по N. f(N,K) - искомая функция.
f(N,K)=2*f(N-1,K)+g(N,K). Если мы к "K-подходящему" числу припишем спереди 0 или 1, оно останется "K-подходящим", отсюда первое слагаемое. Второе слагаемое - это количество чисел, которые до приписывания 1 не были "K-подходящими", а после приписывания 1 они такими стали.
Как g(N,K) выразить через f-ки - основная проблема в задаче - думай. | Есть двоичные числа из N (не превышает 100 000) цифр
Число из ста тыщ цифр? Круто. |
1|2|3К списку тем
|
