Keylogger-OIS round 4

Aiuto
1

Salve a tutti!
Stavo risolvendo il problema “pin” del round 4 delle OIS, è mi è successa una cosa alquanto strana:
provando il codice in locale, risolveva correttamente entrambi i casi d’esempio. Sottoposto il codice, ho ottenuto uno 0/100 con un errore anche nel subtask 0, che dovrebbe corrispondere ai casi d’esempio stessi. Qualcuno ha idea di cosa potrebbe essere?

2

potresti mandare il codice?

6

(chiedo scusa per i vari messaggi eliminati ma ho poca dimestichezza con l’opzione per sfocare gli spoiler)
#include <bits/stdc++.h>

using namespace std;

ifstream in(“input.txt”);
ofstream out(“output.txt”);

int N, K;
map <int, int> rip;

int main(){
cin >> N >> K;
int corr=0;
int mod = pow(10, K)+1;
for(int i=0; i<K; i++){
int a;
cin >> a;
corr*=10;
corr+=a;
}

rip[corr]++;
int mas=1;
int idxmas=corr;

for(int i=K; i<N; i++){
    int a;
    cin >> a;
    corr*=10;
    corr+=a;
    corr%=mod;
    rip[corr]++;
    if(rip[corr]>mas){
        idxmas=corr;
        mas=rip[corr];
    }
}

vector <int> sol;
while(idxmas>0){
    sol.push_back(idxmas%10);
    idxmas/=10;
}
while(sol.size()<K)
    sol.push_back(0);

for(int i=sol.size()-1; i>=0; i--)
    cout << sol[i] << " ";

}

7

L’errore è in queste righe:

while(idxmas>0){
    sol.push_back(idxmas%10);
    idxmas/=10;
}

idxmas > 0 potrebbe non considerare un numero che inizia per 0. Sostituisci la condizione col fatto che il numero consiste comunque di K cifre.

8

dopo c’è un while(sol.size()>0) che risolve questo problema

9

Ma il fatto strano è che provando i casi d’esempio sul mio pc l’output è corretto, mentre sottoponendo risulta sbagliato uno dei due

10

Ne sei certo?
A me risulta che la soluzione sbagli il secondo caso di esempio:

./sol/forum_EVAL < input/input1.txt
9 2 5 0 %
11

Sì, a me stampa correttamente 2 5 0 1

12

Con esattamente il codice che hai messo sopra? Mi pare strano…

Comunque il problema dovrebbe stare qua:

Se di un numero XYYYY vuoi ottenere YYYY devi prendere il resto della divisione per 10^4, non per 10^4+1.

13

Si ma la funzione pow restituisce un double, e ho trovato che nel caso di 10^K restituisce (10^K)-1 in quanto tronca tale double(che suppongo sia in realtà uguale a 999,9999…) alla parte intera.

14

OK risolto, era proprio lì l’errore. Però ora mi sorge un altro dubbio: come è possibile che la funzione pow si comporti in due modi diversi? sono sicuro che essa si comporti come ho scritto sopra, perlomeno sul mio pc…

15

:see_no_evil:

A proposito di pow se n’è già parlato qua:

Probabilmente l’implementazione delle librerie standard è diversa (e quasi certamente peggiore) nelle versioni più vecchie del compilatore oppure nel porting di MinGW (se stai usando windows). Basta poco per propagare errori con numeri in floating point IEEE 754.

16

OK, grazie mille per la disponibilità

17

Io l’ho implementato in C ma non tutti i casi vengono risolti correttamente.
Qualche suggerimento?

#include<stdio.h>
#include<stdlib.h>

int n;
int pin[9];
int lunghezza;
short digits[1000000];
int numero;

int quanti(int partenza, int p[])
{
    int i;
    int j;
    int cont=0;
    int flag;
    for(i=partenza; i+lunghezza<n; i++)
    {
        flag=1;
        for(j=0; flag && j<lunghezza; j++)
        {
            if(p[j]!=digits[i+j])
                flag=0;
        }
        if(flag)
        {
            cont++;
            i+=lunghezza;
        }
    }
    
    return cont;
}

main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    
    scanf("%d", &n);
    scanf("%d", &lunghezza);
    int i;
    int j;
    int temp;
    
    for(i=0; i<n; i++)
    {
        scanf("%hi", &digits[i]);
    }
    for(i=0; i<lunghezza; i++)
        pin[i]=digits[i];
    numero=1;
    
    for(i; i<n; i++)
    {
        temp=quanti(i, &(digits[i]));
        if(temp>numero)
        {
            numero=temp;
            for(j=0; j<lunghezza; j++)
                pin[j]=digits[i+j];
        }
    }
    for(i=0; i<lunghezza; i++)
        printf("%d ", pin[i]);
}