EuroDiffusion
P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))
Эту задачу в 2003 году IBM предлагала программистам кандидатам на работу. Я ее решил. Но на работу меня все равно не взяли. Предлагаю всем желающим скачать архив и оценить решение. Я не спорю код не идеален но все работает правильно.
P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))
Упс, забыл постановку задачи...
Problem D
Eurodiffusion
Input File: euro.in
On January 1, 2002, twelve European countries abandoned their national currency for a new currency, the euro. No more francs, marks, lires, guldens, kroner,... only euros, all over the eurozone. The same banknotes are used in all countries. And the same coins? Well, not quite. Each country has limited freedom to create its own euro coins:
“Every euro coin carries a common European face. On the obverse, member states decorate the coins with their own motif. No matter which motif is on the coin, it can be used anywhere in the 12 Member States. For example, a French citizen is able to buy a hot dog in Berlin using a euro coin with the imprint of the King of Spain.” (source: http://europa.eu.int/euro/html/entry.html)
On January 1, 2002, the only euro coins available in Paris were French coins. Soon the first non-French coins appeared in Paris. Eventually, one may expect all types of coins to be evenly distributed over the twelve participating countries. (Actually this will not be true. All countries continue minting and distributing coins with their own motifs. So even in a stable situation, there should be an excess of German coins in Berlin.) So, how long will it be before the first Finnish or Irish coins are in circulation in the south of Italy? How long will it be before coins of each motif are available everywhere?
You must write a program to simulate the dissemination of euro coins throughout Europe, using a highly simplified model. Restrict your attention to a single euro denomination. Represent European cities as points in a rectangular grid. Each city may have up to 4 neighbors (one to the north, east, south and west). Each city belongs to a country, and a country is a rectangular part of the plane. The figure below shows a map with 3 countries and 28 cities. The graph of countries is connected, but countries may border holes that represent seas, or non-euro countries such as Switzerland or Denmark. Initially, each city has one million (1000000) coins in its country’s motif. Every day a representative portion of coins, based on the city’s beginning day balance, is transported to each neighbor of the city. A representative portion is defined as one coin for every full 1000 coins of a motif.
A city is complete when at least one coin of each motif is present in that city. A country is complete when all of its cities are complete. Your program must determine the time required for each country to become complete.
The 2003 ACM Programming Contest World Finals sponsored by IBM Input
The input consists of several test cases. The first line of each test case is the number of countries (1 ≤ c ≤ 20). The next c lines describe each country. The country description has the format: name xl yl xh yh, where name is a single word with at most 25 characters; xl, yl are the lower left city coordinates of that country (most southwestward city ) and xh, yh are the upper right city coordinates of that country (most northeastward city). 1 ≤ xl ≤ xh ≤ 10 and 1 ≤ yl ≤ yh ≤ 10.
The last case in the input is followed by a single zero.
Output
For each test case, print a line indicating the case number, followed by a line for each country with the country name and number of days for that country to become complete. Order the countries by days to completion. If two countries have identical days to completion, order them alphabetically by name.
Use the output format shown in the example.
Sample Input Output for the Sample Input 3
France 1 4 4 6
Spain 3 1 6 3
Portugal 1 1 2 2
1
Luxembourg 1 1 1 1
2
Netherlands 1 3 2 4
Belgium 1 1 2 2
0
Case Number 1
Spain 382
Portugal 416
France 1325
Case Number 2
Luxembourg 0
Case Number 3
Belgium 2
Netherlands 2
Эту задачу в 2003 году IBM предлагала программистам кандидатам на работу. Я ее решил. Но на работу меня все равно не взяли. Предлагаю всем желающим скачать архив и оценить решение. Я не спорю код не идеален но все работает правильно.
P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))
Мне программа понравилась.
Вот если бы в код добавить комментариев, то даже Янукович не смог бы помешать IBM взять вас на работу ;)
О БЛИН. Форум откатили???? =) Половина ответов в теме канула в лету.. Юпиииии!!! :D
Тема разделена на две
1. Эта, про EuroDiffusion
2. Про комментирование исходников
Тема разделена на две
1. Эта, про EuroDiffusion
2. Про комментирование исходников
А зачем удалять мое последнее сообщение, уже после того как тема была разделена на две ? Может там был матюк ? тогда почему не был удален предыдущий ответ ( не мой )? Ээээ ребята.... по моему вы чего то испугались...
Очень нужно!!!!!!!!!!!!!!!!!! __________________
Эту задачу в 2003 году IBM предлагала программистам кандидатам на работу. Я ее решил. Но на работу меня все равно не взяли. Предлагаю всем желающим скачать архив и оценить решение. Я не спорю код не идеален но все работает правильно.
P.S. Я вот иногда думаю мож меня на работу не берут потому что я Януковича на выборах поддерживал ? :)))
А алгоритм для решения этой задачи у Вас есть?
А алгоритм для решения этой задачи у Вас есть?
Алгоритмы устарели :)), пользуйтесь OOP :))).
А насчет ООР, мне нужно на чистом С++, без ООР.
т.е. ручками нужно написать, без Visual!!!!!
ооп есть главное отличие c++ от c. и причем тут visual.. :o не понять мне, не понять.. :{
А мне не понять и фразы: "Алгоритмы устарели ), пользуйтесь OOP ))."
Интересно а насколько устарело?
Да, неясная тема. Много неоднозначных высказываний. Не буду сюда больше заглядывать, а-то ведь еще и меня устарелым признают.. :{
?????????:))))))))))??????????:)))))))))) а что здесь происходит ?
А мне не понять и фразы: "Алгоритмы устарели ), пользуйтесь OOP ))."
ну ладно поясню.....по всей видимости девушке нужен был алгоритм как средство документирования проекта....смысл фразы состоял и в том что документироание проги в виде одного большого, толстого и детального алгоритма устарело, и это надо делать в терминах OOP. Это примерно как фраза : мне нужен алгоритм работы Windows. Эта прога конечно не Windows, но вследтвии фрактального построения мира, это правило применимо и к ней. Вот блин, файл скачан 45 раз!!, кому это он интересно понадобился??? еббб....задача ж решена по секретной технологии прораммирования ....главное что б никто не догадался :))))))))))))
Я тоже скачала и выкинула.
Да эт я седня качал:D Решил ишо раз глянуть=) Так объяснитя мне, в чем сила кода? Как с ним можно эффективнее жевачки с пола соскребать?:D
эээ...я смотрю у тя как в том анекдоте : сила есть, код есть, силы кода нет :D
1. Придти завтра на работу и что нибудь соврать про свое отсутсвие.
2. Придти завтра на работу и сказать что я увольняюсь.
никак не могу определиться, предлагаю всем желающим проголосовать ( нужна помощь зала :))) ), за правильный по их мнению вариант.
Как могут устареть алгоритмы.
Интересно а насколько устарело?
Долго думал что на это ответить и наконец меня осенило : алгоритмы устарели процентов на 98%. :)))) ( да простят меня за тупость ответа ). Как было написано в одной книге тело метода должно состоять не более чем из трех строчек. О каких алгоритмах тут может идти речь ???? Остаете товарищи отстаете. :D
Долго думал что на это ответить и наконец меня осенило :
<skip>
<skip>
<skip>
"И тут Остапа понесло..." (c)И.Ильф,Е.Петров
"И тут Остапа понесло..." (c)И.Ильф,Е.Петров
Насчет skipa это ты зря :). Без паники. Я дам вам парабеллум.
P.S. Интересуемя ценами на нефть?. А на то фотке ск картой ты по всей видимости по середине ?:))))))))))))
P.S. Интересуемя ценами на нефть?.
Ну да... Подхалтуриваю на международных торгах...
А на то фотке ск картой ты по всей видимости по середине ?:))))))))))))
Нет. Я это фото делаю, поэтому меня там быть не может или может и не быть...
Но вот в маске - это я.
P.S. Долой оффтоп!
Ну да... Подхалтуриваю на международных торгах...
Нет. Я это фото делаю, поэтому меня там быть не может или может и не быть...
Но вот в маске - это я.
P.S. Долой оффтоп!
ок.....:)))).
год спустя.... файл скачан 110 раз... помоему абсолютный рекорд по download-ам на этом сайте. Принимаю поздравления и денежные переводы. Могу опубликовать всеь список вступительных заданий от IBM и решений к ним за отдельную плату.
эйййййййййййййййййййййй.... уки_дуки и прочие математически настроеные личности которые утверждали что разработка в програмировании есть выведение математических формул :))))))))))))))))))))))))))))))) вы мне на 25 апреля какого года математическое решение этой задачи обещали ? а то уже 3 мая я начинаю за вас беспокоится как бы вы там не перевешались пытаясь решить мою задачу.
Вы не подскажите как скачать исходники данной замечательной программы?
я новичок на форумах и никак не могу найту линк где можно скачать исходники
Спасибо
Вы не подскажите как скачать исходники данной замечательной программы?
я новичок на форумах и никак не могу найту линк где можно скачать исходники
Спасибо[/QUOTE]
вот исходники... а то сменой дизайна форума предыдущие исчезли.
Ты с ней носишься уже второй год, рекламируя на каждом шагу,не гнушаясь создавать липовый ажиотаж липовыми участниками форума.
Бедный arsenaltula был создан и забыт с одной лишь целью - поднять тему наверх... :D
Неужели, больше нечем похвастаться?
Чтож взгляну, что там внтри... Жди коментариев. :D
Ты с ней носишься уже второй год, рекламируя на каждом шагу,не гнушаясь создавать липовый ажиотаж липовыми участниками форума.
Бедный arsenaltula был создан и забыт с одной лишь целью - поднять тему наверх... :D
Неужели, больше нечем похвастаться?
Чтож взгляну, что там внтри... Жди коментариев. :D[/QUOTE]
расскажи об этом своему психиатру.
Код не понравился. Код сырой, нагромажденный, запутанный, одним словом некрасивый. Автор не потрудился взглянуть на задачу с математической или алгоритмической точки зрения, считая, что это как-то противоречит ООП, а решил делать "в лоб", что в купе с низкой культурой и практикой использования C++, привело к печальным результатам. Код работает, но вот как он это делает, с какими ресурсозатратами, а так же его читабельность оставляет желать лучшего.
О структуре проекта могу сказать следущее:
1) зачем тащить лишние файлы в архиве (.ncb, .asp и т.п.) ?
2) зачем тащить лишние файлы в проекте (Resource.rc, Resource.h и т.п.) ?
3) зачем подключать столько лишних файлов (см. stdafx.h) ?
Теперь объективно обо всех нюансах.
Я довольно скурпулезно разобрался в работе этого кода, и вот мои замечания:
1. Использование контейнеров STL и MFC. Само по себе использование MFC (по сути своей, оконной библиотеки) в консольном приложении - плохая практика. Причем, из STL используется только vector. Видимо, автор кода не знает о существовании в STL других контейнеров, таких как map или list, поэтому он использует CList и CMap из MFC.
2. Использование глобальных переменных, инициализация и пр. операции с которыми разбросаны по всему коду.
3. Многочисленное дублирование информации. Так, например, введено лишнее поле Space::nCountries, информация в котором идентична Space::ListOfCountries.GetSize(). Это далеко не единичный случай. Еще примеры: поле Space::nCountriesCompleted, Space::AllCountriesCompleted и т.д.
4. Огромное количество контейнеров:
CList: 1 + 3*N, где N - количество городов (!!!)
CMap: N, где N - количество городов (!!!)
std::vector: 3
C-array: 1
Это как увеличивает количество потребляемой памяти, так и приводит к избыточным пересылкам данных, что снижает производительность. Кстати, а зачем понадобился ассоциативный контейнер? Там вполне хватило бы и обычного динамического выделенного массива.
5. Используется C-string, хотя, не причин не использовать std::string. Это снижает читабельность алгоритма, приводит к потенциальным багам, т.к. проверки размерности C-string нет.
6. Множество перекрестных зависимостей. Например, класс Space агрегирует набор экземпляров класса Country, класс Country в свою очередь имеет ссылку на класс Space, а так же информацию об общем количестве своих экзеспляров. Ну это ещё что... Вот класс City тоже содержит информацию о количестве экземпляров класса Country, и ссылку на сам класс Country. Причем класс Country не агрегирует набор классов City, для этого служит глобальный (!!!) массив. Конечно, горожане должны знать в какой стране живут, да и количество стран тоже надо знать, это же школьный курс географии. Странно, что в класса City нет информации о президенте страны или хотя бы мэре города. :)
7. Удивляют так же "callback-и". Например, по заполнению каждого (!) города об этом сигнализируется отдельным вызовом классу Country.
8. Судя по коду, наибольшую трудность у автора вызвала операция передачи монет в соседние города. Для этого он завел целых три (!!!) списка, хотя хватило бы одного контейнера. Ну и весьма разветвленная схема вызовов (см. прикрепленную диаграмы вызовов).
9. Поражает и медленная скорость работы: 3000 итераций из 3х стран обрабатывались около 400 сек. (!!!), т.е. за секунду обрабатывалось менее 10 итераций (!!!). Я уверен, что скорость при должном алгоритме и архитектуре можно поднять как минимум в 10 раз.