Algorithmen und Datenstrukturen

Mit Farben malen

Du möchtest einen Streifen mit 3 Farben – red, blue und orange – bemalen. Jeder Abschnitt des Streifens wird dabei mit genau einer Farbe gefärbt. Damit der Streifen auffälliger wirkt, sollen folgende Regeln eingehalten werden:
  1. Du darfst nie die gleiche Farbe unmittelbar nebeneinandersetzen.
  1. Die Farbe blue muss immer zwischen red und orange oder zwischen orange und red platziert werden.
Gesucht ist die Anzahl unterschiedlicher Streifen, die du für einen Streifen der Länge n erhalten kannst.

Eingabe

Die Eingabe besteht aus einer einzelnen ganzen Zahl n (1 ≤ n ≤ ).

Ausgabe

Das Programm soll die Anzahl möglicher Streifen ausgeben. Da das Ergebnis sehr groß werden kann, muss die Ausgabe modulo erfolgen.

Beispiele

Eingabe
Ausgabe
1
2
2
2
3
4

Erklärung

  1. (red), (orange)
  1. (red, orange), (orange, red)
  1. (orange, red, orange), (red, blue, orange), (orange, blue, red), (red, orange, red)
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue