Rezolvare completă PbInfo #2261 turn

Se consideră n cuburi numerotate de la 1 la n pentru care se cunosc latura și culoarea. Să se genereze toate turnurile de înălțime H ce se pot forma cu cele n cuburi, astfel încât fiecare turn să respecte următoarele condiții:
  • orice cub se așează peste un altul ce are latura mai mare sau egală cu a lui;
  • să nu existe două cuburi consecutive de aceeași culoare;

Date de intrare

Fișierul de intrare turn.in conține pe prima linie două numere naturale n și H, iar pe următoarele n linii descrierea cuburilor. Linia i+1 conține descrierea cubului i sub forma: latură culoare.

Date de ieșire

Fișierul de ieșire turn.out va conține soluțiile generate în ordinea lexicografică a indicilor. O soluție este validă dacă conține descrierea indicilor cuburilor care alcătuiesc turnul de înălțime H.

Restricții și precizări

  • 1 ≤ n < 15
  • 1 ≤ H ≤ 50
  • 1 ≤ latura ≤ 10
  • 1 ≤ culoare ≤ 5
  • nu există cuburi identice
  • pentru datele de intrare există întotdeauna soluție

Exemplu

turn.in

5 5
1 1
2 1
1 2
2 2
3 1

turn.out

2 4 1 
4 2 3 
5 3 1 
5 4

Explicație

Primul turn este format din cuburile: 2 (2,1), 4 (2,2), 1 (1,1).
Al doilea turn este format din cuburile: 4 (2,2), 2 (2,1), 3 (1,2)
etc.

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 turn:

# include <fstream>
using namespace std;

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

struct cub{
    int l, c;
}T[101];

int st[20], h[20];
int n, H;
bool ap[101];

void tipar(int k)
{
    for(int i=1; i<=k; ++i)
        g << st[i] << ' ';
    g << '\n';
}

void back(int k)
{
    for(int x=1; x<=n; ++x){
        st[k] = x;
        if (!ap[st[k]]){
            if (h[k-1] + T[st[k]].l <= H){
                if (k == 1 || (T[st[k]].c != T[st[k-1]].c && T[st[k]].l <= T[st[k-1]].l)){
                    ap[st[k]] = 1;
                    h[k] = h[k-1] + T[st[k]].l;
                    if (h[k] == H) tipar(k);
                        else back(k+1);
                    ap[st[k]] = 0;
                }
            }
        }
    }
}

int main()
{
    f >> n >> H;
    for(int i=1; i<=n; ++i){
        f >> T[i].l  >> T[i].c;
    }

    back(1);

    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 #2261 turn

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2261 turn 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!