# Diana and Numbers (div3) ... 0/100

**URL:** <https://forum.olinfo.it/t/diana-and-numbers-div3-0-100/8173>\
**Category:** Chiarimenti\
**Created:** [11 Aprile 2023, 7:39pm UTC](https://forum.olinfo.it/t/diana-and-numbers-div3-0-100/8173 "2023-04-11T19:39:56Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![AlessandroPapii](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/77aa72/32.png) [@AlessandroPapii](https://forum.olinfo.it/u/AlessandroPapii)\
**Post date:** [11 Aprile 2023, 7:39pm UTC](https://forum.olinfo.it/t/diana-and-numbers-div3-0-100/8173/1 "2023-04-11T19:39:56Z")

</div>

Mi chiedo se sia giusta la correzione… 0/100 …  
Mi sembra davvero troppo strano, per es. nel caso di tutti 1 o 2 ho letteralmente eseguito migliaia di prove e sono ragionevolmente sicuro che sia corretto.  
Ho eseguito test con decine di migliaia di input generati random fino a 100000 cifre, e verificando con un altro eseguibile più lento ed esaustivo … se il risultato fosse stato anche solo 1/100 ci crederei … ma 0/100 !!!  
E’ possibile avere anche soltanto un singolo input utilizzato nei test ? giusto per levarmi il dubbio 😃

ecco il sorgente inviato

```auto
#include <fstream>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<string> cosaRimuovere;
string outputNum = "", inputNum = "", numNoMul3 = "";
int resto = 0;

void erase_all_of(string &S, char C) {
  int p = S.find(C);
  while(p>=0) {
    S.erase(p, 1);
    p = S.find(C);
  }
}

void erase_first_of(string &S, char C) {
  int p = S.find(C);
  if(p>=0) S.erase(p, 1);
}

int mod3(string I) {
  int ret=0;
  for (char d: I) ret=(ret+(d-'0'))%3;
  return ret;
}

void rimuovi() {
  if (cosaRimuovere.empty()) {
    outputNum = "-1";
  } else {
    outputNum = "";
    for (string cifre:cosaRimuovere) {
      string soluzione=inputNum;
      for (char c: cifre) erase_first_of(soluzione, c);
      if(soluzione > outputNum) outputNum = soluzione;
    }
    outputNum.erase(0, outputNum.find_first_not_of('0'));
    if (outputNum=="") outputNum = "-1";
  }
}

void combina(int k, int iter, string rimuovi) {
  if (rimuovi.size() < k) {
    for(int i = iter; i < numNoMul3.size(); i++) {
      rimuovi += numNoMul3[i];
      combina(k, i+1, rimuovi);
      rimuovi.erase(rimuovi.end()-1);
    }
  } else {
    if ((resto==mod3(rimuovi)) && (!count(cosaRimuovere.begin(), cosaRimuovere.end(), rimuovi))) cosaRimuovere.push_back(rimuovi);
  }
}

string trova(string I) {
  numNoMul3 = inputNum = I;
  for (char c: {'0','3','6','9'}) erase_all_of(numNoMul3, c);
  resto = mod3(inputNum);
  if (resto) {
    cosaRimuovere.clear();
    for(int i=1; i<3; i++) if (cosaRimuovere.empty()) combina(i, 0, ""); 
    rimuovi();
  } else {
    outputNum = inputNum;
  }
  return outputNum;
}

int main() {
    ifstream cin("input.txt");
    ofstream cout("output.txt");
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
      string V, O;
      cin >> V;
      O = trova(V);
      cout << O << endl;
    }
    return 0;
}

```

---

<div class="post-metadata">

**Author:** ![fve5](https://forum.olinfo.it/user_avatar/forum.olinfo.it/fve5/32/3229_2.png) [@fve5](https://forum.olinfo.it/u/fve5)\
**Post date:** [11 Aprile 2023, 8:11pm UTC](https://forum.olinfo.it/t/diana-and-numbers-div3-0-100/8173/2 "2023-04-11T20:11:39Z")

</div>

Ciao, potresti spiegare meglio la logica del tuo programma? Non sono molto riuscito a seguirla. Comunque ti do un esempio (di circa 45000 sotto 10^6 che ho trovato) di output errato da parte del tuo programma: per l’input

```auto
1
212

```

il tuo programma trova come risposta 12, ma la risposta corretta è 21.

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [11 Aprile 2023, 9:15pm UTC](https://forum.olinfo.it/t/diana-and-numbers-div3-0-100/8173/3 "2023-04-11T21:15:50Z")

</div>

Anche con questi input il tuo programma non da i risultati giusti

1  
804440  
8040 non 4440

1  
100888  
1008 non 888
