Category Archives: Fase nazionale

Giornalismo d’inchiesta

Durante la sua attività giornalistica, Mino incappa in uno scoop.
Ha infatti scoperto l’esistenza di un’associazione che fu fondata e composta da due membri che si conoscevano direttamente.
Tutti gli altri membri furono successivamente reclutati se conoscevano direttamente uno o due garanti facenti già parte dell’associazione.

Mino è riuscito a ricostruire la genesi dell’attuale associazione.
Numerati i suoi membri da 1 a N, ha scritto sul suo taccuino una serie di M coppie di interi.
In particolare, la coppia composta da due interi (I,J) indica che I ha garantito per J o viceversa.
Infatti, Mino non è riuscito a stabilire chi dei due sia entrato per primo nell’associazione: sia (I,J) che (J,I) rappresentano la stessa coppia, anche perché l’ordine di numerazione dei membri non riflette necessariamente quello dell’iscrizione all’associazione (per esempio, non è detto che i membri numero 1 e 2 siano stati i fondatori o che il membro numero N sia l’ultimo arrivato).

Lo scoop di Mino consiste nell’aver trovato le prove di azioni criminali da parte di alcune triadi all’interno dell’associazione.
Una triade è composta da tre membri I, J e K dell’associazione, tali che le coppie (I,J), (I,K) e (J,K) sono tutte presenti nel taccuino di Mino (è lecito supporre che i membri di una triade si siano aiutati reciprocamente, in un qualche ordine, per entrare nell’associazione).

Per stimare il numero di controlli che Mino deve effettuare, aiutatelo a contare efficientemente quante triadi in tutto contiene l’associazione, basandovi sulle coppie trascritte nel suo taccuino e sulla modalità di reclutamento di nuovi membri: per entrare nell’associazione occorre avere conoscenza diretta di uno o due garanti che ne siano già membri.

Dati in Input

Il file input.txt è composto da M+1 righe.

  • La prima riga contiene due interi positivi M e N separati da uno spazio: M rappresenta il numero di coppie contenute nel taccuino di Mino e N il numero di membri dell’associazione.
    Tali membri sono numerati da 1 a N.
  • Le successive M righe rappresentano le coppie nel taccuino: ciascuna riga è composta da due interi differenti I e J, separati da uno spazio, per indicare la coppia (I,J).

 

Dati in Output

Il file output.txt è composto da una sola riga contenente un intero non negativo che rappresenta il numero totale di triadi in seno all’associazione.

Assunzioni

  • 1 ≤ N ≤ 100000
  • N-1 ≤ M ≤ 2N-3
  • 1 ≤ I, J ≤ N
  • Non esistono due righe in input che rappresentano la stessa coppia.
    Notare che (I,J) = (J,I), per cui non è possibile trovarle entrambe in input.

 

Esempi

input.txt output.txt
1 3 4
4 2
1 3
3 4
0
2 13 8
4 2
8 3
1 2
8 5
6 8
4 8
7 2
6 7
2 8
7 4
8 1
5 6
3 2
5

 

Note

  • L’ordine con cui si considerano i membri per definire una triade è irrilevante: per esempio, sia 2, 4, 7 che 4, 7, 2 definiscono la stessa triade e, pertanto, essa deve essere conteggiata una volta soltanto.

Numeri antipatici

E’ ben nota l’antipatia umorale della Regina di Cuori per certi numeri: per esempio, odia il numero 13; non solo, anche il 17 non è molto amato da Sua Maestà.

Ahimè, questi non sono gli unici casi poiché ci sono diversi numeri M che non sono tollerati dalla Regina e a farne le spese sono i poveri giardinieri.
Il problema è che, ogni mattina, la Regina si alza e indica ai giardinieri qual è il numero M che le è antipatico quel giorno.

Lungo il dritto viale che porta alla regale dimora, c’è un filare di N piante di rose.
Purtroppo, la Regina conta le rose mentre passeggia nel viale e non sopporta che una sequenza di una o più piante consecutive contenga un totale di M rose: ha fatto tagliare diverse teste per questioni meno gravi.
I giardinieri sono terrorizzati dal fatto che lo Stregatto ci abbia messo lo zampino, alterando il numero di rose in modo da far apparireM rose.
Aiutali a individuare il numero S di sequenze le cui piante totalizzano M rose nel filare.
Notare che alcune piante possono contenere zero rose.

Per esempio, con un filare di N=20 piante, contenenti rispettivamente 2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2 rose, il numeroM=9 appare in S=18 sequenze:

2, 3, 0, 4 , 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1 , 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4 , 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0 , 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0 , 2
2, 3, 0, 4, 0, 3, 1, 0, 1, 0, 1, 0, 0, 0, 5, 0, 4, 0, 0, 2

 

Dati in Input

Il file input.txt è composto da due righe.
La prima riga contiene due interi M e N separati da uno spazio: M è il numero antipatico alla Regina di Cuori quel giorno, e N è il numero di piante lungo il filare che costeggia il viale.
La seconda riga contiene N interi positivi separati da uno spazio: l’I-esimo intero indica il numero di rose nella I-esima pianta nel filare.

Dati in Output

Il file output.txt è composto da una sola riga che contiene l’intero positivo S, a indicare il numero di sequenze di piante nel filare che totalizzano M rose.

Assunzioni

  • 0 <= M < 231
  • 1 <= N <= 1 000 000
  • 1 <= S < 231, maledetto Stregatto!
  • 0 <= I < 231, dove I è il numero di rose in una pianta.

 

Esempi

input.txt output.txt
1 9 20
2 3 0 4 0 3 1 0 1 0 1 0 0 0 5 0 4 0 0 2
18
2 0 5
0 0 0 0 0
15

 

Nota

Una sequenza può essere composta anche da una sola pianta, se quest’ultima contiene esattamente M rose.

Sponsor e atleti

Alle Olimpiadi invernali, al pari di altre manifestazioni sportive internazionali, gli sponsor equipaggiano più di un atleta.
Per evitare che il messaggio pubblicitario arrivi al consumatore in modo confuso, un noto principio di marketing insegna che per ogni coppia di sponsor A e B deve occorrere uno solo dei seguenti due casi:

  • gli atleti ingaggiati dallo sponsor A e quelli ingaggiati dallo sponsor B sono completamente diversi e, quindi, formano due insiemi disgiunti;
  • gli atleti ingaggiati dallo sponsor A sono tutti ingaggiati anche dallo sponsor B o, viceversa, tutti gli atleti ingaggiati dallo sponsorB sono anche ingaggiati dallo sponsor A.

In altre parole, non deve mai accadere che esistano due sponsor A e B che contraddicano tale principio di marketing e, pertanto, verifichino simultaneamente tutte e tre le seguenti condizioni:

  1. vi sono degli atleti ingaggiati sia da A che da B,
  2. vi sono degli atleti ingaggiati da A ma non da B,
  3. vi sono degli atleti ingaggiati da B ma non da A.

Scrivete un programma che verifichi se N atleti ingaggiati da M sponsor rispettano il principio sopra indicato, supponendo che gli atleti siano numerati da 1 a N e che gli sponsor lo siano da 1 a M.

Dati in Input

Il file input.txt è composto da 1+N righe.
La prima riga contiene due interi positivi separati da uno spazio:

  • il primo intero rappresenta il numero N di atleti
  • e il secondo intero rappresenta il numero M di sponsor.

Le successive N righe rappresentano gli ingaggi degli atleti.
La i-esima di tale righe (1 ≤ i ≤ N) contiene 1+Q interi separati da uno spazio che rappresentano gli sponsor che hanno ingaggiato l’atleta i:

  • il primo intero rappresenta il numero Q di tali sponsor (0 ≤ Q ≤ M) ed è pari a 0 se l’atleta non ha sponsor;
  • i successivi Q interi (in ordine crescente) indicano quali sono i suoi sponsor se Q è positivo.

 

Dati in Output

Il file output.txt è composto da una riga contenente uno solo dei due seguenti possibili risultati:

  • l’intero 1 se tutti gli atleti e gli sponsor soddisfano il noto principio di marketing;
  • tre interi 0, A e B separati da uno spazio, se esistono degli sponsor A e B che non rispettano tale principio con i loro atleti ingaggiati.

 

Assunzioni

  • 1 ≤ N ≤ 10000
  • 1 ≤ M ≤ 10000
  • 1 ≤ A, B ≤ M e A ≠ B

 

Esempi

input.txt output.txt
1 4 3
1 2
2 1 3
0
1 1
1
2 4 3
1 2
2 1 2
1 2
2 1 3
0 1 2

Tè con gli amici

Il Cappellaio Matto ama offrire il suo tè verde, uno dei più pregiati al mondo.
Lo serve facendo accomodare i suoi ospiti in un tavola rotonda, i cui posti sono numerati da 1 a N in modo circolare.
Di conseguenza, i posti N e 1 risultano consecutivi.

Sfortunatamente, c’è un pegno da pagare per l’ospitalità ricevuta.
Ogni volta che il Cappellaio Matto fa squillare la sua tromba, ciascun ospite viene catapultato dal suo posto a un altro posto,
simultaneamente agli altri ospiti, secondo una tabella di mobilità M: l’ospite che siede nel posto J, viene catapultato nel posto indicato da M[J] (cioè nel posto il cui numero è scritto nella posizione J della tabella M).

Tra gli ospiti vi sono K amici: lo Stregatto li informa che dopo T squilli di tromba essi occuperanno K posti consecutivi nella tavola ma, per dispetto, non dice quali saranno questi posti.
In quell’occasione, i K amici vorrebbero circondare il Cappellaio Matto per strappargli la tromba, potendo infine degustare il tè in santa pace, ma non sanno in quali posti finiranno.

Aiuta i K amici a individuare velocemente quali posti occuperanno dopo T di squilli di tromba: poiché tali posti saranno consecutivi nella tavola, devi soltanto indicare da quale posto P in poi gli amici si troveranno.

Per esempio, vi siano N=9 ospiti, Anna, Bianca, Caterina, Daniele, Elena, Fabrizio, Giada, Hugo e Irene, in ordine crescente di posto inizialmente assegnato dal Cappellaio Matto (in realtà i nomi degli ospiti non sono rilevanti ai fini del problema).
I K=3 amici (Anna, Fabrizio, Hugo) occupano inizialmente le posizioni 1, 6 e 8; vale T=2 per la seguente tabella M di mobilità:

1 2 3 4 5 6 7 8 9 posto J
2 1 6 3 9 5 4 8 7 prossimo posto M[J]

Inizialmente, gli ospiti sono seduti come segue, dove la lettera iniziale del loro nome è riportata ai soli fini illustrativi:

1 2 3 4 5 6 7 8 9
A B C D E F G H I

Dopo il primo squillo di tromba, gli ospiti sono disposti come segue:

1 2 3 4 5 6 7 8 9
B A D G F C I H E

Dopo il secondo squillo di tromba (T=2), Hugo, Fabrizio e Anna occupano i posti consecutivi 8, 9 e 1; pertanto, bisogna restituire P=8:

1 2 3 4 5 6 7 8 9
A B G I C D E H F

Dati in Input

Il file input.txt è composto da tre righe.
La prima riga contiene tre interi N, K e T separati da uno spazio:

  • N rappresenta il numero di ospiti,
  • K il numero di amici che vogliono rendere innocuo il Cappellaio Matto,
  • T il numero di squilli di tromba necessari affinché essi occupino posti consecutivi nella tavola.

La seconda riga contiene N numeri interi separati da uno spazio, cioè la tabella di mobilità M:

  • il J-esimo intero indica il posto M[J] in cui viene catapultato l’ospite che occupa il posto J.

La terza riga contiene K interi distinti separati da uno spazio, ossia i posti inizialmente assegnati dal Cappellaio Matto ai K amici.

Dati in Output

Il file output.txt è composto da una sola riga contenente l’intero P, ossia da quale posto in poi saranno disposti consecutivamente i amici nella tavola, dopo T squilli di tromba.

Assunzioni

  • 2 <= N <= 1 000 000
  • 2 <= K <= N-1
  • 0 <= T <= 100 000 000
  • 1 <= M[J] <= N e M[I] != M[J] per I != J (dove 1 <= I <= N e 1 <= J <= N)
  • Viene sempre garantito che il valore di T soddisfa quanto richiesto dal problema.

Esempi

input.txt output.txt
9 3 2
2 1 6 3 9 5 4 8 7
1 6 8
8

Note

  • Il Cappellaio Matto non ha predisposto alcun posto a tavola per sè in quanto è continuamente impegnato a servire il tè ai suoi ospiti e a suonare la tromba.
  • E’ ammesso che sia M[J]=J per qualche valore J, in quanto non cambia la natura del problema.
  • Il Cappellaio Matto potrebbe usare una tabella Min cui, per esempio, ogni ospite viene catapultato nel posto alla sua sinistra: se gli amici non sono inizialmente vicini, allora non lo saranno mai e non esiste un valore T che soddisfa le condizioni del problema. Come precisato nelle assunzioni, situazioni simili a questa non vengono presentate come input.

Salti spettacolari

Quando il Dr. Bruce Banner si trasforma nell’incredibile Hulk, acquista sempre più forza con l’andare del tempo.
Al tempo t=0 riesce a saltare un solo metro, al tempo t=1 ne salta due, al tempo t=2 ne salta quattro e così via: in generale, al tempo t ≥ 0, riesce a saltare 2t metri.
Tuttavia l’incredibile Hulk può saltare sempre e solo nella stessa direzione: dunque ad ogni istante t può decidere se saltare in avanti alla distanza permessagli in quel momento oppure stare fermo.

Hulk deve percorrere una certa distanza D > 0, espressa in metri, e vuole effettuare il minor numero di salti.

  • Per esempio, per D=9, Hulk salta due volte (effettua un salto da 1 e uno da 8);
  • per D=7, Hulk salta tre volte (un salto da 1, uno da 2 e uno da 4);
  • per D=16, Hulk effettua il solo salto da 16.

Aiuta Hulk a calcolare quale è il minimo numero di salti che deve effettuare per coprire la distanza D.

Dati in Input

Il file input.txt è composto da una sola riga contenente un intero positivo D, che rappresenta la distanza da percorrere.

Dati in Output

Il file output.txt è composto da una sola riga che contiene il numero di salti che Hulk deve effettuare per coprire la distanza D.

Assunzioni

  • 1 <= D <= 230

 

Esempi

input.txt output.txt
1 9 2
2 7 3
3 16 1

 

Note

  • Per ogni input, esiste una sola risposta da fornire in output.

Pesca bizzarra

Pinco Panco e Panco Pinco hanno deciso di andare a pesca di ostrichette, ciascuno con la propria barca.
Poiché sanno solo andare in direzione Nord o in direzione Est, Pinco Panco e Panco Pinco decidono di dividere concettualmente la zona di pesca in quadrati adiacenti, con i lati nelle direzioni Nord-Sud e Est-Ovest, ossia disposti come in un foglio a quadretti, e numerati secondo le coordinate cartesiane intere.
Pertanto, ogni quadrato della griglia è univocamente identificato da una coppia di interi (I,J), ossia è collocato all’incrocio della colonna I e della riga J nella suddetta divisione (dove 1 <= I < 231 e 1 <= J < 231).

Ciascuna barca si muove soltanto in due direzioni, attraverso uno dei seguenti comandi numerici, che vengono inviati da una base a terra:

  • +D (=Nord) per spostarsi dal quadrato attualmente occupato (I,J) al quadrato (I, J+D) attraversando tutti i D-1 quadrati intermedi sulla colonna I, dove D è un intero positivo;
  • -D (=Est) per spostarsi dal quadrato attualmente occupato (I,J) al quadrato (I+D, J) attraversando tutti i D-1 quadrati intermedi sulla riga J, dove D è un intero positivo;

Una sequenza di comandi è quindi una sequenza di interi diversi da zero che termina con zero.

oii_2009_pesca

Pinco Panco e Panco Pinco utilizzano lo stesso quadrato A=(I0,J0) di partenza: i loro sistemi di navigazione sono sincronizzati e ogni barca riceve dalla base a terra la propria sequenza di comandi con la garanzia che i quadrati attraversati da entrambe le barche sono solo quello di partenza A e quello di arrivo B.
Soltanto alcuni dei quadrati sono pescosi e la base a terra è a conoscenza della loro posizione.

Entrambe le barche iniziano quindi il percorso dal quadrato di partenza A=(I0,J0) e ciascuna viene pilotata con la corrispondente sequenza di comandi.
Durante il percorso, ciascuna barca prende un’estremità di un’enorme rete da pesca (ebbene sì, Pinco Panco e Panco Pinco usano la rete per pescare le ostrichette!).
Le due estremità dovranno essere ricongiunte nel quadrato di arrivo B: in questo modo, verranno catturate tutte le ostrichette che si troveranno nella zona racchiusa dall’enorme rete.

Per esempio, siano I0=3 e J0=2.
Nella figura, i P=5 quadrati con un asterisco sono pescosi e i quadrati colorati indicano quelli percorsi delle due barche, con le sequenze di comandi +3 -3 +1 -2 +1 -2 0 e -2 -2 +1 -1 +1 -1 +1 -1 +2 0 (notare che possono esserci più numeri consecutivi dello stesso segno).
Risultano Q=3 quadrati pescosi nella zona delimitata dalla rete (quelli identificati da (4,5), (5,3) e (8,5)).

Aiuta Pinco Panco e Panco Pinco a calcolare il numero Q di quadrati pescosi che saranno inglobati dalla rete in questo modo.
In tale conteggio, vanno considerati anche i quadrati attraversati dalle due barche.

Dati in Input

Il file input.txt è composto da P+4 righe, dove P è il numero totale di quadrati pescosi.

  • La prima riga contiene un intero P per indicare che la zona di pesca contiene P quadrati pescosi.
  • La seconda riga contiene due interi I0 e J0 separati da uno spazio, per indicare che il quadrato di partenza è (I0, J0).
  • Le successive P righe contengono le coordinate dei P quadrati pescosi. Ogni riga è composta da due interi I e J separati da uno spazio (dove 1 <= I < 231 e 1 <= J < 231), per indicare che quel quadrato pescoso ha coordinate (I, J).
  • La penultima riga contiene una sequenza di interi diversi da 0 e terminata da uno 0, separati da uno spazio: rappresenta la prima sequenza di comandi (dove 0 è semplicemente utilizzato per indicare la fine della sequenza di interi).
  • L’ultima riga contiene anch’essa una sequenza di interi diversi da 0, terminata da zero, separati da uno spazio: rappresenta la seconda sequenza di comandi.

 

Dati in Output

Il file output.txt è composto da una sola riga contenente il numero Q di quadrati pescosi che sono inglobati dalla rete.

Assunzioni

  • 1 <= P <= 1000000
  • 1 <= I0 < 231
  • 1 <= J0 < 231
  • Una sequenza di comandi contiene M interi diversi da 0, per un qualche valore 2 <= M <= 1000000.

 

Esempi

input.txt output.txt
5
3 2
2 7
4 5
5 3
8 5
9 2
+3 -3 +1 -2 +1 -2 0
2 -2 +1 -1 +1 -1 +1 -1 +2 0
3

Scuola di supereroi

Hulk vuole organizzare una scuola per supereroi.
A tal fine, vuole invitare N supereroi che verranno numerati da 1 a N e dovranno superare due prove P.

La prima prova (P=1) prevede che i supereroi vengano messi di fronte a N cattivi, anch’essi numerati da 1 a N.
La prova è suddivisa in N round.
In ciascun round, ogni supereroe deve affrontare uno dei cattivi.
In uno stesso round, non ci possono essere due o più supereroi che affrontano lo stesso cattivo oppure due o più cattivi che si oppongono allo stesso supereroe.
Inoltre, ogni supereroe deve affrontare tutti gli N cattivi negli N round previsti per la prova.

Per esempio, per N=3, una soluzione è data dai tre round [(1,1), (2,2), (3,3)], [(1,3), (2,1), (3,2)] e [(1,2), (2,3), (3,1)], dove la coppia (I,J) indica che il supereroe numero I affronta il cattivo numero J.
In generale altre soluzioni sono possibili, mentre alcune configurazioni non sono risposte valide, come per esempio
organizzare i seguenti tre round [(1,1), (2,2), (3,3)], [(1,3), (2,1), (3,2)] e [(1,3), (2,2), (3,1)], i quali violano le regole suddette.

La seconda prova (P=2) prevede che i supereroi debbano quindi affrontarsi tra di loro.
La prova consiste in N-1 round. In ciascun round, i supereroi si affrontano a due a due.
Ogni supereroe deve affrontare tutti gli altri N-1 supereroi negli N-1 round previsti per la prova.

Per esempio, per N=4, una soluzione è data dai tre round [(1,2), (3,4)], [(1,3), (2,4)] e [(1,4), (2,3)], dove la coppia (I,J) indica che i due supereroei numero I e J si affrontano.

Aiuta Hulk a organizzare le due prove specificando le coppie che devono affrontarsi in ciascuno dei round.
Il tuo obiettivo è di organizzare N round nella prima prova e N-1 round nella seconda prova, permettendo a tutti di affrontarsi secondo le regole riportate sopra.
Per facilitarti il compito, nella seconda prova il valore di N è una potenza di 2 (N = 2, 4, 8, 16, 32, 64, …).

Dati in Input

Il file input.txt è composto da una riga contenente due interi N e P separati da uno spazio, dove N è il
numero di supereroi (e di cattivi) e P è il numero della prova da organizzare in round (ossia vale P=1 oppure P=2).

Dati in Output

Il formato del file output.txt dipende dal valore P specificato nel file input.txt.

  • Se P=1, il file output.txt è composto da N righe. Ciascuna riga individua un round e contiene 2N interi separati da uno spazio che, quando vengono presi a due a due, rappresentano le N coppie che si affrontano nel round.
  • Se P=2, il file output.txt è composto da N-1 righe. Ciascuna riga individua un round e contiene N interi separati da uno spazio che, quando vengono presi a due a due, rappresentano le N/2 coppie che si affrontano nel round.

 

Assunzioni

  • 2 <= N <= 2100

 

Esempi

input.txt output.txt
1 3 1 1 1 2 2 3 3
1 3 2 1 3 2
1 2 2 3 3 1
2 3 1 1 3 2 1 3 2
1 1 2 2 3 3
2 3 1 2 3 1
3 4 2 1 2 3 4
1 3 2 4
1 4 2 3
4 4 2 1 3 2 4
1 2 3 4
3 2 1 4

Note

  • Nella prima prova, le coppie (I,J) e (J,I) rappresentano due situazioni diverse, in quanto la prima componente della coppia indica il supereroe e la seconda indica il cattivo.
  • Nella seconda prova, le coppie (I,J) e (J,I) hanno medesimo significato: i supereroi I e J si affrontano.

Troupe televisive

Mino ha deciso di intraprendere la carriera giornalistica iniziando il suo tirocinio negli Stati Uniti, presso la prestigiosa sede newyorkese della CNN.
Il suo compito è quello di pianificare gli spostamenti giornalieri di due troupe televisive a Manhattan.

Com’è noto, le strade di Manhattan formano concettualmente una griglia di righe (street) e di colonne (avenue).
La zona assegnata a Mino corrisponde a una griglia quadrata MxM, le cui righe e colonne sono entrambe numerate da 1 a M.

La CNN dispone di due troupe televisive, ciascuna dotata di una potente telecamera con zoom telescopico:

  • la troupe R può muoversi soltanto lungo la prima colonna per riprendere ciò che succede nelle righe (street) della griglia;
  • la troupe C può muoversi soltanto lungo la prima riga per riprendere ciò che avviene nelle colonne (avenue) della griglia.

Inizialmente, entrambe le troupe sono posizionate nell’incrocio che corrisponde alla prima riga e alla prima colonna.

Il costo di spostamente di una troupe, dalla posizione I alla posizione J, è misurato come il valore assoluto della differenza di posizione, ossia |I-J| (righe o colonne, a seconda della troupe).
In questo modo, una troupe che non si sposta ha correttamente costo pari a zero.

Ogni mattina Mino riceve la lista degli N eventi che andranno ripresi nella giornata, nell’ordine temporale previsto (ossia il primo evento è il primo ad accadere e così via).
Ciascun evento è identificato dalle sue coordinate r c a indicare che avverrà in corrispondenza dell’incrocio tra la riga (street) r e la colonna (avenue) c della griglia assegnata a Mino.

Tale evento potrà essere ripreso dalla troupe R, posizionandosi sulla riga r, oppure dalla troupe C, posizionandosi sulla colonna c.
Per la troupe scelta da Mino per riprendere quell’evento, verrà pagato un costo pari al suo eventuale spostamento dalla posizione corrente alla posizione di ripresa (come definito sopra).
Infatti, non è sempre necessario spostare una troupe per riprendere due eventi successivi.

Mino deve decidere quale delle due troupe va assegnata a ciascun evento da riprendere, in modo da minimizzare il costo totale, ovvero la somma dei costi di ognuna delle due troupe.
Aiutate Mino a ottenere il costo totale minimo.

Dati in Input

Il file input.txt è composto da N+1 righe, dove N è un intero positivo.
La prima riga contiene due interi positivi N e M che rappresentano rispettivamente il numero N di eventi da riprendere e il lato M della griglia (ossia ci sono M righe e M colonne).
Le successive N righe contengono gli eventi da riprendere nell’ordine temporale in cui si presenteranno.
La k-esima di tali righe è composta da due interi r e c separati da uno spazio per indicare che il k-esimo evento (in ordine temporale) avverrà in corrispondenza dell’incrocio tra la riga (street) r e la colonna (avenue) c.

Dati in Output

Il file output.txt è composto da N righe.
La k-esima di tali righe contiene un solo carattere: la lettera R (maiuscola) oppure la lettera C (maiuscola) per indicare che il k-esimo evento (in ordine temporale) va ripreso, rispettivamente, con la troupe R oppure con la troupe C.
La scelta operata in questo modo deve minimizzare il costo degli spostamenti delle due troupe per riprendere tutti gli eventi nel loro ordine dato.

Assunzioni

  • 1 ≤ N, M ≤ 1000
  • 1 ≤ r, c ≤ M

 

Esempi

input.txt output.txt
1 3 5
4 5
3 3
2 2
R
R
C
2 7 6
4 2
5 2
6 2
4 3
4 4
4 5
4 6
C
C
C
R
R
R
R

Note

  • Nel primo esempio sopra, il costo ottenuto da RRC è 5 (=3+1+1): in questo caso, tale costo è ottimo perché lo spostamento minimo per riprendere tutti gli eventi è proprio 5. Anche RRR è una risposta corretta in quanto il suo costo è 5. Bisogna specificarne una sola in output.
  • Nel secondo esempio sopra, il costo ottenuto da CCCRRRR è ottimo perché è pari a 4 (=1+0+0+3+0+0+0). Notare che la sequenzaCCCCCCC produce invece un costo non ottimo, in quanto esso è pari a 5 (=1+0+0+1+1+1+1).
  • Se una troupe viene spostata su una riga (o colonna), vi rimane fino all’eventuale spostamento successivo, su indicazione di Mino.

Parole saturnine

Come ogni giornalista moderno che si rispetti, Mino deve imparare anche qualche lingua straniera.
Mino, che è un tipo bizzarro, opta per il linguaggio saturnino!
Su Saturno, ogni abitante ha un proprio vocabolario, che è formato dalle parole che non contengono una certa sequenza S di M caratteri consecutivi.

Per pura curiosità, Mino vuole contare quante parole sopravvivono in un tipico vocabolario saturnino.
A tal fine, considera il caso più semplice delle parole su un alfabeto binario, aventi lunghezza prefissata N ≥ M, dove S è composta da Msimboli binari.

Per esempio, se S=01, allora le parole binarie di lunghezza N=4 che non contengono S sono

  • 0000, 1000, 1100, 1110, 1111.

Se invece S=11, allora esse sono

  • 0000, 1000, 0100, 0010, 1010, 0001, 1001, 0101.

Mino vuole quindi contare le parole binarie di lunghezza N che non contengono S, solo che il loro numero può esplodere al crescere diN.
Allora, indicato con K tale numero, Mino vuole calcolare il valore di K modulo 2011 (in effetti, gira voce che i saturnini sappiano solo contare da 0 fino a 2010 perché tale è il loro numero di dita).
Aiutate Mino a calcolare tale valore.

Dati in Input

Il file input.txt è composto da due righe.
La prima riga contiene due interi positivi M e N separati da uno spazio: M rappresenta la lunghezza della sequenza binaria S da evitare eN la lunghezza delle parole binarie da contare.
La successiva riga contiene M caratteri binari '0' e '1' che rappresentano la sequenza binaria S da evitare.

Dati in Output

Il file output.txt è composto da una sola riga contenente un intero, compreso tra 0 e 2010, che rappresenta il valore K modulo 2011, doveK è il numero di parole binarie di lunghezza N che non contengono S.

Assunzioni

  • 1 ≤ N, M ≤ 1000
  • Per almeno metà dei casi di prova, su cui saranno valutati i programmi, vale 1 ≤ M ≤ 16.

Esempi

input.txt output.txt
1 2 4
01
5
2 2 4
11
8
3 2 15
11
1597
4 2 16
11
563

Note

  • Ricordiamo che a modulo b = c se e solo se c è il resto della divisione intera tra a e b.
    L’operazione di modulo in linguaggio C si effettua con il simbolo di percentuale, in linguaggio Pascal con l’operatore mod.
  • E’ importante usare sempre il modulo dopo un’operazione aritmetica di conteggio perché i valori intermedi generati possono richiedere più di 32 bit.
    Poiché il risultato è K modulo 2011, suggeriamo di sfruttare il fatto che (A + B + C) modulo 2011 = ((A + B) modulo 2011) + C) modulo 2011.
    Stessa cosa per le altre operazioni aritmetiche.
    In questo modo, i risultati intermedi sono sempre modulo 2011 e possono essere mantenuti in una normale variabile intera a 32 bit.

Somme di sequenze

Data una sequenza S di N numeri interi, tipo 11 -4 52 -7 -2 -20, vogliamo computare la somma di tutti i numeri in S avvalendoci di un robot con capacità limitate. Infatti, tale robot può soltanto effettuare la somma intermedia Y di due numeri A e B consecutivi nella sequenza, rimpiazzando A e B con Y e ottenendo così una sequenza più corta (con un intero in meno).

Per effettuare tale somma intermedia Y e produrre la sequenza più corta, il robot consuma esattamente |Y| unità di energia (dove |Y|indica il valore assoluto di un numero intero Y).

Per calcolare la somma degli N numeri in S sono quindi necessarie N-1 somme intermedie. Pur disponendo di energia sufficiente per eseguire le N-1 somme intermedie in tale calcolo, il robot ha problemi con i picchi di energia. In altre parole, vogliamo che il massimo consumo energetico per una somma intermedia (il picco energetico) sia minimizzato.
sequenze
Nel caso di cui sopra una soluzione ottima è data da

11 -4 52 -7 (-2 -20)
11 -4 52 (-7 –22)
11 -4 (52 -29)
(11 -4) 23
(7 23)
30

In questo caso i valori intermedi ottenuti sono -22, -29, 23, 7, 30 e il picco energetico è 30, essendo il massimo tra |-22|, |-29|, |23|, |7|e |30|.
Meglio di così non si può fare in quanto il valore della somma è 30.

Un altro esempio è dato dalla sequenza

(7 -1) -8
(6 -8)
-2

in cui le somme intermedie hanno generato 6 e -2 e quindi il picco energetico è pari a 6. Tale picco è minimo poiché l’altra possibilità consiste nel sommare prima -1 con -8 e poi 7 con -9, dando luogo a un picco pari a 9.

Scrivete un programma che calcoli il minimo picco energetico per una sequenza di interi.

Dati in Input

Il file input.txt è composto da due righe.

  • La prima riga contiene un intero positivo che rappresenta il numero N di interi nella sequenza d’ingresso.
  • La successiva riga contiene N interi, separati da uno spazio, che rappresentano la sequenza su cui computare la somma.

 

Dati in Output

Il file output.txt è composto da una sola riga che contiene l’intero non negativo E, il quale rappresenta il picco energetico minimo del robot per calcolare la somma degli interi nella sequenza d’ingresso.

Assunzioni

  • 2 ≤ N ≤ 500

Esempi

input.txt output.txt
1 6
11 -4 52 -7 -2 -20
30
2 5
4 7 -9 8 -10
2
3 3
7 -1 -8
6
4 5
0 0 0 0 0
0