Se consideră n mărgele numerotate de la 1 la n de culori și grad de strălucire diferite. Se generează toate posibilitățile de construire a unui colier de m mărgele distincte, astfel încât mărgelele aflate pe poziții învecinate să fie de culori diferite. Un colier este cu atât mai prețios (valoros) cu cât suma gradelor de strălucire a mărgelelor este mai mare.

Cerință

Să se determine cel mai prețios minim lexicografic colier format.

Date de intrare

Fișierul de intrare colier.in conține pe prima linie două numere naturale n și m, iar pe următoarele n linii descrierea mărgelelor. Linia i+1 conține descrierea mărgelei i sub forma: culoare grad_stralucire.

Date de ieșire

Fișierul de ieșire colier.out va conține pe prima linie, separate prin spațiu, cele m numere de ordine ale mărgelelor care formează colierul cel mai prețios.

Restricții și precizări

1 ≤ n ≤ 12
2 ≤ m < 10
gradul de strălucire al mărgelelor este cuprins în intervalul [1..100]
culoarea mărgelelor este dată sub forma unui număr natural nenul <20
nu există mărgele identice
colierul este circular – prima mărgea se învecinează cu ultima

Exemplu

colier.in

colier.out

1 2 5 4

Explicație

Colierul format din mărgelele: 1,2,5,4 este colierul cel mai prețios minim lexicografic.
Gradul total de strălucire = 10.
Cu același grad maxim de strălucire sunt de exemplu și colierele: 1 4 5 2, 6 1 4 5.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema colier1:

# include <fstream>
using namespace std;

ifstream f("colier.in");
ofstream g("colier.out");

struct colier{
    int g, c;
}C[101];

int st[101], sol[101], sumg[101];
bool ap[101];
int gmax, n, m;

void back(int k)
{
    for(int x=1; x<=n; ++x){
        st[k] = x;
        if (!ap[st[k]]) {
            if (k == 1 || (C[st[k]].c != C[st[k-1]].c)){
                ap[st[k]] = 1;
                sumg[k] = sumg[k-1] + C[st[k]].g;
                if (k == m) {
                    if (C[st[k]].c != C[st[1]].c) {
                        if (sumg[k] > gmax) {
                            gmax = sumg[k];
                            for(int i=1; i<=k; ++i)
                                sol[i] = st[i];
                        }
                    }
                }
                else if (k < m) back(k+1);
                ap[st[k]] = 0;
            }
        }
    }
}
int main()
{
    f >> n >> m;
    for(int i=1; i<=n; ++i){
        f >> C[i].c >> C[i].g;
    }

    back(1);

    for(int i=1; i<=m; ++i)
        g << sol[i] << " ";

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2256 colier1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2256 colier1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2256 colier1