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

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

Войти
Регистрация
Восстановить пароль
 
gogaby
1 / 1 / 0
Регистрация: 15.11.2011
Сообщений: 28
#1

Нарушен предел памяти при тестах - C++

22.03.2013, 16:37. Просмотров 318. Ответов 0
Метки нет (Все метки)

Условие задания:
Текст шифруется с помощью ключа, представляющего собой слово небольшой длины из строчных латинских букв. В шифруемом тексте заменяются только латинские буквы, остальные символы остаются неизменными. Латинские буквы разделяются на блоки так, что длина всех блоков (кроме, может быть, последнего) равна длине ключа. Пусть a1 — номер первой буквы блока в латинском алфавите, b1 — номер первой буквы ключа. Тогда первая буква блока заменяется буквой, чей номер в алфавите равен a1 + b1 (если a1 + b1 > 26, то берется величина a1 + b1 − 26). При этом прописная буква заменяется на прописную, а строчная — на строчную. Вторая и последующие буквы блоков шифруются с помощью соответствующих букв ключа аналогичным образом.

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

Определите ключ литореи, имеющий минимальную длину, на основании имеющихся данных!

Входные данные
Первая строка текстового файла littera.in содержит величину N — количество символов в каждом фрагменте (1 ≤ N ≤ 106). Далее следует незашифрованный и зашифрованный фрагменты. Зашифрованный фрагмент начинается с новой строки, но каждый из фрагментов может быть разбит на несколько строк произвольным образом.
Выходные данные
Единственная строка выходного файла littera.out должна содержать искомый ключ. Если задача имеет несколько решений, выведите наименьшее из них в лексикографическом порядке.
ПРИМЕР:
littera.in
41
To be or not t
o be? What is the question!
Yp ru aw oej ft cu?
Mtfu yi fmf gkqxuyez!
littera.out
apple|


Собственно вот моя реализация, которая работает нормально, но при длине ключа около 65к символов программа-тестировщик выдает : "Нарушен предел памяти 500м 192.9 Mb". длина исходного текста при этом не известна.

Подскажите пожалуйста в чем проблема, и как её исправить? Поможет ли хранение ключа в файле вместо строки string?

Добавлено через 22 секунды
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <string>
 
using namespace std;
 
 
char subtraction(char &letter, char &addicted_letter)
{
    int key_number = addicted_letter - letter;
    if (key_number<=0)
        key_number = 26 + key_number;
    return key_number + 96;
}
bool is_letter(char &symbol)
{
    return ((symbol>=65 && symbol<=90)||(symbol>=97 && symbol<=122));
}
 
void main(){
    
    FILE *first_block;
    FILE *second_block;
    FILE *output;
    errno_t error;
    
    error = fopen_s (&first_block, "littera.in", "r");
    error = fopen_s (&second_block, "littera.in", "r");
    error = fopen_s (&output, "littera.out", "wr");
    char start_symbol;
    char end_symbol;
    char *digits = new char [256];
    fgets(digits,255,first_block);
    unsigned int n = atoi(digits);
    fgets(digits,255,second_block);
    delete []digits;
    unsigned long i;
    for (i=0; i<n;)
    {
        if ((end_symbol = fgetc(second_block))!= '\n')
            i++;
    }
    end_symbol = fgetc(second_block);
    char symbol;
    string temp;
 
    string key;
    unsigned long r=0,k=1,t=0, num=1;
    for (i=0; i<n;i++)
    {
        do 
            start_symbol = fgetc(first_block);
        while (start_symbol == '\n');
 
        do
            end_symbol = fgetc(second_block);
        while (end_symbol == '\n');
        if (is_letter(start_symbol))
        {
            symbol = subtraction(start_symbol,end_symbol);
            if (symbol == key[r])
            {
                r++;
                if (r == key.length())
                {
                    num++;
                    r=0;
                    temp = "";
                }
                else
                {
                    temp += symbol; 
                    
                }
            }
            else
            {
                for (unsigned long j=0; j<num; j++)
                    key = key + key;
                num=0;
                r=0;
                key = key + temp + symbol;
                temp="";
            }
        }
    }
    unsigned long len = (long)key.length();
    string tt;
    string minimal_key = key;
    for (i=0; i<len; i++)
    {
        temp = key;
        temp.resize(len-1);
        tt = key.at(len-1);
        key = tt + temp;
        if (minimal_key > key)
            minimal_key = key;
 
    }
    
    fputs(minimal_key.c_str(),output);
    
 
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.03.2013, 16:37
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Нарушен предел памяти при тестах (C++):

Переполнение по времени на больших тестах - C++
Максимальное время работы на одном тесте: 1 секунда Максимальный объем используемой памяти: 64 мегабайт Слово...

Задача на коробки, ошибка в проверочных тестах - C++
День добрый, подскажите, в чем может быть ошибка в программе, написанной для данной задачи (сами тесты неизвестны) Есть две коробки,...

Ошибка памяти при выполнении, при компиляции не выводит ошибки - C++
ПОмогите плс программа вводит строку символов до точки, а после вычисляет процент согласных в этой строке и выводит их в обратном порядке....

Нарушен баланс мощности при выводе звука - Linux
Доброго времени суток всем ценителям открытого кода! Имеется Lucid, Creative SB Live! Value, Microlab 4.1 Проблема: при увеличении...

Зависает системник при тестах Aida - Процессоры
Я собрал системник с i7, видео 2gb, озу 8gb и 2 жд по 500gb. При тесте на AIDA64 Extreme Edition начинает плавать на других пк(с i5) при...

Предел выделения памяти (VirtualAlloc) - C++ WinAPI
Вот рабочий код: #include &lt;Windows.h&gt; #include &lt;iostream&gt; using namespace std; void main() {

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.03.2013, 16:37
Привет! Вот еще темы с ответами:

Нарушен ли solid ? - ООП и паттерны
Привет. Есть например сущности предметной области Нож и Складной Нож. Как вы думаете нужно спроектировать классы в этом случае? ...

Нарушен принцип инкапсуляции - Java
Под спойлером ссылка на цитату из книги Хорстмана. Не могу до конца разобраться с этим...вроде объявили мы метод как private, но говорят,...

Определить предел g(x), зная предел f(x) и предел выражения с ними - Математический анализ
Даны две задачи, пожалуйста, проверьте моё решение, оно получилось слишком простым, нет ли подвоха? Большое спасибо Вам заранее) 1....

Выгрзука в Excel из DataGridView. Нарушен порядок столбцов - C#
Здравствуйте. Выгружаю данные из БД на DataGridView. Затем из DataGridView делаю экспорт в Excel. На компьютерах с Win7 все замечательно...


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

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

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