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

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Олимпиадная задача... Прохожу только 24 теста 
:(
    Опции темы
kolesnle
Дата 17.11.2013, 15:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Упертый сишник
*


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

Репутация: нет
Всего: нет
Решая задачу Хоккей на Урале мой мозг выдал мне вот такой код:
Код

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

bool haveIntersection(const std::vector<int>& s1, const std::vector<int>& s2)
{
    if(s1.size()==0 || s2.size() ==0 )
        return false;

    bool intersects = false;

    for(int i = 0; i<s1.size();i++){
        for(int j = 0;j<s2.size();j++){
            if(s1.at(i) == s2.at(j)){
                intersects = true;
                break;
            }
        }
        if(intersects)
            break;
    }
    return intersects;
}

int main()
{
    int N;
    std::cin >> N;
    std::vector< std::vector<int> > sets(N+1);
    
    for (int i=0; i<N; ++i){
        int c1,c2;
        std::cin >> c1 >> c2;
        sets[c1].push_back(c2);
        sets[c2].push_back(c1);
    }

    for(int i=1; i<N+1;i++)
        std::sort(sets[i].begin(),sets[i].end());

    int K;
    std::cin >> K;
    std::vector<int> trueKset;
    
    for(int i=1;i<sets.size();++i){
        std::vector<int> Kset;
        Kset.push_back(i);

        for(int j=1; j<sets.size();++j){
            if(j == i)
                continue;

            if(!haveIntersection(Kset,sets.at(j)))
                Kset.push_back(j);

            if(Kset.size() == K){
                trueKset = Kset;
                break;
            }
        }

        if(Kset.size() == K)
            break;
    }

    if(trueKset.size() == K)
        for(int i=0;i<trueKset.size();i++)
            std::cout<<trueKset[i]<<" ";
    else
        std::cout<<0;
}

Который безукоризнинно работает для N<=10, а дальше(по мнению проверяющей системы) выдает неправильные ответы и не укладывается в таймаут(5 секунд!!!!). Я ничего не понимаю, голова уже не работает, прошу вашей помощи!
PM MAIL   Вверх
feodorv
Дата 17.11.2013, 19:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45
Цитата(kolesnle @  17.11.2013,  16:11 Найти цитируемый пост)
    std::vector< std::vector<int> > sets(N+1);

Всего два тура! Зачем такие сложности?

Почему не просто
Код
   int *first = new int[N+1];
   int *second = new int[N+1];

   for( int i=0; i<N/2; ++i)
   {
     int c1, c2;
     std::cin >> c1 >> c2;
     first[c1] = c2;
     first[c2] = c1;
   }

   // то же для второго тура



Алгоритм я не понял. Зачем сортировка? Почему условие такое жёсткое:
Цитата(kolesnle @  17.11.2013,  16:11 Найти цитируемый пост)
           if(Kset.size() == K){

Не игравших друг с другом команд может быть больше К, а из них вполне можно отобрать K штук...


На мой взгляд, заалгоритмизировать можно проще, и безо всякой подпрограммы, потребляющей много времени. Нужен дополнительный массив, соответствующий списку команд, в котором просто отображать факт, что с этой командой уже играли (эту команду "вычёркиваем")))); плюс считать число невычеркнутых из списка команд. Если их останется более или равно K, то вывести список невычеркнутых команд числом не более К и завершить программу. Потребуется цикл из N-K итераций для полного перебора, соответствующий выбору начальной команды, которую гарантированно включим в список (а все команды с меньшими номерами - вычеркнем). Как-то так.

Это сообщение отредактировал(а) feodorv - 17.11.2013, 19:57


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
kolesnle
Дата 17.11.2013, 20:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Упертый сишник
*


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

Репутация: нет
Всего: нет
Цитата(feodorv @  17.11.2013,  19:53 Найти цитируемый пост)
Зачем сортировка?

Я ее сначала убрал, но так (к моему изумлению) программа работала медленнее. Вставил обратно, от греха подальше:))

Цитата(feodorv @  17.11.2013,  19:53 Найти цитируемый пост)
плюс считать число невычеркнутых из списка команд

Не вычеркнутых пар комманд. :( ПС. Может я не правильно понял.
А на туры они вообще поделили чтобы запутать, 2 тура или 1 - все-равно

Это сообщение отредактировал(а) kolesnle - 17.11.2013, 20:18
PM MAIL   Вверх
feodorv
Дата 17.11.2013, 21:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45
Цитата(kolesnle @  17.11.2013,  21:12 Найти цитируемый пост)
Не вычеркнутых пар комманд

Почему пар? Ведь мы отбираем именно команды, которые не играли друг с другом.
Цитата
1 2
3 5
4 6
2 3
4 5
1 6

Здесь начинаем с 1, 2 вычёркиваем. Смотрим 3 - не пересекались с ней, 5 - вычёркиваем. Смотрим 2 - она вычеркнута, пропускаем. Смотрим 4 - не пересекались с ней, 5 уже вычеркнута. Смотрим 1 - это наш старт, 6 вычёркиваем. Итого осталось: 1, 3, 4 - это >= 3 необходимых команд, следовательно, ответ положительный. Если бы был отрицательный, то 1 бы вычеркнули, а стартовали бы с 2: 1 (вычеркнута, пропускаем), 2 (старт) -> 1 уже вычеркнута, 3 (не вычеркнута) -> 5, 4 (не вычеркнута) -> 6, 2 (старт) -> 3, 4 (не вычеркнута) -> 5 (уже вычеркнута), 1 (вычеркнута, пропускаем); итого: 2, 4 - ответ отрицательный. Потом бы вычеркнули 1 и 2, 3 - старт...


Цитата(kolesnle @  17.11.2013,  21:12 Найти цитируемый пост)
А на туры они вообще поделили чтобы запутать, 2 тура или 1 - все-равно

Нет, не всё равно. Если бы был всего один тур, то всегда можно было бы отобрать N/2 команд (из списка first, например). И всё зависело бы от того, больше K этого N/2 или нет. В случае же двух туров всё совсем не очевидно.


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
akizelokro
Дата 18.11.2013, 03:42 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Крокодил
**


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

Репутация: 1
Всего: 5
Код

std::cin >> c1 >> c2;


Я вот бухаю уже второй день, но как оно подразделяться будет?
Я так понял, в значении меньше одной цифры будет от 0 до 9, а от больше девяти (10 и две цифры, понесутся советы программеров, и вообще я намерен смотаться в Сочи в командировку, а затем в Нью-Йорк, и малость поиграть на бирже, и вообще я сибирский поэт и сепаратист)
Ух!

Добавлено @ 03:44
Код

std::cin >> N;
std::cin >> c1 >> c2;

где вообще-то отладчик ругается? на какой цифре?


Добавлено @ 03:56
Щас вернусь в чат для фондовой биржи и обматерю пару отечественных игроков, потом всётки поемняю пасопрт и ломанусь в Лос-Анджелос, куда меня уже приглашали "воротить" биржевые транзакции, но меня не устроила разница во времени с моим родным Нижневартовском

Это сообщение отредактировал(а) akizelokro - 18.11.2013, 03:58


--------------------
a = a + b; b = a - b; a = a - b;
PM MAIL   Вверх
akizelokro
Дата 18.11.2013, 04:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Крокодил
**


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

Репутация: 1
Всего: 5
Код

    std::vector< std::vector<int> > sets(N+1);

а уж извини, такая конструкция мне только в страшном сне приснится.
в трезвом!

Добавлено через 9 минут и 46 секунд
 smile 
AC/DC - Thunderstruck-Live At Donington 
Йо!


--------------------
a = a + b; b = a - b; a = a - b;
PM MAIL   Вверх
feodorv
Дата 18.11.2013, 09:04 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Комодератор
Сообщений: 2214
Регистрация: 30.7.2011

Репутация: 12
Всего: 45
Цитата(feodorv @  17.11.2013,  22:07 Найти цитируемый пост)
Здесь начинаем с 1, 2 вычёркиваем. Смотрим 3 - не пересекались с ней, 5 - вычёркиваем. Смотрим 2 - она вычеркнута, пропускаем. Смотрим 4 - не пересекались с ней, 5 уже вычеркнута. Смотрим 1 - это наш старт, 6 вычёркиваем. Итого осталось: 1, 3, 4 - это >= 3 необходимых команд, следовательно, ответ положительный. Если бы был отрицательный, то 1 бы вычеркнули, а стартовали бы с 2: 1 (вычеркнута, пропускаем), 2 (старт) -> 1 уже вычеркнута, 3 (не вычеркнута) -> 5, 4 (не вычеркнута) -> 6, 2 (старт) -> 3, 4 (не вычеркнута) -> 5 (уже вычеркнута), 1 (вычеркнута, пропускаем); итого: 2, 4 - ответ отрицательный. Потом бы вычеркнули 1 и 2, 3 - старт...

Вообще, нельзя просто вычёркивать одну команду без варианта вычёркивания другой из пары игравших друг с другом  smile 
Так что всё это не годится...


--------------------
Напильник, велосипед, грабли и костыли - основные инструменты программиста...
PM MAIL   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "C/C++: Для новичков"
JackYF
bsa

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, JackYF, bsa.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Для новичков | Следующая тема »

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


 




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


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

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