Una linked-list definisce un ciclo se scorrendola un nodo di essa viene visualizzato più di una volta. Dato un puntatore alla testa della lista, determina se essa contiene un ciclo; se essa contiene un ciclo restituisci 1, altrimenti restituisci 0.

Esempio 1

Dato head che si riferisce alla lista di nodi 1 → 2 → 3 → NULL

N.B. I numeri mostrati sono i numeri dei nodi, non i valori dei loro dati. Non esiste nessun ciclo in questa lista quindi devi restituire 0.

Esempio 2

Dato head che si riferisce alla lista di nodi 1 → 2 → 3 → 1 → NULL

In questo caso c’è un ciclo quando il nodo 3 punta all’indietro al nodo 1, quindi devi restituire 1.

Oggetto della Challenge è creare la funzione has_cycle. Essa deve contenere il parametro SinglyLinkedListNode, il riferimento alla testa della lista.

Tale funzione restituisce l’intero 1 se esiste un ciclo (sulla base di quanto illustrato sopra) e 0 in caso non esista.
Nota: se la lista è vuota head deve essere nullo.

Il codice stub legge da stdin e passa l’argomento appropriato alla funzione in oggetto. Il format dei test case personalizzati non viene descritto in questo caso a causa della sua complessità.

Opzionale

Crea una lista personalizzata

0 ≤ list size ≤ 1000

Input

I riferimenti a ciascuna delle seguenti liste collegate vengono considerati come argomenti alla funzione:

Output

0
1

Spiegazione

1. 1. La prima lista dell’illustrazione non contiene un ciclo, quindi la funzione has_cycle deve restituire 0.
2. 2. La seconda lista dell’illustrazione contiene un ciclo, quindi la funzione has_cycle deve restituire 1.

Ti viene richiesto di produrre il codice che permette, dati gli input e i constraint elencati, di stampare in output l’intero che corrisponde al punteggio massimo assegnabile alla product allocation.

N.B. Ti raccomandiamo di importare tutte le librerie e/o i framework di cui hai bisogno nel codice.

Il foglio di codice completo deve essere caricato nell’apposito spazio di upload di questa pagina all’interno di un file ZIP contenente all’interno anche il tuo CV.

Nomina il file ZIP con l’iniziale del tuo nome e il tuo cognome (es. M_Rossi).

A piacere.

Un’azienda cliente di Akkodis ha richiesto di razionalizzare la propria strategia di product allocation. Dati n prodotti, ognuno dei quali ha uno specifico valore assegnato, ti viene richiesto di suddividere essi in vari segmenti che dovranno poi essere processati/elaborati. Esistono infiniti segmenti indicizzati come 1, 2, 3 e così via.

Ci sono due constraint di seguito descritti.

• Puoi assegnare un prodotto ad un segmento con indice j se e solo se j = 1 o il segmento che ha indice j – 1 ha almeno m
• Ogni segmento deve contenere o 0 prodotti o almeno m

Ogni segmento ha un punteggio, definito come l’indice del segmento moltiplicato per la somma dei valori di tutti i prodotti che contiene. La somma dei punteggi di tutti i segmenti definisce il punteggio generale della product allocation. Il tuo obiettivo è calcolare il punteggio massimo ottenibile con un’allocazione dei prodotti.

Considera, per esempio, n = 11 prodotti e m = 3. Una possibile strategia ottimale per assegnare i prodotti è la seguente.

• Assegna i primi 3 prodotti al segmento 1
• Assegna i successivi 3 prodotti al segmento 2
• Assegna i successivi 5 prodotti al segmento 3

Da notare, per capire meglio la richiesta, che non sarebbe possibile assegnare 3 prodotti al segmento 3 e creare un quarto segmento con 2 prodotti in quanto si andrebbe a violare il secondo constraint illustrato.

Il punteggio di questa product allocation appena illustrata è dunque il seguente.

1 * (1 + 2 + 3) + 2 * (4 + 5 + 6) + 3 * (7 + 8 + 9 + 10 + 11) = 6 + 30 + 135 = 171.

Nello svolgere la Challenge, ti accorgerai che il punteggio risultante potrebbe essere molto elevato; quindi, restituiscilo in modulo 10⁹ + 7.

Nella prima linea ci sono 2 interi n e m separati da spazio.

Nella seconda linea ci sono n interi h₀, h₁, …, h_n-1 separati da spazio.

1 ≤ n ≤ 10⁶

1 ≤ m ≤ n

1 ≤ a_i ≤ 10⁹

In una singola riga, stampa il numero intero che indichi il punteggio massimo dell’allocazione in modulo 10⁹ + 7.

Input
5 2
1 5 4 2 3

Output
27

Spiegazione

Il vettore è a = [1, 5, 4, 2, 3] e m = 2. La strategia ottimale in questo caso è mettere il primo e il quarto prodotto all’interno del primo segmento e i restanti nel secondo. Facendo ciò otteniamo il seguente punteggio massimo di product allocation in modulo 10⁹ + 7:

1 * (1 + 2) + 2 * (3 + 4 + 5) = 27

Ti viene richiesto di produrre il codice che permette, dati gli input e i constraint elencati, di stampare in output l’intero che corrisponde al punteggio massimo assegnabile alla product allocation.

N.B. Ti raccomandiamo di importare tutte le librerie e/o i framework di cui hai bisogno nel codice.

Il foglio di codice completo deve essere caricato nell’apposito spazio di upload di questa pagina all’interno di un file ZIP contenente all’interno anche il tuo CV.

Nomina il file ZIP con l’iniziale del tuo nome e il tuo cognome (es. M_Rossi).

• Python
• Java
• Javascript
• C++
• C#