Problema Forgotten Pencil Case 95%


#1

Ciao a tutti,
ho risolto il problema forgotten pencil case con questo semplice algoritmo:

#include <fstream>
#include <iostream>
using namespace std;
int minStud(int[],int,int);

int main()
{
ifstream in("input.txt");
ofstream out("output.txt");

int num;

in >> num; //totale da pagare

int studenti[num];
int noPencil=0;

for(int i=0;i<num;i++)
{
  int a;
  in>>a;
  if(a==0) noPencil++;
  studenti[i]=a;
}

int min=minStud(studenti,num,noPencil);

out << min << endl;
in.close();
out.close();
}

int minStud(int v[],int l,int noPencil)
{
    if(v[0]==0&&v[1]>1)
    {
      v[0]++;
      v[1]--;
      noPencil--;
    }
    
    for(int i=1;i<l-1;i++)
    {
      if(v[i]==0)
      {
        if(v[i-1]>1)
        {
          v[i-1]--;
          v[i]++;
          noPencil--;
        }else if(v[i+1]>1)
              {
                   v[i+1]--;
                   v[i]++;
                   noPencil--;
                   i++;       
              }
      }
    }
    if(v[l-1]==0&&v[l-2]>1) noPencil--;
    return noPencil;
}

che segue un banale approccio Greedy.
Ottengo però 95% sbagliando 2 test case.
Qualcuno ha qualche suggerimento?

Grazie


#2

All’inizio dava anche a me questo errore, l’ho risolto mettendo un paio di controlli che N fosse diverso da 1.
Più che altro penso che nel primo e nell’ultimo if del codice che hai postato, non avendo il controllo che N!=1 ti puoi trovare in situazioni dove va a testare se pens[1] sia maggiore di 1 quando pens[1] non esiste, generando una situazione di undefined behavior (o almeno penso si chiami così XD).

Spero di esserti stato utile


#3

Grazie, ho aggiunto all’inizio della funzione:
if(l==1) return noPencil;
e ho risolto.
Non so perchè ma ero convinto che N fosse >=2…
Grazie per l’aiuto