Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Qualcuno e' riuscito a risolverlo con un algoritmo veloce? (Deve terminare entro 5 minuti).
Problema:
Testo quotato
After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest.
John knows the following: for each index i, where k <= i < n, m[ i] is the minimum non-negative integer which is *not* contained in the previous *k* values of m.
For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1.
John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.
Given the first k values of m, calculate the nth value of this array. (i.e. m[n - 1]).
Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given positive integers a, b, c and r, the known values of m can be calculated as follows:
m[0] = a
m[i ] = (b * m[i - 1] + c) % r, 0 < i < k
Input
The first line contains an integer T (T <= 20), the number of test cases.
This is followed by T test cases, consisting of 2 lines each.
The first line of each test case contains 2 space separated integers, n, k (1 <= k <= 105, k < n <= 109).
The second line of each test case contains 4 space separated integers a, b, c, r (0 <= a, b, c <= 109, 1 <= r <= 109).
Output
For each test case, output a single line containing the case number and the nth element of m.
After sending smileys, John decided to play with arrays. Did you know that hackers enjoy playing with arrays? John has a zero-based index array, m, which contains n non-negative integers. However, only the first k values of the array are known to him, and he wants to figure out the rest.
John knows the following: for each index i, where k <= i < n, m[ i] is the minimum non-negative integer which is *not* contained in the previous *k* values of m.
For example, if k = 3, n = 4 and the known values of m are [2, 3, 0], he can figure out that m[3] = 1.
John is very busy making the world more open and connected, as such, he doesn't have time to figure out the rest of the array. It is your task to help him.
Given the first k values of m, calculate the nth value of this array. (i.e. m[n - 1]).
Because the values of n and k can be very large, we use a pseudo-random number generator to calculate the first k values of m. Given positive integers a, b, c and r, the known values of m can be calculated as follows:
m[0] = a
m[i ] = (b * m[i - 1] + c) % r, 0 < i < k
Input
The first line contains an integer T (T <= 20), the number of test cases.
This is followed by T test cases, consisting of 2 lines each.
The first line of each test case contains 2 space separated integers, n, k (1 <= k <= 105, k < n <= 109).
The second line of each test case contains 4 space separated integers a, b, c, r (0 <= a, b, c <= 109, 1 <= r <= 109).
Output
For each test case, output a single line containing the case number and the nth element of m.
Case #1: 8
Case #2: 38
Case #3: 41
Case #4: 40
Case #5: 12
Ho creato i primi k valori di m con la formula
m[0]=a;
m=(b*m[i-1]+c)%r;
e mi torna che m contiene :
34 71 82 4 28 43 16 84 78 50 81 64 17 24 89 69 8 79 87 92 83 41 39 62 40 2 51 21 75 36 48 7 42 76 73 59 26 66 91
come può il risultato (ovvero l'n-esimo valore di m) essere 8 se 8 è contenuto in già nei primi k elementi?
Magari ho capito male il testo...
quello che ho capito è questo :
i primi k valori della matrice son calcolati secondo la formula che danno loro e con le loro variabili...
i valori da k a n li dobbiamo calcolare noi.. e sappiamo che ogni valore che calcoliamo è il valore minimo che non è contenuto nella parte antecedente della matrice..
se è come ho capito questo è il codice che ho pensato :
Secondo me c'è qualche trucco per dedurre il nuovo elemento. Qualsiasi algoritmo con complessità lineare non può andar bene (e non c'è modo di scendere al di sotto di O(n) con questo approccio).
Secondo me c'è qualche trucco per dedurre il nuovo elemento. Qualsiasi algoritmo con complessità lineare non può andar bene (e non c'è modo di scendere al di sotto di O(n) con questo approccio).
allora ho scoperto le seguenti cose :
esiste una serie di k+1 elementi che si ripete sempre, quindi basta calcolare questi...
ho trovato un modo per "dedurre il nuovo elemento" ma sto avendo alcuni problemi a ottimizzare il codice
il mio scopo è aumentare l'efficienza dell'algoritmo non usando insert_order quando inserisco i nuovi visto che per rilevare quale numero mettere ho già gli elementi tra i quali inserirlo... non riesco a capire cosa c'è di sbagliato nella parte commentata visto che impazzisce...
Ultima modifica effettuata da Maury91 il 27/01/2013 alle 14:32
Probabilmente quella serie è dovuta all'algoritmo che genera i numeri pseudocasuali. Comunque una lista non è la struttura dati migliore. E poi se mischi il codice che gestisce la lista con quello che risolve il problema non si capisce molto: sono su due livelli di astrazione diversi.
si ma se uso l'insert_order quando ho già qual'è il nodo in cui inserire perdo di efficienza...
a me la lista sembra la struttura migliore per gestire il problema... tra tutti gli algoritmi che ho provato... questo senza nemmeno essere ottimizzato risulta il più veloce...