| Автор | Задачи по информатике (сложные) |
|---|
| первая задача комбинаторная и решается без перебора. можно вывести формулу. |
не проходит по времени
всегда было интересно подобное условие. существует эталонный компьютер? или коня в вакууме мереем? |
всегда было интересно подобное условие. существует эталонный компьютер? или коня в вакууме мереем?
Есть авторское решение. его запускают на данном компьютере. Ученику выделяют время, за которое программа автора задачи завершила свою работу *5. |
+40
но не менее 100 миллисекунд. |
| Пост 19 и 21. |
для SuperNapalm:
Повторюсь, мож ты не заметил. Решение первой задачи - тупо посчитать все эти числа.
Допустим нужно посчитать 6 единичек. Первое число (n) - 111111 = 2^(6+1)-1. Это первое число. Второе число - n*2 (сдвигаем влево на бит), если оно меньше предельного. Третье - n*4. Ну и т. далее, пока не вылезем за ограничение.
Затем берём 7 единичек (n*2+1) и повторяем ту-же операцию. Итого двойной цикл.
Переменные: стартовое из единичек, которые будем двигать в следующем вложенном цикле; сдвинутые единички во вложенном цикле; максимальное значение; счётчик ответов - 4шт.
Константы - 2, для сдвига единичек - 1шт.
Операции сдвига, сравнения, присваивания, инкремента.
В стеке хранится 5 значений, пусть по 64 байта - 320 байт. Я думаю, вся эта байда вместится в килобайтный стек, даже с учётом red. |
для FireSwarm:
Не знаю, как ТС, а я нифига не понял. |
для alden:
Ну что тут непонятного!
Предел: 11010101
Счётчик - 0.
Нужно найти 6 повторяющихся единичек. Берём первое значение: 00111111. Оно меньше предела. Увеличиваем счётчик ответов (1). Двигаем единички 01111110. Опять подходит, увеличиваем счётчик (2), двигаем единички: 11111100 - не подходит, ибо больше предела. Берём 7 единичек. 01111111. Подходит (3), двигаем: 1111110 - не подходит. Берём восем единичек - 11111111 - сразу больше предела (до первого сдвига), на сём вычисления заканчиваем. Итого 3 варианта, где повторяются хотя бы 6 единичек подряд в числах меньше 11010101. |
48 2011-01-30 19:45:44
для alden:
Ну что тут непонятного!
Предел: 11010101
Что за предел? Откуда взялся? |
для alden:
Что за предел? Откуда взялся?
Вот отсюда:
Есть двоичные числа из N (не превышает 100 000) цифр
Это условие определяет предел. Число, больше которого мы не считаем. Если двоичне числа из 10 цифр, то предел - 1111111111. |
первая задача комбинаторная и решается без перебора. можно вывести формулу.
Не спорю. А при чём тогда pascal? Посчитать по формуле? |
для FireSwarm:
Всё равно не понял.
А числа, вида 10111111 ты вообще не учитываешь? |
для alden:
Ага, не учитываю))) Вот ведь фигня... |
В любом случае беда в том, бит - 100 000 штук, а времени 0,1 секунда.
В любом случае, сегодня выяснилось что у меня второй диплом (ура!), так что если только никто не хочет для себя порешать эти задачи то тему могу закрывать. Так же 1 числа могу выложить авторские (читай, наиболее рациональные) решения этих задач на Pascal, C++, Delphi. |
бит - 100 000 штук, а времени 0,1 секунда.
Тогда так:
бит - N, число единиц - k, число вариантов - C = (2^(N-k))*(N-k+1). Думаю, времени хватит. |
для FireSwarm:
Пост 39
Нет. Результаты для (3 1) и (4 2) отличаются:
001 1100
010 0110
100 0011
101 1101
110 1011
011 1110
111 0111
??? 1111 |
для alden:
Не отличаются:
Может так:
001 0110
010 0011
011 1101
100 1011
101 1110
110 0111
111 1111 |
для FireSwarm:
А 1100 куда дел? |
