DWITE '09 R2 #3 - Binary Test String

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
DWITE Online Computer Programming Contest, November 2009, Problem 3

Besides high school programming contests, another application for automated execution of code is in test suites, that validate the correctness of software (which, in some ways, is what DWITE judge does anyway). Given enough tests and edge cases in sample input, we could increase the confidence that the software is correct. Absolute certainty will require mathematical proofs, or generating every possible sample input and testing against that (which is often not possible).

For this problem, we'll be generating binary strings -- words of length 4, consisting of only 1s and 0s, with certain additional restrictions specified in the input file.

The input file will contain 5 lines, a binary string of length 1 to 4 -- a pattern that should not appear in binary strings in the generated set.

That is: if the input is "1", then the only valid output string is "0000" (any other binary string of size 4 will contain "1"). Substring "11" disallows: 1100, 0110, 0011; but it also appears in 1110, 0111, and 1111.

The output will contain 5 sets of generated binary strings, sorted in ascending order, that is, from 0000 to 1111.

Sample Input


Sample Output


Attribution-NonCommercial-ShareAlike 3.0 Unported (CC BY-NC-SA 3.0) Problem Resource: DWITE


  • 0
    timurichk  commented on May 29, 2018, 2:59 p.m.

    Yo your sample output is missing a single binary string.

  • 0
    TypicalToxic  commented on Oct. 22, 2017, 2:13 a.m.

    invalid case