Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 1, средняя оценка - 5.00
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
#1

ДП Динамическое программирование - C++

01.11.2012, 21:59. Просмотров 967. Ответов 2

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.

Рассмотрим все строки длины N, состоящие только из букв 'a' и 'b', в которых никакие две буквы 'b' не идут подряд. Упорядочим их в алфавитном порядке. Вам необходимо найти K-ю строку в упорядоченном списке.

Входные данные
Числа N (1 <= N <= 90) и K (K >= 1). Гарантируется, что K не превосходит общего числа рассматриваемых строк.

Выходные данные
Выведите искомую строку.

Пример

Ввод
3 5

Вывод
bab
{------------------------------------------}
Вот моё решение:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
 
using namespace std;
 
vector <unsigned long long> fib(2, 1);
 
unsigned long long calc(long long k){
    int j = 0;
    if (k == 0) return 0;
    if (k == 1) return 1;
    while (fib[j] <= k) 
        j++;
    j--;
    unsigned long long c = fib[j];
    return pow(2, double(j-1)) + calc(k-c);
}
int main(){ 
    int n;
    unsigned long long k;
    cin >> n >> k;
    for (int i = 2; i <= n+1; i++){
        fib.push_back(fib[i-1] + fib[i-2]);
    }
    unsigned long long temp = calc(k-1);
    bitset<100> c = temp;
    for (int i = n-1; i >= 0; i--)
        cout << ((c[i])?'b':'a');
    return 0;
}
1) Я заметил, что начиная с 78 числа Фибоначчи в векторе fib значения уже неправильные, хотя в ulong long вмещается
2) Проходит 29 из 50 тестов c ошибкой wrong answer
3) Можно ли перевести в bitset ulonglong ?
Разъясню алгоритм:
а = 0; b = 1;
строки длины 4
____
0000 = 0
____
0001 = 1
____
0010 = 2
____
0100 = 4
0101 = 5
____
1000 = 8
1001 = 9
1010 = 10
____
и так далее
1) видно, что длина пака - это число фибоначчи
1.5) собсно терь перевидём всё в 10-ю запись
2) теперь видно, что начиная со 2-ой пачки z[k] = 2^j + z[i], где i [0..fib[j]]
3) Но так как длина z будет очень большой замутим рекурсию.
х3 в чём ошибка

Добавлено через 7 минут
и k [2^j..2^j + fib[j]]

Добавлено через 3 минуты
Ой!!! Т.Е : z[i] = 2^j + z[i - fib[j]], по i [0..fib[j-1])
1
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2012, 21:59
Здравствуйте! Я подобрал для вас темы с ответами на вопрос ДП Динамическое программирование (C++):

Динамическое программирование - C++
Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт У Пети есть полоска бумаги, разделенная на N клеток. Он хочет...

Динамическое программирование - C++
Не понимаю динамических структур, списков, работы с ними. Посоветуйте источник изучения. Что-то вроде того что написано здесь...

Динамическое программирование - C++
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда сделать шаг: к магазину или в противоположном направлении. ...

динамическое программирование - C++
Народ помогите плиз найти алгоритм решения следующей задачи. На посвящение в студенты собрались все первокурсники. Некоторые из них знают...

Динамическое программирование - C++
Усложнили задачу мне.... : Дан массив A. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным...

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2012, 06:11 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Ternsip Посмотреть сообщение
1) Я заметил, что начиная с 78 числа Фибоначчи в векторе fib значения уже неправильные, хотя в ulong long вмещается
да вроде все правильно.

Цитата Сообщение от Ternsip Посмотреть сообщение
2) Проходит 29 из 50 тестов c ошибкой wrong answer
я думаю, что ошибка здесь (при определенных значениях скорее всего теряется точность):
Цитата Сообщение от Ternsip Посмотреть сообщение
unsigned long long calc(long long k){
int j = 0;
if (k == 0) return 0;
if (k == 1) return 1;
while (fib[j] <= k)
j++;
j--;
unsigned long long c = fib[j];
return pow(2, double(j-1)) + calc(k-c);
}
Цитата Сообщение от Ternsip Посмотреть сообщение
Можно ли перевести в bitset ulonglong ?
А есть смысл. Попробуйте такой (более простой) вариант:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
 
using namespace std;
 
vector <unsigned long long> fib(2, 1);
 
int main(){ 
    int n;
    unsigned long long k;
    cin >> n >> k;
    for (int i = 2; i <= n+1; i++){
        fib.push_back(fib[i-1] + fib[i-2]);
    }
    for(int i=n; i>0; i--)
        if(k-1>=fib[i])
        {
            cout<<'b';
            k-=fib[i];
        }
        else
            cout<<'a';
    cout<<endl;
    return 0;
}
3
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
02.11.2012, 10:06  [ТС] #3
valeriikozlov, Спаибо! Вы большой молодец! работает Поставил бы 3 лайка
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.11.2012, 10:06
Привет! Вот еще темы с ответами:

Динамическое программирование. - C++
Помогите, пожалуйста, составить алгоритм по одному из ниже представленных заданий, используя методы динамического программирования и жадных...

Динамическое программирование - C++
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 1, а...

Динамическое программирование - C++
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать, сколькими способами можно полностью замостить ими поле n на m,...

Динамическое программирование! - C++
#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; int a, n, m; int main() { scanf(&quot; %d %d&quot;, &amp;n,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru