1 Тема від zxzpogoncuk

  • zxzpogoncuk
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 20.12.2019
  • Повідомлень: 92
    • Репутація: 15

Тема: Алготестер. Задачі. Петрик і змійка.

https://www.algotester.com/uk/ArchivePr … play/20079
Підкажіть алгоритм. Як розв'язувати? На 17 прикладі перевищує ліміт пам'яті.

#include <iostream>

using namespace std;

int main()
{
    long int x,y;
    cin>>x>>y;
    string S;
    cin>>S;
    long int n;
    n = S.size();

    bool arr[1000000][1000000];
    arr[y][x] = true;
    long int nomer_S=0;
    while( nomer_S<n){
        if(S[nomer_S]=='R'){
            x+=1;
            if(arr[y][x]==true){
                n = -1;
                cout<<"Fail"<<endl<<nomer_S+1;
                return 0;
            }
            else{
                arr[y][x] = true;
            }
        }
        if(S[nomer_S]=='L'){
            x-=1;
            if(arr[y][x]==true){
                n = -1;
                cout<<"Fail"<<endl<<nomer_S+1;
                return 0;
            }
            else{
                arr[y][x] = true;
            }
        }
        if(S[nomer_S]=='U'){
            y+=1;
            if(arr[y][x]==true){
                n = -1;
                cout<<"Fail"<<endl<<nomer_S+1;
                return 0;
            }
            else{
                arr[y][x] = true;
            }
        }
        if(S[nomer_S]=='D'){
            y-=1;
            if(arr[y][x]==true){
                n = -1;
                cout<<"Fail"<<endl<<nomer_S+1;
                return 0;
            }
            else{
                arr[y][x] = true;
            }
        }
        nomer_S+=1;


    }
 if(n!=-1){
        cout<<"Success";
    }
    return 0;
}
Подякували: 221VOLT1

2 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Алготестер. Задачі. Петрик і змійка.

Читайте рухи по одному символу, вся стрічка в пам'яті вам не потрібна.
І замініть масив на std::vector<bool>, він значно менше пам'яті потребує. Хоча геш-таблиця координат, звісно, ще краща.

Подякували: 221VOLT, zxzpogoncuk2

koala вебсайт

3 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Алготестер. Задачі. Петрик і змійка.

▼Прихований текст
#include <iostream>
#include <set>

struct Point
{
    int x;
    int y;
    void move(Point shift)
    {
        x += shift.x;
        y += shift.y;
    }
    bool operator <(const Point& other) const
    {
        return x<other.x || (x==other.x && y<other.y);
    }
};

std::istream& operator>>(std::istream &s, Point& pt)
{
    return s>>pt.x>>pt.y;
}

int main() {
    Point head;
    std::cin >> head;
    std::set<Point> visited = {head};
    static const std::string LETTERS = "LRUD";
    static const Point SHIFTS[] = {{-1,0},{1,0},{0,1},{0,-1}};
    for(size_t step=1;;step++) {
        char shift;
        std::cin>>shift;
        size_t shift_index = LETTERS.find(shift);
        if(!std::cin || shift_index == std::string::npos) {
            std::cout<<"Success";
            break;
        }
        head.move(SHIFTS[shift_index]);
        if(visited.find(head) == visited.end()) {
            visited.insert(head);
        } else {
            std::cout<<"Fail\n"<<step;
            break;
        }
    }
    return 0;
}
Подякували: leofun01, 221VOLT, zxzpogoncuk, Дмитро-Чебурашка4

koala вебсайт

4 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Алготестер. Задачі. Петрик і змійка.

А ось тут мені вже потрібна підказка. Я переробив код на геш-таблицю, але він не проходить за часом. ЩЯРНТ?

#include <iostream>
#include <unordered_set>

struct Point
{
    int x;
    int y;
    void move(Point shift)
    {
        x += shift.x;
        y += shift.y;
    }
    bool operator ==(const Point& other) const
    {
        return x==other.x && y==other.y;
    }
};

namespace std
{
template<>
struct hash<Point>
{
    size_t operator()(const Point& p) const
    {
        return std::hash<int>()(p.x) ^ std::hash<int>()(p.y);
    }
};
}
std::istream& operator>>(std::istream &s, Point& pt)
{
    return s>>pt.x>>pt.y;
}

int main() {
    Point head;
    std::cin >> head;
    std::unordered_set<Point, std::hash<Point>> visited = {head};
    visited.reserve(200000);
    static const std::string LETTERS = "LRUD";
    static const Point SHIFTS[] = {{-1,0},{1,0},{0,1},{0,-1}};
    for(size_t step=1;;step++) {
        char shift;
        std::cin>>shift;
        size_t shift_index = LETTERS.find(shift);
        if(!std::cin || shift_index == std::string::npos) {
            std::cout<<"Success";
            break;
        }
        head.move(SHIFTS[shift_index]);
        if(visited.find(head) == visited.end()) {
            visited.insert(head);
        } else {
            std::cout<<"Fail\n"<<step;
            break;
        }
    }
    return 0;
}
Подякували: 221VOLT, leofun01, zxzpogoncuk3

koala вебсайт

5 Відповідь від koala

  • koala
  • koala
  • Лінива тваринка
  • Поза форумом
  • Дата реєстрації: 01.05.2013
  • Повідомлень: 15 603
    • Репутація: 13312

Re: Алготестер. Задачі. Петрик і змійка.

Розібрався.
1. Неправильний об'єм геш-таблиці - в умові до мільйона кроків. Заміна на

    visited.reserve(1200000);

2. Погана геш-функція. Мушу зізнатися, що маю лише досить загальне уявлення про хороші геші, але глянувши в мережі, переробив на

    size_t operator()(const Point& p) const
    {
        size_t hx = std::hash<int>()(p.x);
        size_t hy = std::hash<int>()(p.y);
        return  hx ^ (hx<<3) ^ (hx>>2) ^ hy ^ (hy<<6) ^ (hy>>1);
    }

Результат: 

Дерево 0.554с    56.188МіБ
Геш    0.345с    69.082МіБ
Подякували: leofun01, zxzpogoncuk2

koala вебсайт

6 Відповідь від zxzpogoncuk

  • zxzpogoncuk
  • Новий користувач
  • Поза форумом
  • Дата реєстрації: 20.12.2019
  • Повідомлень: 92
    • Репутація: 15

Re: Алготестер. Задачі. Петрик і змійка.

Щиро дякую, пане koala.