Tag Archives: string

Trova la parola

Fase Territoriale 2013

ter_2013_trovaparolaVisto il successo del gioco Ruzzle, che riprende il noto paroliere, i giochi basati su trovare parole stanno vivendo un periodo molto popolare.
Luciano, patito di giochi di tutti i tipi, ha ideato un nuovo gioco, che funziona nel modo seguente: avete una griglia di caratteri e una parola da trovare nella griglia, partendo dalla cella in alto a sinistra.
Le uniche mosse consentite sono gli spostamenti a destra o in basso.
Ad esempio, considerate la seguente griglia e la parola olimpiadi:

O L I V E N T
G Q M P W E R
G T R I A Y E
I U I C D P E
A F C O I G H
J K X C V R S
R O M I T A A
S T A N L E E

In questo caso, la sequenza di spostamenti è DDBDBDBB, rappresentando gli spostamenti a destra con il carattere D e quelli in basso con il carattere B.
Non esiste alcuna soluzione, invece, se la parola da cercare è olimpionico.

Il vostro compito consiste nello scrivere un programma che, ricevute in ingresso una parola (da cercare) e una griglia, restituisca la sequenza di spostamenti, qualora esista una soluzione, oppure stampi ASSENTE.
Se dovessero esistere molteplici sequenze di spostamenti corrette, è sufficiente stamparne una qualunque.

Dati di input

Il file input.txt è composto da 2+R righe.

  • La prima riga contiene due interi positivi R e C: le dimensioni della griglia, ovvero il numero di righe R e il numero di colonne C.
  • La riga successiva contiene P, una parola da cercare, rappresentata da una stringa lunga almeno 2 caratteri (alfabetici maiuscoli) e al massimo R+C-1 caratteri.
  • Le rimanenti R righe del file contengono le righe della griglia, rappresentate da stringhe di C caratteri alfabetici maiuscoli.

Dati di output

Il file output.txt è composto da una sola riga contenente una stringa di testo: la sequenza di spostamenti necessari per trovare la parola nella griglia, se la parola è presente, oppure la stringa “ASSENTE” (senza le virgolette).

Assunzioni

  • 2 ≤ R, C ≤ 100.

Esempi di input/output

input.txt output.txt
8 7
OLIMPIADI
OLIVENT
GQMPWER
GTRIAYE
IUICDPE
AFCOIGH
JKXCVRS
ROMITAA
STANLEE
DDBDBDBB
8 7
OLIMPIONICO
OLIVENT
GQMPWER
GTRIAYE
IUICDPE
AFCOIGH
JKXCVRS
ROMITAA
STANLE
ASSENTE

Espressione di parentesi

Olimpiadi Italiane a Squadre

Giorgio ha scritto un programma contenente una serie di espressioni molto elaborate, formate ciascuna da un gran numero di parentesi di tutti i tipi, e cioè:

  • angolate: ’<’ e ’>
  • tonde: ’(’ e ’)
  • quadrate: ’[’ e ’]
  • graffe: ’{’ e ’}

Purtroppo, quando ha provato ad eseguirlo, il compilatore gli ha detto che c’è un errore senza nemmeno dirgli in quale espressione si trova!
Aiutalo controllando quali espressioni sono ben formate e quali no.

Dati di input

Il file input.txt è composto da due righe.

  • La prima riga contiene l’unico intero N.
  • La seconda riga contiene la stringa E.

Dati di output

Il file output.txt è composto da un’unica riga contenente un unica parola, la risposta a questo problema.

Assunzioni

  • 1 ≤ N ≤ 10000
  • Ei è uno tra i caratteri ’{[(<>)]}’.

Esempi di input/output

input.txt output.txt
4
([)]
malformata
5
<({})
malformata
12
()([]{(<>)})
corretta
20
{(<><>){{()[<>]<>}}}
corretta

Utilizzo una seconda stringa


Utilizzo una pila (stack)