| At line 1 changed one line |
| Овој натпревар сеуште не е оддржан... |
| !!Шопинг |
|
| Во оваа задача се бараше да напишеме програма која од стандарден влез ќе прочита цени на N производи, и на стандарден излез ќе ја отпечати минималната вкупна сума која што треба да ја платиме за сите производи, доколку на секој трет производ од сметката добиваме одреден попуст D (производите на сметката можеме да ги наредиме како сакаме). \\ \\ |
| Очигледно, најмала цена ќе платиме доколку добиеме попуст на најскапите производи. Наједноставното решение би одело вака: најпрвин ги подредуваме (сортираме) производите, а потоа со еден for-циклус ги собираме цените што треба да ги платиме за секој производ (имајќи предвид дека сега нема да пресметуваме попуст на секој 3 производ, туку на оние кои што се наоѓаат на почетокот на низата, бидејќи таму ни се наоѓаат најскапите производи). Следи изворниот код на официјалното решение: |
|
| %%prettify |
| {{{ |
| #include <iostream> |
| #include <vector> |
| #include <iomanip> |
| #include <algorithm> |
| using namespace std; |
|
| int main() |
| { |
| int n, d = 0; |
| vector<int> prices; |
|
| cin >> n >> d; |
| |
| for (int i=0; i<n; i++) |
| { |
| int price; |
| cin >> price; |
| prices.push_back(price); |
| } |
| |
| sort(prices.begin(), prices.end()); |
| reverse(prices.begin(), prices.end()); |
| |
| double total_price = 0.0; |
| int cheaper_items = prices.size() / 3; |
| |
| for (int i=0; i<n; i++) |
| { |
| if (i < cheaper_items) |
| total_price += prices[i] - prices[i] * (d/100.0); |
| else |
| total_price += prices[i]; //normal price |
| } |
| |
| cout << fixed << setprecision(2); |
| cout << total_price << endl; |
| return 0; //exit code 0 |
| } |
|
| }}} |
| /% |
|
| Решението дадено погоре има сложеност O(nlogn), која што следи од комплексноста на алгоритамот за сортирање. Повеќе информации околу алгоритмите за сортирање можете да најдете [тука|Материјали За Подготовка] и [тука|ПИН 2009]. |
|
|
| !!Магацин |
|
| Во оваа задача се бараше да напишеме програма која ќе го отпечати редоследот на поставување на неколку кутии, така што за нивното поставување во магацин би требало најмалку напор (терминот напор е дефиниран во текстот на задачата). Тука ќе го претставиме наједноставното решение на оваа задача, но имајте превид дека постојат многу посложени и побрзи решенијата. \\ \\ |
|
| Она што требаше да се забележи од текстот на задачата е дека бројот на кутии е многу мал (максимум 8), така што можеме во многу кратко време да ги креираме сите можни редоследи на кутиите (вкупно 8!=40320 редоследи). Потоа, за секој добиен редослед, го пресметуваме напорот потребен за негово креирање и, доколку е минимален досега, го паметиме редоследот во некоја низа. \\ \\ |
|
| За креирање на можните редоследи (пермутации) можеме да ја користиме готовата функција next_permutation() - за оние кои што користат C++, а можеме и да ги креираме сите можни редоследи со помош на рекурзија. Тука ќе го претставиме изворниот код на функцијата која служи за креирање на редоследите (ова е многу важен алгоритам кој секој сериозен натпреварувач треба да научи да го имплементира): |
|
| %%prettify |
| {{{ |
| void recursion(vector<int> order, int position) |
| { |
| if (position >= n) |
| { |
| check_solution(order); |
| } else |
| { |
| int used[10]; |
| fill(used, used+10, 0); |
| for (int i=0; i<order.size(); i++) |
| used[order[i]] = 1; |
| |
| for (int i=1; i<=n; i++) |
| if (used[i] == 0) |
| { |
| order.push_back(i); |
| recursion(order, position+1); |
| order.pop_back(); |
| } |
| } |
| } |
| }}} |
| /% |
|
| Следи изворниот код на функцијата која служи за проверување на секој редослед (дали прекршува некое ограничување и дали за него треба најмал напор, во кој случај треба да го запамети решението во низа): |
|
| %%prettify |
| {{{ |
| void check_solution(vector<int> order) |
| { |
| int price = 0; |
| int inserted[10]; |
| fill(inserted, inserted+10, 0); |
| |
| for (int i=0; i<order.size(); i++) |
| { |
| int box = order[i]; |
| inserted[box] = 1; |
| price += weight[box-1] * i; |
| |
| vector<int> above = must_lie_above[box]; |
| |
| for (int j=0; j<above.size(); j++) |
| if (inserted[above[j]] == 0) |
| return ; //not a valid solution |
| } |
| |
| if (price < best) |
| { |
| best = price; |
| result = order; |
| } |
| } |
| }}} |
| /% |
|
| Следи уште изворниот код на главната програма (тука се наоѓаат наредби за дефинирање на некои глобални променливи и код за читање и запишување на резултатите): |
|
| %%prettify |
| {{{ |
| #include <iostream> |
| #include <vector> |
| using namespace std; |
|
| int n, best = 2100000000; |
| vector<int> must_lie_above[10]; |
| vector<int> weight; |
| vector<int> result; |
|
| int main() |
| { |
| cin >> n; |
| |
| for (int i=0; i<n; i++) |
| { |
| int w; |
| cin >> w; |
| weight.push_back(w); |
| } |
| |
| int limits; |
| cin >> limits; |
| |
| for (int i=0; i<limits; i++) |
| { |
| int ai, bi; |
| cin >> ai >> bi; |
| |
| must_lie_above[ai].push_back(bi); |
| } |
| |
| recursion(vector<int>(), 0); |
| |
| for (int i=0; i<result.size(); i++) |
| if (i == 0) |
| cout << result[i]; |
| else |
| cout << " " << result[i]; |
| |
| cout << endl; |
| return 0; |
| } |
|
| }}} |
| /% |
|
| Ова решение има сложеност О(n! * n%%sup 2/%). Решението може да се унапреди доколку користиме динамичко програмирање (мемоизација). |
|
|
| !!Тест случаи |
| Тест случаите можете да ги симнете како .zip архива [тука|Втор електронски натпревар/testovi_vtor_elektronski_2010.zip]. \\ |
| Текстот и решенијата дадени погоре можете слободно да ги коментирате на форумот. |
