Non so per quale motivo l’algoritmo su questi testcases da’ output errati
Allora, l’algoritmo si basa su due array binari in cui ci possono essere solo 0 e 1, e ogni volta che eseguo calcolaBin e calcolaTri, il primo posto degli due array viene aumentato di 1, e se e’ maggiore di 1, si trasforma in 0, e il posto successivo viene aumentato di 1, fino a quando non c’e’ nessun 2 nell’array. Inoltre, ogni volta che aggiungo o tolgo qualcosa durante il calcolo, quella quantita’ viene calcolata anche su un contatore che conta gli 1.
Mi basta anche solo input possibili per cui questo l’algoritmo non funziona.
#include <bits/stdc++.h>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
int array1[28];
int array2[28];
int act1 = 1;
int act2 = 1;
int calcolaBin()
{
int app1 = act1;
array1[0]++;
app1++;
if(array1[0] > 1)
{
for(int j = 0; j<28; ++j)
{
if(array1[j] > 1)
{
array1[j] = 0;
app1--;
array1[j+1]++;
}else
break;
}
}
act1 = app1;
return app1;
}
int calcolaTri()
{
int app2 = act2;
array2[0]++;
app2++;
if(array2[0] > 1)
{
for(int j = 0; j<28; ++j)
{
if(array2[j] > 2)
{
array2[j] = 0;
app2 -= 2;
array2[j+1]++;
}else
break;
}
}
act2 = app2;
return app2;
}
void soluzione(int N, int num[])
{
fill(array1, array1+28, 0);
fill(array2, array2+28, 0);
//parto da numero 1
array1[0] = 1;
array2[0] = 1;
vector<int>ris;
ris.reserve(10010);
map<int, int>orders;
for(int i = 0; i<N; ++i)
{
orders.insert({num[i], i});
}
if(orders.count(1))
{
auto app = orders.find(1);
ris[app->second] = 1;
orders.erase(1);
}
int max = 0;
for(int i = 0; i<N; ++i)
{
if(num[i] > max) max = num[i];
}
auto temp = orders.begin();
int pre = 1;
int cont = 1;
while(!orders.empty())
{
++cont;
int app1 = calcolaBin();
int app2 = calcolaTri();
if(app1 == app2)
{
pre = pre + 1;
}
if(cont == temp->first)
{
ris[temp->second] = pre;
orders.erase(temp);
temp = orders.begin();
}
}
for(int i = 0; i<N; ++i)
{
out << ris[i] << " ";
}
}
main()
{
int N;
in >> N;
int num[N];
for(int i = 0; i<N; ++i)
{
in >> num[i];
}
soluzione(N, num);
}