ACM RTK - 2. skupina

Binarni sef

Binarni sef ima na številčnici dve tipki: 0 in 1. Če ima sef šifro 011, se bo odprl takrat, ko bodo zadnje tri pritisnjene tipke zaporedno 0, 1 in 1. Če ne poznamo šifre, lahko poskusimo sef odpreti tako, da vtipkamo vseh 8 trimestnih kombinacij. Vendar gre tudi hitreje — če vtipkamo na primer zaporedje 0001011100, se bodo vrata zagotovo odprla, saj se v tem zaporedju pojavljajo kot podnizi kombinacije 000, 001, 010, 101, 011, 111, 110, 100 — kar je ravno vseh osem kombinacij. Napiši podprogram Sef(s, n), ki bo za dano zaporedje s in znano dolžino šifre (n znakov) preveril, ali zaporedje s zagotovo odpre sef. Predpostaviš lahko, da je n (dolžina šifre) največ 12, zaporedje s pa je dolgo največ 10.000 znakov.

Tvoj podprogram naj bo takšne oblike:

function Sef(s: string; n: integer): boolean;  { v pascalu }
bool Sef(char *s, int n);                     /* v C/C++ */
bool Sef(string s, int n);                    // v C++
public static boolean Sef(String s, int n);   // v javi
public static bool Sef(string s, int n);      // v C#
def Sef(s, n): ...                            # v pythonu; naj vrne True/False