Problemas [Seleccao 2008]

Recommended Posts

Heys,

Hoje decidi voltar aos problemas de treino das ONI, e pela segunda vez tive run-time error e não consigo saber porque :s já perguntei na plataforma e nao tive resposta, alguem me pode dar uma ajuda?

Problema A - O cartaz do google: (RunTimeError 93pontos)

```#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <string>
#define MAX 10000010
using namespace std;

bool primes[MAX+10];
string bigger, straux;

void pre(void){
unsigned int raiz = (unsigned int) sqrt(MAX);
primes[0] = primes[1] = false;
for(unsigned int i=2; i<MAX; i++)
primes[i] = true;
for(unsigned int i=2; i<=raiz; i++)
if(primes[i])
for(unsigned int j=i*2; j<MAX; j+=i)
primes[j] = false;
return;
}

int main(void){
unsigned int qdigs, qprimes=0, num;

cin >> qdigs;
while(cin >> straux){
bigger.append(straux);
}

pre();

for(unsigned int i=0; i<=(unsigned int)(bigger.size()-qdigs); i++){
if(bigger[i]=='0'){
continue;
}
straux = bigger.substr(i, qdigs);
num = (unsigned int) atoi(straux.c_str());
if(primes[num]){
qprimes ++;
}
}

cout << qprimes << endl;
return 0;
}
```

Problema E - Primometro: (RunTimeError 65pontos)

```#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <vector>
#define MAX 3000
using namespace std;

struct CASE{
int N, K;
};

struct SOL{
int knap[MAX+100];
};

int C;
bool crivo[MAX+100];
vector <int> primos;
CASE aux;
vector <CASE> ins;
vector <SOL> dp;
SOL sock;

void input(void){
cin >> C;
for(int i=0; i<C; i++){
cin >> aux.N >> aux.K;
if(aux.K > aux.N) aux.K = aux.N;
ins.push_back(aux);
}
return;
}

void gerar_primos(void){
unsigned int raiz = (unsigned int) sqrt(MAX);
crivo[0] = crivo[1] = false;
for(unsigned int i = 2; i <= MAX; i ++)
crivo[i] = true;
for(unsigned int i = 2; i <= raiz; i ++)
if(crivo[i])
for(unsigned int j = (i*2); j <= MAX; j += i)
crivo[j] = false;
for(unsigned int i = 2; i <= MAX; i ++)
if(crivo[i])
primos.push_back(i);
return;
}

void calcular(void){
int qpr = primos.size();
sock.knap[0] = 1;
for(int i = 1; i <= MAX; i ++)
sock.knap[i] = 0;
dp.push_back(sock);
for(int i = 0; i < qpr; i ++){
for(int j = (MAX - primos[i]); j >= 0; j --)
sock.knap[(j + primos[i])] += sock.knap[j];
dp.push_back(sock);
}
return;
}

void solve(void){
gerar_primos();
calcular();
return;
}

void output(void){
for(int i = 0, indice = 0; i < C; i ++, indice = 0){
while(ins[i].K >= primos[indice])
indice ++;
cout << dp[indice].knap[(ins[i].N)] << endl;
}
return;
}

int main(void){
input();
solve();
output();
return 0;
}
```

Acho que a lógica com que estou a fazer é a correcta mas deve-me estar a falhar algo, basicamente estou a usar uma especie de memoization com knapsack.

"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share on other sites

No 1º tás a fazer o erro comum de misturar indevidamente ints com unsigned ints. Basta experimentares um input como

5

13

No 2º, ter esses structs Case e Sol parece-me altamente desnecessário. Complicação desnecessária k prejudica a leitura do código. Podes simplesmente processar cada caso directamente. Não há necessidade nenhuma de os guardar.

O rte mais provavel parece array out of bounds.

btw, não vejo memoization nenhum nesse código..

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share on other sites

Nao coloquei links para os enunciados porque naos os encontrei fora do mooshak :s

Obrigado, ja tive os 100pontos no A

(Removo o código do post ou deixo?)

Ainda não percebi muito o conceito de memoization, tenho que treinar bem isso

Processar directamente como? Eu guardei porque depois é mais fácil de gerir os resultados obtidos e só necessito de gerar uma única vez, em vez de para cada caso fazer o knapsack do 0. Vou tentar para já "descomplicar" o código.

Já agora como se faz uma declaração de vector de matrizes, não deveria ser algo como:

vector <int[30][30]> vt;

Não obtenho erro na declaração, mas quando tento adicionar algo é que são elas :x

"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share on other sites
Ainda não percebi muito o conceito de memoization, tenho que treinar bem isso

Quando resolves um problema com DP resolves o problema em estilo bottom-up (de baixo para cima). Com memoization resolves em top-down (de cima para baixo) o que vai fazer com que recalcules algumas coisas. Com memoization limitas-te a guardar o resultado de uma determinada chamada. Se já calculaste esse valor utilizas, noutro caso calculas.

Um exemplo simples para perceber isto é o shortest path com DFS. Se já passaste por um nó vais obrigatoriamente já ter calculado a distância desse nó ao teu destino, então não necessitas de recalcular esse valor, simplesmente deves utilizá-lo.

here since 2009

Share on other sites

Processar directamente como? Eu guardei porque depois é mais fácil de gerir os resultados obtidos e só necessito de gerar uma única vez, em vez de para cada caso fazer o knapsack do 0. Vou tentar para já "descomplicar" o código.

Lês os dados de cada caso de teste e calculas logo, fazes o output e depois lês o caso de teste seguinte.

Já agora como se faz uma declaração de vector de matrizes, não deveria ser algo como:

vector <int[30][30]> vt;

Não obtenho erro na declaração, mas quando tento adicionar algo é que são elas :x

isso não funciona. na prática isso é basicamente equivalente a vector <int * > vt.  Quando depois tentas usar os apontadores guardados no vector dessa maneira, estes já são inválidos. Eu evitaria ao máximo usar apontadores nesses casos, comete-se erros muito facilmente e é complicado de debuggar

Eu diria para criares uma estrutura de dados ou usar um vector de matrizes, mas isso fica meio estranho

```
vector< vector<vector<int> > > vectorMatrizes ; // que complicação :s

struct Tipo {
int mat[30][30];
// outros campos
};
vector< Tipo > vt
```

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share on other sites

Btw isso de não saberes onde encontrar os enunciados é muito mau :|  Só usas os problemas do mooshak para praticar?

http://www.dcc.fc.up.pt/oni/2011/index.cgi?page=problemas tem imensos problemas de edições anteriores. Os concorrentes nem lêm o site :|

"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share on other sites

Acho que o código está bastante mais simples mas contínuo a obter só 65 pontos, só que agora com WA :s já fiz vários casos de teste e todos de dão correctamente :S

```#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <vector>
#define MAX 3000
using namespace std;

struct KNAP{
int cfg[MAX];
};

/**/vector <int> primos; //Vector com todos os números primos necessários;
/**/vector <KNAP> knaps; //Vector com o knapsack ao nível que os números primos irão ser adicionadas;
/**/KNAP k_aux;

//Função para gerar primos através do crivo:
void gerar_primos(void){
int raiz = (int) sqrt(MAX);
bool crivo[MAX+1];
//Inicializar o crivo:
crivo[0] = crivo[1] = false;
for(int i = 2; i <= MAX; i ++)
crivo[i] = true;
//Fazer o crivo:
for(int i = 2; i <= raiz; i ++)
if(crivo[i])
for(int j = (i*2); j <= MAX; j += i)
crivo[j] = false;
//Percorrer o crivo à procura dos primos e guarda-los no vector:
for(int i = 2; i <= MAX; i ++)
if(crivo[i])
primos.push_back(i);
//Voltar ao main:
return;
}

//Função para fazer o knapsack:
void dotheknap(void){
//Inicializar a configuração do knapsack e guarda-la no vector pois é o momento em que ainda nenhum primo foi adicionado,
//necessário para quando o K for menor do que 2;
k_aux.cfg[0] = 1;
for(int i = 1; i <= MAX; i ++)
k_aux.cfg[i] = 0;
knaps.push_back(k_aux);

//Ir adicionando os números primos e guardando as configurações do knapsack:
for(int i = 0; i < (int) primos.size(); i ++){
for(int j = (MAX - primos[i]); j >= 0; j --)
k_aux.cfg[(j + primos[i])] += k_aux.cfg[j];
knaps.push_back(k_aux);
}
//Voltar ao main:
return;
}

//Função para procurar o indice da configuração de knap a ser utilizada:
int searchid(int K){
int index = 0;
for(int i = 0; i < (int) primos.size(); i++)
if(K >= primos[i])
index ++;
else
break;
return index;
}

//Função principal:
int main(void){
int C, N, K;

gerar_primos();
dotheknap();

cin >> C;
for(int i=0; i<C; i++){
cin >> N >> K;
if(K > N) K = N;
cout << knaps[searchid(K)].cfg[N] << endl;
}
return 0;
}```

"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Share on other sites

skiller, o que te dá por exemplo o caso:

1

3000 3000

Share on other sites

Está-me a dar 0, vou ver o que se passa :s

EDIT: Problema resolvido, estava a estoirar a variável :s Thanks ;D

"Eu acredito que a vida está constantemente nos testando em nosso nível de confiança, e a vida tem grande recompensa reservada àqueles que demonstram uma confiança sem fim para agir até conseguir. Este nível de resolução pode mover montanhas, mas ele tem de ser constante e consistente. Tão simples quanto isso possa soar, ainda é o denominador comum que separa aqueles que vivem seus sonhos dos que vivem simplesmente.."

Create an account

Register a new account

×

• Revista PROGRAMAR

• Wiki
• IRC
×
• Create New...