#include <iostream> #include "kanapka.h" #include "message.h" #include <algorithm> #include <array> #include <vector> using namespace std; array<long long,4> zbadaj_przedzial(long long start, long long stop) { long long suma = 0, max_suma=0, min_suma=0, najgorszy=0; for (long long ii=start; ii<stop; ii++) { suma += GetTaste(ii); max_suma = max(suma, max_suma); min_suma = min(suma, min_suma); najgorszy = min(najgorszy, suma-max_suma); } //long long najlepszy = suma-najgorszy; array<long long, 4> wyniki = {suma, max_suma, min_suma, najgorszy}; return wyniki; } int main() { long long N; N = GetN(); int Nk = min((long long)NumberOfNodes(), N/2+1); // liczba instancji // long long porcja_danych = N/(Nk-1); // rozmiar przedzialu danych na instancje // int bonus = N%(Nk-1); // liczba instancji dostajacych pakiet dluzszy o 1 long long start, stop; if (MyNodeId()<Nk) { // if (MyNodeId()<=bonus) // { // start = (porcja_danych+1) * (MyNodeId()-1); // stop = start + porcja_danych +1; // } // else // ID > bonus // { // start = (porcja_danych+1)*bonus + porcja_danych*(MyNodeId()-1-bonus); // stop = start + porcja_danych; // } start = (MyNodeId()*N)/Nk; stop = ((MyNodeId()+1)*N)/Nk; array<long long,4> wyniki = zbadaj_przedzial(start, stop); for(int ii=0; ii<4; ii++) { PutLL(0, wyniki[ii]); } Send(0); } if(MyNodeId()==0) { vector<long long> sumy, max_sumy, min_sumy; long long najgorszy_wewnatrz = 0; // najgorszy kawalek kanapki wewnatrz przedzialu for (int instancja=0; instancja<Nk; instancja++) { Receive(instancja); sumy.push_back( GetLL(instancja)); max_sumy.push_back( GetLL(instancja)); min_sumy.push_back( GetLL(instancja)); najgorszy_wewnatrz = min(najgorszy_wewnatrz, GetLL(instancja)); } for (unsigned int ii=1; ii<sumy.size(); ii++) { sumy[ii] += sumy[ii-1]; // sumy skumulowane ze wszystkich przedzialow max_sumy[ii] += sumy[ii-1]; min_sumy[ii] += sumy[ii-1]; } // znalezienie najgorszego kawalka lezacego w kilku przedzialach long long najgorszy_total = najgorszy_wewnatrz, spadek; unsigned int ii=0, jj;// zapamietany_indeks=1; while(ii<max_sumy.size()-1) { for (jj = ii+1; jj<min_sumy.size(); jj++) { spadek = min_sumy[jj] - max_sumy[ii]; if (spadek<najgorszy_total) { najgorszy_total = spadek; // zapamietany_indeks = jj; } } ii++; } long long najsmaczniejszy = sumy.back() - najgorszy_total; cout<< najsmaczniejszy; } //long long odp = zbadaj_przedzial(0, N); //cout<< odp; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 | #include <iostream> #include "kanapka.h" #include "message.h" #include <algorithm> #include <array> #include <vector> using namespace std; array<long long,4> zbadaj_przedzial(long long start, long long stop) { long long suma = 0, max_suma=0, min_suma=0, najgorszy=0; for (long long ii=start; ii<stop; ii++) { suma += GetTaste(ii); max_suma = max(suma, max_suma); min_suma = min(suma, min_suma); najgorszy = min(najgorszy, suma-max_suma); } //long long najlepszy = suma-najgorszy; array<long long, 4> wyniki = {suma, max_suma, min_suma, najgorszy}; return wyniki; } int main() { long long N; N = GetN(); int Nk = min((long long)NumberOfNodes(), N/2+1); // liczba instancji // long long porcja_danych = N/(Nk-1); // rozmiar przedzialu danych na instancje // int bonus = N%(Nk-1); // liczba instancji dostajacych pakiet dluzszy o 1 long long start, stop; if (MyNodeId()<Nk) { // if (MyNodeId()<=bonus) // { // start = (porcja_danych+1) * (MyNodeId()-1); // stop = start + porcja_danych +1; // } // else // ID > bonus // { // start = (porcja_danych+1)*bonus + porcja_danych*(MyNodeId()-1-bonus); // stop = start + porcja_danych; // } start = (MyNodeId()*N)/Nk; stop = ((MyNodeId()+1)*N)/Nk; array<long long,4> wyniki = zbadaj_przedzial(start, stop); for(int ii=0; ii<4; ii++) { PutLL(0, wyniki[ii]); } Send(0); } if(MyNodeId()==0) { vector<long long> sumy, max_sumy, min_sumy; long long najgorszy_wewnatrz = 0; // najgorszy kawalek kanapki wewnatrz przedzialu for (int instancja=0; instancja<Nk; instancja++) { Receive(instancja); sumy.push_back( GetLL(instancja)); max_sumy.push_back( GetLL(instancja)); min_sumy.push_back( GetLL(instancja)); najgorszy_wewnatrz = min(najgorszy_wewnatrz, GetLL(instancja)); } for (unsigned int ii=1; ii<sumy.size(); ii++) { sumy[ii] += sumy[ii-1]; // sumy skumulowane ze wszystkich przedzialow max_sumy[ii] += sumy[ii-1]; min_sumy[ii] += sumy[ii-1]; } // znalezienie najgorszego kawalka lezacego w kilku przedzialach long long najgorszy_total = najgorszy_wewnatrz, spadek; unsigned int ii=0, jj;// zapamietany_indeks=1; while(ii<max_sumy.size()-1) { for (jj = ii+1; jj<min_sumy.size(); jj++) { spadek = min_sumy[jj] - max_sumy[ii]; if (spadek<najgorszy_total) { najgorszy_total = spadek; // zapamietany_indeks = jj; } } ii++; } long long najsmaczniejszy = sumy.back() - najgorszy_total; cout<< najsmaczniejszy; } //long long odp = zbadaj_przedzial(0, N); //cout<< odp; return 0; } |