Rezolvare completă PbInfo #1078 Adunscad

Considerăm un număr întreg N şi un şir de M cifre zecimale nenule. Să se determine dacă numărul N poate fi rezultatul unei expresii aritmetice simple (fără paranteze), formată exclusiv din cifrele şirului citit şi din operatorii aritmetici desemnaţi pentru operaţiile de adunare şi scădere (+, -).

Cerinţă

Scrieţi un program care citeşte numerele N şi M de pe prima linie a fişierului de intrare şi şirul de M cifre de pe linia următoare şi determină şi afişează expresia găsită sau valoarea 0 în cazul în care nu există soluţie.

Date de intrare

Fișierul de intrare adunscad.in conține pe prima linie numerele întregi N M, separate printr-un spaţiu, reprezentând valoarea ce trebuie obţinută la evaluarea expresiei şi numărul de cifre din şir. Linia a doua a fişierului de intrare conţine şirul celor M cifre nenule, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire adunscad.out va conține pe prima linie expresia determinată, în cazul în care există soluţie, sau valoarea 0 în cazul în care nu există soluţie.

Restricții și precizări

  • -180 ≤ N ≤ 180
  • 2 ≤ M ≤ 20
  • în şirul citit cifrele se pot repeta
  • toate cifrele din şir trebuie să apară şi în expresia aritmetică, în aceeaşi ordine în care au fost citite
  • în expresia aritmetică, orice cifră trebuie să fie precedată de un operator; în cazul în care prima cifră este precedată de operatorul '+' acesta nu se pune în expresie
  • în expresia aritmetică nu există spaţii
  • expresia aritmetică se termină cu caracterul sfârşit de linie
  • în cazul în care soluţia nu este unică se va afişa o soluţie corectă

Exemplu 1

adunscad.in

21 4
3 9 1 8

adunscad.out

3+9+1+8

Exemplu 2

adunscad.in

-1 4
1 2 3 5

adunscad.out

-1+2+3-5

Exemplu 3

adunscad.in

-7 7
1 1 1 1 1 1 1

adunscad.out

-1-1-1-1-1-1-1

Exemplu 4

adunscad.in

12 3
1 2 3

adunscad.out

0

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

//serban marinel - februarie 2011
//100 puncte
//algoritm de tip succesor pentru generarea combinatiilor de semne
//adunare in baza 2
#include <stdio.h>

FILE * Fin, *Fout;

int N, M, gasit;
int cifre[31], comb[31];

void afiseaza(int care)
{
  int i;
  gasit = 1;
  if (care == 1 || care == 3)
    {
      for (i = 1; i < M; i++)
    {
      fprintf(Fout, "%d", cifre[i]);
      if (comb[i+1])
        fprintf(Fout, "-");
      else
        fprintf(Fout, "+");
    }
      fprintf(Fout, "%d
", cifre[M]);
    }
  else
    {
      fprintf(Fout, "-");
      for (i = 1; i < M; i++)
    {
      fprintf(Fout, "%d", cifre[i]);
      if (comb[i+1])
        fprintf(Fout, "+");
      else
        fprintf(Fout, "-");
    }
      fprintf(Fout, "%d
", cifre[M]);
    }
}

int OK(void)
{
  int i, Sum = 0, Sum_ = 0;

  for (i = 1; i <= M; i++)
    if (comb[i])
      Sum -= cifre[i];
    else
      Sum += cifre[i];
  for (i = 1; i <= M; i++)
    if (comb[i])
      Sum_ += cifre[i];
    else
      Sum_ -= cifre[i];

  if (Sum == N && Sum_ == N) return 3;
  if (Sum == N) return 1;
  if (Sum_ == N) return 2;
  return 0;
}

int main(void)
{
  int i, care;

  Fin = fopen("adunscad.in", "r");
  Fout = fopen("adunscad.out", "w");

  fscanf(Fin, "%d %d
", &N, &M);     //citesc N si M
  for (i = 1; i <= M; i++)            //citesc cifrele din sir
    fscanf(Fin, "%d", &cifre[i]);
  fclose(Fin);

  for (i = 0; i < 31; i++) comb[i] = 0;
  gasit = 0;
  while (!gasit && !comb[1])          //cand comb[1] este 1 am terminat
    {
      care = OK();  //verific expresia
      if (care)     //este OK
    {
      afiseaza(care);  //afisez
      break;           //opresc ciclul
    }
      i = M;                          //adun 1 in baza 2
      while (comb[i]) comb[i--] = 0;  //caut primul 0
      comb[i] = 1;                    //il fac 1
    }
  if (comb[1]) fprintf(Fout, "0
");

  fclose(Fout);
  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 #1078 Adunscad

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