Блог пользователя Zhandos

Стэк в Си++
Автор Zhandos, 14 лет назад, По-русски
Как то раз сидел и решал задачки. Наткнулся на задачу почтальён. Вроде халява :) Решил на Си++ и получил Stack Overflow. Переписал код на Паскале и все прошло :D. 
И как решать задачи подобного рода на Си++ ?

Так же писал топсорт на Си++. Си++ --> Stack Owerflow, Pascal--> Accepted.
Как избавиться от этой проблемы? 
  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

14 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
AFAIK в начало программы нужно добавить строку вида
#pragma comment(linker,"/STACK:100000000")
→ Ответить
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Я пробовал уже это. Всё равно не работает :(
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    Тогда надо попытаться сделать все переменные глобальными - wrong
    → Ответить
14 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Вот решение на Си++, а это на паскале.
Первое решение не работает, второе проходит все тесты.
→ Ответить
  • 14 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    AC получает решение на Си, если в нём заменить (58 строка)
    if (k&1) s=k;
    на
    if (k&1) s=i;
    → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Продолжим здесь. Протокол проверки такой:

    Test 01: 0.011 0.016 972K ok Ok
    Test 02: 0.033 0.016 980K ok Ok
    Test 03: 0.032 0.016 1000K ok Ok
    Test 04: 0.005 0.016 1168K ok Ok
    Test 05: 0.013 0.016 1404K ok Ok
    Test 06: 0.017 0.031 8852K ok Ok
    Test 07: 0.054 0.047 9136K ok Ok
    Test 08: 0.193 0.191 11856K ok Ok
    Test 09: 0.196 0.191 11856K ok Ok
    Test 10: 0.193 0.191 11856K ok Ok
    Test 11: 0.203 0.206 11860K ok Ok
    Test 12: 0.205 0.222 11860K ok Ok
    Test 13: 0.208 0.206 11856K ok Ok
    Test 14: 0.195 0.191 11856K ok Ok
    Test 15: 0.195 0.191 11856K ok Ok
    Test 16: 0.196 0.175 11856K ok Ok
    Test 17: 0.201 0.191 11856K ok Ok
    Test 18: 0.203 0.191 11856K ok Ok
    Test 19: 0.199 0.191 11856K ok Ok
    Test 20: 0.207 0.191 11860K ok Ok
    Test 21: 0.004 0.016 976K ok Ok
    Test 22: 0.004 0.016 996K ok Ok
    Test 23: 0.005 0.016 1400K ok Ok
    Test 24: 0.054 0.063 9136K ok Ok
    Test 25: 0.195 0.206 11856K ok Ok
    Accepted
    → Ответить
14 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
http://mirror.codeforces.com/blog/entry/79
→ Ответить
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Значит мой компилятор немного тупой. :(
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    На g++ не работает прагма. В строке компиляции укажи параметры -wl,--stack=256000000
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      а как решать проблему если сдаешь задачу на сайт?
      после вашего поста я сразу написал прагму для одной моей проги и сдал под MS C++ и все прошло! а под g++ ошибка выполнения... не оч хочется из-за этого переходить с g++((
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Обычно на g++ жюри само проставляет стек.
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Для начала нужно попробовать уменьшить число локальных переменных в рекурсивной функции.
        Например, если используются три переменных - а, b и c, то можно заменить их на одну переменную i и завести три глобальных массива A, B, C и вместо a использовать A[i] и.т.д

        Еще в некоторых задачах можно переписать по другому, так чтобы не было рекурсии. Например, вместо поиска в глубину иногда можно использовать поиск в ширину (смотря для чего, конечно).

        Если ничего из этого не помогает, то остается только воспользоваться теоремой о том, что всякая программа содержащая рекурсию может быть переписана в виде нерекурсивной программы, и реализовать свой стэк состояний ;)
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Еще могу сказать, что можно писать на g++, а сабмитить в MSVS. Случай разного поведения за все время встретился один раз. Ну только long double в MSVS нету.
        → Ответить