Gira le carte nel numero minimo di passaggi

Question

Gira le carte nel numero minimo di passaggi

#1 da (2 voti)

0

Immagina di ricevere una serie di carte. Alcuni di questi sono rivolti verso il basso (0), mentre alcuni di essi sono rivolti verso l'alto (1). È possibile che una determinata K abbia la possibilità di girare tutte le carte a faccia in su girando tutte le carte K consecutive? Se è possibile qual è il numero minimo di passaggi?

Ad esempio:

N=6; K=3;
1 0 0 1 0 0

È possibile rendere tutte le carte rivolte verso l'alto, girando prima le carte 2-3-4 e poi girando le carte 4-5-6. E il numero minimo di passaggi è 2.

La mia idea era quella di scorrere la sequenza e quando trovo uno 0 allora lancio le prossime K card (se è possibile), incluso lo 0. Ma sembra che questa idea non funzioni sempre. Ad esempio:

N=56; K=5
0 0 1 0 0 1 1 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 0

è un contro-esempio. Da quando eseguo l'algoritmo sopra descritto, finisco con tutte le carte a faccia in su, tranne che per l'ultimo.

Questo è un problema di contest, quindi uno dei casi di test è:

1000 25
0 0 1 0 0 1 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1 0 1 1 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 0 1 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 0 1 0 0 0

La presunta risposta corretta è 441, mentre il mio algoritmo dice 443.

algorithms problem-solving

posta Stefan4024 08.04.2015 - 01:29

fonte

1 risposta

Leggi altre domande sui tag algorithms problem-solving

L'addendum H2 di EPL e MPL è compatibile con queste licenze? [chiuso] sessioni utente in un server web; velocità o persistenza?

score 2 · Answer 1

In primo luogo, esiste un'alta possibilità che la combinazione di parametri e carte iniziali possa essere irrisolvibile. Ad esempio

N=3; K=2
1 0 1

È irrisolvibile.

Il tuo algoritmo non trova il numero minimo di passaggi, perché la tua configurazione di esempio non può essere risolta affatto.

Ora la domanda è ogni volta che l'algoritmo fornito garantisce effettivamente che può sempre trovare una soluzione, se esiste. Non ho prove rigide, ma credo di sì.

Il motivo della mia convinzione sono le carte di bordo. Nel momento in cui le carte bordo diventano 1, non è possibile applicare la funzione "capovolgi" su di esse e l'area K-1 accanto a loro. Se lo facessi, dovresti applicarlo di nuovo, ripristinando completamente il precedente flip. Sono invarianti per la funzione di capovolgimento. Quindi, se riesci a capovolgere una carta bordo per essere 1, puoi ignorarla, rimuoverla dall'elenco delle carte e continuare con l'elenco ridotto. Se c'è 0 sul bordo, lo si gira insieme a K-1 altre carte, che danno 1 che puoi quindi ignorare. Lo stai facendo esattamente con il tuo algoritmo. Alla fine di questo algoritmo, si finisce con l'elenco delle carte la cui lunghezza è EndN <= K .

Detto questo, capire quando la configurazione è risolvibile è facile. La configurazione è risolvibile solo se EndN = K e se le carte rimanenti sono su o giù.