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]. \\ |
Текстот и решенијата дадени погоре можете слободно да ги коментирате на форумот. |