Cerința

În clasa a 10-a Alina, Bogdan şi Clara se întâlneau în fiecare săptămână să se joace BlitzCatan. Ei aveau la dispoziţie o repriză de 2 ore pe care o foloseau din plin, fiecare joc durând cel puţin 30 de minute. Cei trei prieteni, dornici să reţină cine a câştigat fiecare joc au vrut sa noteze într-un carneţel. Ei s-au temut ca cineva le va citi carneţelul, aşa că au procedat astfel:

la finalul unui joc i, câştigătorul c, alege un număr secret \(m_i\) > 0 astfel încât \(m_i\) % 3 = c (Alina alege un multiplu de 3 când câştigă, Bogdan un multiplu de 3+1, Clara un multiplu de 3+2)
la finalul celor 2 ore, ei calculează \(T = \sum\limits_{i=0}^J (m_i – 1)*m_i*(m_i + 1) \) unde J este numărul de jocuri, şi notează T în carneţel

La reuniunea de 10 ani după liceu Alina, Bogdan şi Clara dau de carneţel. Fiecare din ei crede ca el/ea a câştigat cele mai multe jocuri. Ei nu au timp să verifice decriptând semnificaţia numerelor din carneţel, aşa că te roagă pe tine să îi ajuţi, spunându-le pentru fiecare număr din el, câte jocuri reprezintă, cine a câştigat fiecare din ele, şi cu ce număr secret.

Date de intrare

Fişierul blitzcatan.in va conţine: pe prima linie N – numărul de numere din carneţel şi pe următoarea linie \(T_1 T_2 … T_N\) cele N numere separate prin câte un spaţiu

Date de ieșire

In fişierul blitzcatan.out se vor afişa N linii: pe linia i se afişează J numărul de jocuri jucate în repriza I şi J perechi de numere \(c_i\), \(m_i\), separate prin spaţiu, unde \(c_i\) este câştigătorul, iar \(m_i\) este numărul ales de câştigător.

Restricții și precizări

Se garantează că există o soluţie pentru fiecare repriză.
Pentru fiecare repriza \(T_i\), dacă există mai multe soluţii, se va afişa cea care conţine un număr minim de jocuri. Nu contează ordinea în care se scriu cele J perechi de numere.
0 < T_i <= 10⁹, pentru fiecare repriza i
N <= 10

Exemplu

blitzcatan.in

2
120 1001616

blitzcatan.out

1 2 5
2 0 12 1 100

Explicație

120: S-a jucat un joc. Clara a câştigat şi a ales numărul 5.
1001616: S-au jucat 2 jocuri. Alina a câştigat un joc şi a ales numărul 12. Bogdan a câştigat un joc şi a ales numărul 100.

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

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#include <utility>
#include <vector>
#include <iterator>
#include <algorithm>

#define t_s2pit vector<pair<int, pair<int, int> > >::iterator
#define MAX_N_P 1001 // numarul maxim de numere piramidale
#define MAX_T 1000000001

using namespace::std;

vector<int> s1p;
vector<pair<int, pair<int, int> > > s2p;
int n_s1p, n_s2p;

void print_secrets(vector<int> secrets, FILE* fout) {
  fprintf(fout, "%d", (int) secrets.size());
    vector<int>:: iterator it;
  for(it = secrets.begin(); it != secrets.end(); it++) {
    // + 2 pentru ca for loopul pentru numere piramidale
    // e 0-indexat dar incepe cu s = 2
    fprintf(fout, " %d %d", (*it + 2) % 3, *it + 2);
  }
  fprintf(fout, "\n");
}

bool sum_of_two(t_s2pit *s2p_start,
                int nr, vector<int> *secrets) {
    t_s2pit pos = lower_bound(*s2p_start, s2p.end(),
                            make_pair(nr, make_pair(0, 0)));
    *s2p_start = pos;
  if(pos != s2p.end() && pos->first == nr) {
    secrets->push_back(pos->second.first);
    secrets->push_back(pos->second.second);
    return true;
  }

  return false;
}

bool pred(const std::pair<int, std::pair<int, int > > &a,
          const std::pair<int, std::pair<int, int > > &b) {
  return a.first == b.first;
}

int main() {
  FILE* in = fopen("blitzcatan.in", "r");
  FILE* out = fopen("blitzcatan.out", "w");

  int n;
  fscanf(in, "%d", &n);

  s1p.reserve(MAX_N_P);
  s2p.reserve(MAX_N_P * MAX_N_P);

  // precalculam toate numerele piramidale <= MAX_T
  for(int i = 2; i <= MAX_N_P; i++) {
    s1p.push_back((i-1) * i * (i+1));
  }
  n_s1p = s1p.size();

  // precalculam toate sumele de 2 numere piramidale
  for(int i = 0; i < n_s1p; i++) {
    for(int j = i; j < n_s1p && s1p[i] + s1p[j] < MAX_T; j++) {
      s2p.push_back(std::make_pair(s1p[i] + s1p[j],
                                   std::make_pair(i, j)));
    }
  }

  // sortam s2p si eliminam dublurile
  std::sort(s2p.begin(), s2p.end());
  s2p.erase(unique(s2p.begin(), s2p.end(), pred), s2p.end());
  n_s2p = s2p.size();

    t_s2pit it_2;
  int nr;
  std::vector<int> secrets;
  for(int i = 0; i < n; i++) {
    secrets.clear();
    fscanf(in, "%d", &nr);

    while(1) {
      // un numar piramidal
      vector<int>::iterator pos = std::lower_bound(s1p.begin(), s1p.end(), nr);
      if(pos != s1p.end() && *pos == nr) {
        secrets.push_back(pos - s1p.begin());
        break;
      }

      // doua numere piramidale
            it_2 = s2p.begin();
      if(sum_of_two(&it_2, nr, &secrets)) {
        break;
      }

      // trei numere piramidale
      bool done = false;
            it_2 = s2p.begin();
      for(int j = n_s1p - 1; j >= 0;  j--) {
                if (s1p[j] >= nr) continue;
        if(sum_of_two(&it_2, nr - s1p[j], &secrets)) {
          secrets.push_back(j);
          done = true;
          break;
        }
      }
      if(done) break;

      // patru numere piramidale
      done = false;
            it_2 = s2p.begin();
      for(int j = n_s2p - 1; j >= 0; j--) {
              if (s2p[j].first >= nr) continue;
        if(sum_of_two(&it_2, nr - s2p[j].first, &secrets)) {
          pair<int, int> idx = s2p[j].second;
          secrets.push_back(idx.first);
          secrets.push_back(idx.second);
          done = true;
          break;
        }
      }
      if(done) break;

      // nicio solutie
      assert(false);
      break;
    }

    print_secrets(secrets, out);
  }
    //printf("%d %d\n", s1p.size(), s2p.size());
  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 #1831 Blitzcatan

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