Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Miniolimp как настроить написанную программу
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию Miniolimp как настроить написанную программу - 01.02.2006, 19:53

Ну вот. Собрался с силами и наклепаю задачу номер два. Тоже простая, но здесь я, лично, нашел хорошенькую оптимизацию.... но об этом позже.

Курьеры(автор Андрей Гриненко)
Входной файл: courier.in
Выходной: courier.out
Ограничение по времени: 2 сек.
Ограничение по памяти: 64 Мб

В городе X есть улица Толстунов. Все ее жители, по случайному совпадению), очень любят хорошенько пожрать. Компания НДС "Накормим Даже Слона" [укр. оригинал - ННС "Нагодуємо Навіть Слона"] решила сделать на этом деньги. Она развернула широкую сеть доставки еды заказчикам [kost: особенно она широка в тестах с двумя курьерами:]. На улице одновременно и постоянно находятся N курьеров. После получения заказа компанией продукты доставляет курьер, который находится ближе всех в момент заказа. Считать, что такой курьер всегда один и доставка осуществляется молниеносно [вмиг]. Далее курьер остается на новом месте, ждет следующего заказа.

Задание
Вычислить суммарное расстояние, которое пройдут все курьеры при выполнении всех заказов.

Входные данные
Первый ряд содержит два целых числа: N (2 <= N <= 100 000) - количество курьеров и M (0 <= M <= 100 000) - кол-во заказов.

Вторая строка содержит N натуральных чисел X1, X2, ..., XN. Тут Xi - координата начального положения i-го курьера на улице Толстунов, 1 <= Xi <= 1 000 000 000.

Третья строка содержит M натуральных чисел Y1, Y2, ..., YM. Тут Yj - координата дома j-го заказчика с улицы Толстунов. 1 <= Yj <= 1 000 000 000.

Выходные данные
Единственная строка выходного файла должна содержать целое число - искомое суммарное расстояние, которое преодолеют курьеры. [не забываем про перенос строки в конце. Я в прошлом году забыл и получил 0 баллов(]

Примеры
Код:
courier.in
3 6
5 11 3
7 8 5 1 12 4

courier.out
13

courier.in
2 5
2 3
1 1 1 1 1

courier.out
1
Киевская городская олимпиада 2006 г. первый тур. Задача #2.
Ответить с цитированием
  (#2 (permalink)) Старый
Talisman Talisman вне форума
Member
 
Сообщений: 282
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2005
По умолчанию 01.02.2006, 20:06

1) какое ограничение по времени?
2) а собственно в чем проблемы? создаем массив в который расставляем курьеров - изначально во всех ячейках, в которых есть курьер, пишем 0, в которых нету пишем -1 (минус 1), где номер ячейки - координата курьера, затем от координаты заказа идем в обе стороны по массиву, находя первую ячейку, в которой число больше минус 1, ее обнуляем, а в ячейку координаты заказа записываем содержимое ящейки, которую только что очистили + разницу между ними. (в каждой ячейке мы содержим путь курьера) далее обрабатываем следующий заказ, и т.д. ответом будет сумма всех неотрицательных значений массива - вроде все OK и просто написать, да и времени немного надо
Ответить с цитированием
  (#3 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 01.02.2006, 20:17

Цитата:
Originally posted by Talisman
[b]1) какое ограничение по времени?
2) а собственно в чем проблемы? создаем массив в который расставляем курьеров - изначально во всех ячейках, в которых есть курьер, пишем 0, в которых нету пишем -1 (минус 1), где номер ячейки - координата курьера, затем от координаты заказа идем в обе стороны по массиву, находя первую ячейку, в которой число больше минус 1, ее обнуляем, а в ячейку координаты заказа записываем содержимое ящейки, которую только что очистили + разницу между ними. (в каждой ячейке мы содержим путь курьера) далее обрабатываем следующий заказ, и т.д. ответом будет сумма всех неотрицательных значений массива - вроде все OK и просто написать, да и времени немного надо
Во-первых:
Цитата:
Originally posted by kost
[b]Ограничение по времени: 2 сек.
Во-вторых:
Ваш вариант очень медленный, хотя к оптимизации шаг был сделан.
Тем не менее, создавать массив таких размеров [ИМХО] глуповато. Надо:
1. Сортируем масив курьеров.
2. Ищем в массиве ближайшего к данному заказу.
3. И так для каждого.

Собственно, сортировка и поиск она и в Африке сортировка и поиск. Теперь думайте, может еще чего можно сделать.
Ответить с цитированием
  (#4 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 01.02.2006, 20:24

Talisman
Да и вобще. Вы напишите и сравним скорость работы на тесте в:

Код:
1 100
1
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
Я пишу на родном PHP, а Вы воплощаете свой алгоритм, скажем, на ассемблере или что Вы там знаете...
Ответить с цитированием
  (#5 (permalink)) Старый
Talisman Talisman вне форума
Member
 
Сообщений: 282
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2005
По умолчанию 01.02.2006, 20:26

Цитата:
Originally posted by kost+-->
Цитата:
Во-первых:
<!--QuoteBegin-kost
Цитата:
[b]Ограничение по времени: 2 сек.
Во-вторых:
Ваш вариант очень медленный, хотя к оптимизации шаг был сделан.

Во-вторых:
Создавать массив более чем глупо. Надо:
1. Сортируем масив курьеров.
2. Ищем в массиве ближайшего к данному заказу.
3. И так для каждого.

Собственно, сортировка и поиск она и в Африке сортировка и поиск. Теперь думайте, может еще чего можно сделать.
Во-первых: почему с массивом очень медленно? сортировка более трудоемкий по вычислениям процесс! надо сначала элементы в тотже массив занести, а потом только сортировать! (от массива Вы никуда не уйдете)
Во-вторых: для любого метода сортировки есть самая "худшая" исходная расстоновка элементов, и наверняка такое "западло" в тестах есть для каждого метода, выход есть - случайным образом перед сортировкой переставить элементы... но это тоже лишнее время...
ограничения до 100 000 - с этим в разумное время сможет справиться только лишь "Куча", да и то, сомнительно...
В-третьих: да, ваш 3 пункт можно еще оптимизировать - не для после каждого курьера надо целиком сортировать массив - достаточно "пузырьком" поднять/опустить его до новой позиции
В-четвертых: почму следует сразу рубить идеи "на корню" я считаю это неэтичным, ведь форум для того и создан, чтобы рассматривать разные подходы к решению задачи!
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
Talisman Talisman вне форума
Member
 
Сообщений: 282
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2005
По умолчанию 01.02.2006, 20:29

Цитата:
Originally posted by kost
[b]Talisman
Да и вобще. Вы напишите и сравним скорость работы на тесте в:

Код:
1 100
1
1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1 1000000000 1
Я пишу на родном PHP, а Вы воплощаете свой алгоритм, скажем, на ассемблере или что Вы там знаете...
а кто сказал, что нужно для каждой координаты заводить свой элемент массива? ведь это была только идея, а не ее реализация, нужно создавать "сквозные" элементы, т.е. если координаты с 25 по 2485 отсутствуют, то им можно отвести одну ячейку, записав в неё соответствующее значение. (зачем? просто врятли массив такой длины спокойно создастся без "извращений")
Ответить с цитированием
  (#7 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 01.02.2006, 20:32

Цитата:
Originally posted by Talisman+-->
Цитата:
Во-первых: почему с массивом очень медленно? сортировка более трудоемкий по вычислениям процесс! надо сначала элементы в тотже массив занести, а потом только сортировать! (от массива Вы никуда не уйдете)
Смотрите выше мой тест. Сравните размеры наших массивов [у меня там аж один элемент, а у вас 1 000 000 000]
<!--QuoteBegin-Talisman

[b]Во-вторых: для любого метода сортировки есть самая "худшая" исходная расстоновка элементов, и наверняка такое "западло" в тестах есть для каждого метода, выход есть - случайным образом перед сортировкой переставить элементы... но это тоже лишнее время...
ограничения до 100 000 - с этим в разумное время сможет справиться только лишь "Куча", да и то, сомнительно...
Для этого есть std::sort
Цитата:
Originally posted by Talisman
[b]В-третьих: да, ваш 3 пункт можно еще оптимизировать - не для после каждого курьера надо целиком сортировать массив - достаточно "пузырьком" поднять/опустить его до новой позиции
Согласен. Это я случайно сказал. Ведь в этом-то и вся суть, что сортировать один раз достаточно, а потом поиск в отсортированном массиве делать, что есть крайне быстро
Цитата:
Originally posted by Talisman
[b]В-четвертых: почму следует сразу рубить идеи "на корню" я считаю это неэтичным, ведь форум для того и создан, чтобы рассматривать разные подходы к решению задачи! :clever:
Затем что точно так же в одно время предложил решить подобную задачу и я))) Меня прорубили в корень и я понял раз и навсегда, что так делать НИЗЯ. Все. Удачи.
Ответить с цитированием
  (#8 (permalink)) Старый
Talisman Talisman вне форума
Member
 
Сообщений: 282
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2005
По умолчанию 01.02.2006, 20:32

Цитата:
Originally posted by kost
[b]Я пишу на родном PHP, а Вы воплощаете свой алгоритм, скажем, на ассемблере или что Вы там знаете...
я имею представление, и юзаю в различных целях следующие языки: ПШП, перл, Делфи, Асм, си, бейсик, начал осваивать лисп.

И давайте без обсираний друг друга врятли ПШП работает быстрее тогоже делфи, си или асма
Ответить с цитированием
  (#9 (permalink)) Старый
Talisman Talisman вне форума
Member
 
Сообщений: 282
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2005
По умолчанию 01.02.2006, 20:36

Цитата:
Originally posted by kost+-->
Цитата:
<!--QuoteBegin-Talisman
Цитата:
[b]
Во-вторых: для любого метода сортировки есть самая "худшая" исходная расстоновка элементов, и наверняка такое "западло" в тестах есть для каждого метода, выход есть - случайным образом перед сортировкой переставить элементы... но это тоже лишнее время...
ограничения до 100 000 - с этим в разумное время сможет справиться только лишь "Куча", да и то, сомнительно...
Для этого есть std::sort
по-моему, в олимпиадном деле не следует применять стандартные функции, т.к. свои можно оптимизировать под данную задачу, а "заводские" рассматривают еще кучу случаев, не нужных нам...
Ответить с цитированием
  (#10 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 01.02.2006, 20:36

Цитата:
Originally posted by Talisman
[b]я имею представление, и юзаю в различных целях следующие языки: ПШП, перл, Делфи, Асм, си, бейсик, начал осваивать лисп.

И давайте без обсираний друг друга :wink: врятли ПШП работает быстрее тогоже делфи, си или асма :lol:
Нет-нет. Ни в коем случае не подумайте про "обсирание". Все делается во благо отечества. Если нагрубил, тысяча извинений.

А вот про ПХП это была сатира. [насчет алгоритма]
Ответить с цитированием
  (#11 (permalink)) Старый
kost kost вне форума
Member
 
Сообщений: 1,081
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 05.10.2004
По умолчанию 01.02.2006, 20:46

Цитата:
Originally posted by Talisman
[b]по-моему, в олимпиадном деле не следует применять стандартные функции, т.к. свои можно оптимизировать под данную задачу, а "заводские" рассматривают еще кучу случаев, не нужных нам...
Мона применить и свою сортировку, но в данном случае это что ни на есть самый стандартный случай сортировки.

http://www.hardforum.ru/t46108
Ответить с цитированием
  (#12 (permalink)) Старый
michael michael вне форума
Member
 
Сообщений: 969
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 08.08.2003
По умолчанию 02.02.2006, 01:27

Задача несложная, но с подковыркой. Сначала думал решить бинарным деревом, но потом понял, что там не найти ближайшего к искомому элемента (то бишь курьера). Так что по всей видимости сортировка массива и дальнейший бинарный поиск в нём - единственное правильное решение.
Talisman, в твоём алгоритме, даже если бы было достаточно памяти, времени не хватило бы даже на инициализацию этого массива (там же несколько гигабайт памяти используется ). Крайне неэффективно.
Вот решение на C++:
Код:
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

int findnearest(vector<int> &C, int v)
{
    int n = C.size(), i = 0;
    while (n > 1)
    {
        if (C[i] == v) return i;
        n >>= 1;
        if (C[i] < v) i += n; else i -= n;
        if (i < 0) return 0;
        if (i >= C.size()) return C.size()-1;
    }
    if ((i > 0) && (abs(C[i-1]-v) < abs(C[i] - v))) return i-1;
    if ((i < C.size()-1) && (abs(C[i+1]-v) < abs(C[i] - v))) return i+1;
    return i;
}

void main()
{
    fstream in, out;
    in.open("courier.in", ios_base::in);
    out.open("courier.out", ios_base::out | ios_base::trunc);
    int N, M, a, i, j;
    in >> N >> M;               // читаем N и M
    vector<int> C;              // массив курьеров
    for (i = 0; i < N; i++)
    {
        in >> a;
        C.push_back(a);
    }
    sort(C.begin(), C.end());   // сортируем курьеров
    long long result = 0;       // результат может быть очень большим -> 64 бита
    for (i = 0; i < M; i++)
    {
        in >> a;                // читаем клиента
        j = findnearest(C, a);  // находим ближайшего курьера
        result += abs(C[j] - a);// добавляем расстояние к рез-ту
        C[j] = a;               // меняем координаты курьера
    }
    out << result << endl;      // выводим результат
    in.close();
    out.close();
}
Ответить с цитированием
Ads
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как переделать написанную программу v.k.l.chr.by Вопросы начинающих программистов 1 17.06.2011 14:03
Как запустить написанную программу Leks100 Visual C++ 2 15.06.2011 22:34
Как исправить написанную программу equilibrion C++ Builder 2 04.06.2011 23:04
Как понять написанную программу 4x10 Lisp 8 23.05.2011 08:56
Транслировать написанную программу в С++ Banned_by_IP Вопросы начинающих программистов 1 27.04.2007 23:49
Как настроить написанную программу diikar С/С++ 7 02.06.2006 16:19
Как написанную программу передать на С++ tommybolin Assembler 5 11.05.2006 23:13
Загрузка .h .cpp в написанную программу toshkaexe Visual C++ 8 24.04.2006 17:44
Как переделать программу написанную на VP5.2 в VP6.1 allig Prolog 7 19.03.2006 00:33
Как проверить на результативность написанную программу Cheshira Вопросы начинающих программистов 1 12.11.2005 19:21
Как установить свою программу написанную на С++ Nikton Visual C++ 5 03.11.2004 17:49
Оцените написанную программу Алексеев Николай Зацените! 10 11.08.2004 21:34



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов