Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [c++]структуры 
V
    Опции темы
girlsbest
Дата 3.4.2010, 19:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 19.10.2008

Репутация: нет
Всего: нет
Условие
 
Одинокий король долго ходил по бесконечной шахматной доске.
 Известна  последовательность из N его ходов 
 (вверх,  вниз,  влево, вправо, вверх-влево и т.п.). 
 
Необходимо определить побывал  ли король дважды на  одном и том же
 поле за минимально возможное при заданном N число вычислений.
 
Входные данные: in.txt
·               N – количество ходов короля
·               Вторая строка содержит последовательность из N чисел разделеных пробелом:
o  0 - вверх, 
o  1 - вправо-вверх, 
o  2 - вправо, 
o  3 - вправо-вниз,
o  4 - вниз, 
o  5 - влево-вниз
o  6 - влево,  
o  7 влево-вверх
 
Выходные данные : out.txt
 
Единственная строка выходного файла содержит сообщение 
Yes - eсли король побывал на одной клетке дважды и
No  -  в проотивном случае.
 
Пример входных данных
2
0 4
 
Пример выходных данных
Yes

Код

#include <iostream>
#include <fstream> 
#include <map> 

using namespace std;

struct step {
    int x;
    int y;

    step(int x1 = 0, int y1 = 0): x(x1), y(y1) {}

    bool operator ==(const step &s) {
        return ((s.x == x) && (s.y == y));
    }

    step operator+ (const int a[2]) { 
        return step(x + a[0], y + a[1]);
    };
    

}; 

bool operator<(const step& a, const step& b)
{
    if (a.x < b.x) return true;
    if (a.y < b.y) return true;
    return false;
}

const int points[][2] = {  {-1, 0}, {-1, 1}, {0,  1}, {1,   1}, 
                        {1,  0}, {1, -1}, {0, -1}, {-1, -1} };

ifstream f_in("in.txt");
ofstream f_out("out.txt");

typedef  map <step, int> mapStep;
typedef pair <step, int> mapPair;



int main(int argc, char* argv[])
{
    mapStep::const_iterator it;

    mapStep ms;

    int n;
    f_in>>n;

    step now(0, 0);
    ms.insert(mapPair(now, 1));

    int d;
    for (int i = 0; i < n; i++) {
        f_in>>d;
        now = now + points[d];
        it = ms.find(now);
        if (it != ms.end()) {
            f_out<<"Yes";
            return 0;
        }
        ms.insert(mapPair(now, 1));
    }
    
    f_out<<"No";            
    return 0;
}



Вот такая задачка, на примере входных данных, что в условии задача работает, но на большом файле где много ходов, около 10000 не работает(вложила один такой тест) Задачу эту принимает система где подобраны тесты. Буду очень благодарна, если поможете найти ошибку. 


Присоединённый файл ( Кол-во скачиваний: 22 )
Присоединённый файл  in02.txt 195,32 Kb
PM MAIL   Вверх
k0rvin
Дата 4.4.2010, 01:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 442
Регистрация: 24.1.2010

Репутация: нет
Всего: 5
храни посещения в хеш-таблице, где ключ -- координаты, значение -- кол-во посещений
изначальную координату задаешь (0, 0), потом, пошел например король влево-вверх -> текущая-координата+(-1, 1) => (-1, 1) смотришь в хешь-таблице:
есть такое -> следовательно повтор, можешь выдавать ответ
нет такого -> помечаешь, что есть посещение.

вот и всё

в чем проблема непонятно

Это сообщение отредактировал(а) k0rvin - 4.4.2010, 01:36


--------------------
“Object-oriented design is the roman numerals of computing.” — Rob Pike
All software sucks
PM MAIL   Вверх
girlsbest
Дата 4.4.2010, 10:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 19.10.2008

Репутация: нет
Всего: нет
ну во первых я не знаю, что такое хешь-таблица...а во вторых я не понимаю почему ЭТА прога не работает на больших тестах, а на маленьких работает и работает правильно.
PM MAIL   Вверх
girlsbest
Дата 5.4.2010, 21:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 19.10.2008

Репутация: нет
Всего: нет
Если поможете подправить код, буду очень благодарна... smile  smile 
PM MAIL   Вверх
Fortnox
Дата 5.4.2010, 22:57 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 373
Регистрация: 31.10.2008
Где: Ростов-на-Дону

Репутация: 4
Всего: 22
girlsbest, а вы уверены, что в этих входных данных король проходит по хоть какому-нибудь поле дважды?
PM MAIL   Вверх
girlsbest
Дата 8.4.2010, 21:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 19.10.2008

Репутация: нет
Всего: нет
Да...ответ должен в файл записаться да, но даже если бы и не проходил, то записало бы нет, а тут выкидывает ошибку неправильной перегрузки знака <
PM MAIL   Вверх
Fortnox
Дата 8.4.2010, 21:32 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 373
Регистрация: 31.10.2008
Где: Ростов-на-Дону

Репутация: 4
Всего: 22
girlsbest, мм, у меня нет такой ошибки.

gcc version 3.4.2 (mingw-special)

А вот на VC++ 2008 удалось воспроизвести (изначально файл не компилировался им)...

Это сообщение отредактировал(а) Fortnox - 8.4.2010, 21:35
PM MAIL   Вверх
girlsbest
Дата 8.4.2010, 22:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 19.10.2008

Репутация: нет
Всего: нет
странно.
PM MAIL   Вверх
Fortnox
Дата 8.4.2010, 22:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 373
Регистрация: 31.10.2008
Где: Ростов-на-Дону

Репутация: 4
Всего: 22
Вроде работает:
Код

struct step 
{
    int x;
    int y;

    step(int x1 = 0, int y1 = 0): x(x1), y(y1) {}

    bool operator ==(const step &s) 
    {
        return ((s.x == x) && (s.y == y));
    }

    step operator+ (const int a[2]) 
    { 
        return step(x + a[0], y + a[1]);
    }

    bool operator< (const step& b) const
    {
        if (x != b.x)
            return x < b.x;
        else if (y != b.y)
            return y < b.y;
        else return false;
    }
};


Причина из-за Strict weak ordering

Это сообщение отредактировал(а) Fortnox - 8.4.2010, 22:51
PM MAIL   Вверх
girlsbest
Дата 9.4.2010, 18:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 96
Регистрация: 19.10.2008

Репутация: нет
Всего: нет
спасибо огромное))) smile  smile  smile  smile 
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0523 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.