Шопинг#
Во оваа задача се бараше да напишеме програма која од стандарден влез ќе прочита цени на N производи, и на стандарден излез ќе ја отпечати минималната вкупна сума која што треба да ја платиме за сите производи, доколку на секој трет производ од сметката добиваме одреден попуст D (производите на сметката можеме да ги наредиме како сакаме).
Очигледно, најмала цена ќе платиме доколку добиеме попуст на најскапите производи. Наједноставното решение би одело вака: најпрвин ги подредуваме (сортираме) производите, а потоа со еден for-циклус ги собираме цените што треба да ги платиме за секој производ (имајќи предвид дека сега нема да пресметуваме попуст на секој 3 производ, туку на оние кои што се наоѓаат на почетокот на низата, бидејќи таму ни се наоѓаат најскапите производи). Следи изворниот код на официјалното решение:
#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), која што следи од комплексноста на алгоритамот за сортирање. Повеќе информации околу алгоритмите за сортирање можете да најдете тука и тука.
Магацин#
Во оваа задача се бараше да напишеме програма која ќе го отпечати редоследот на поставување на неколку кутии, така што за нивното поставување во магацин би требало најмалку напор (терминот напор е дефиниран во текстот на задачата). Тука ќе го претставиме наједноставното решение на оваа задача, но имајте превид дека постојат многу посложени и побрзи решенијата.
Она што требаше да се забележи од текстот на задачата е дека бројот на кутии е многу мал (максимум 8), така што можеме во многу кратко време да ги креираме сите можни редоследи на кутиите (вкупно 8!=40320 редоследи). Потоа, за секој добиен редослед, го пресметуваме напорот потребен за негово креирање и, доколку е минимален досега, го паметиме редоследот во некоја низа.
За креирање на можните редоследи (пермутации) можеме да ја користиме готовата функција next_permutation() - за оние кои што користат C++, а можеме и да ги креираме сите можни редоследи со помош на рекурзија. Тука ќе го претставиме изворниот код на функцијата која служи за креирање на редоследите (ова е многу важен алгоритам кој секој сериозен натпреварувач треба да научи да го имплементира):
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(); } } }
Следи изворниот код на функцијата која служи за проверување на секој редослед (дали прекршува некое ограничување и дали за него треба најмал напор, во кој случај треба да го запамети решението во низа):
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; } }
Следи уште изворниот код на главната програма (тука се наоѓаат наредби за дефинирање на некои глобални променливи и код за читање и запишување на резултатите):
#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! * n2). Решението може да се унапреди доколку користиме динамичко програмирање (мемоизација).
Тест случаи#
Тест случаите можете да ги симнете како .zip архива тука
Текстот и решенијата дадени погоре можете слободно да ги коментирате на форумот.
Add new attachment
List of attachments
Kind | Attachment Name | Size | Version | Date Modified | Author | Change note |
---|---|---|---|---|---|---|
zip |
testovi_vtor_elektronski_2010.... | 14.0 kB | 1 | 20-Aug-2015 17:35 | Bojan Kostadinov |