DWITE '09 R5 #5 - Weak Passwords

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, March 2010, Problem 5

In secure authentication, one does not necessary need to provide their password, they just need to prove that they know their own password. The subtle difference allows one to store just an encoded hash of a password. That way the actual (plaintext) password is never stored, making the system more secure, as the real password is never written down and can't be stolen, should a system be compromised...

The input will contain 5 lines, integers 0 \leq N \leq 1\,000\,000 the hash stored in place of the password.

The output will contain 5 lines, each a 4 character long password that generate the corresponding input hashes.

Assume that all passwords are four characters long and are made up of capital letters only.

A hash is calculated as follows. Given a password P, made up of four letters a_1, a_2, a_3, a_4; each letter is turned into its ASCII value, where A = 65 and Z = 90n_1, n_2, n_3, n_4. Let k = n_1 \times 10^6 + n_2\times10^4 + n_3\times10^2 + n_4. Let m = n_1\times11 + n_2\times101 + n_3\times1009 + n_4\times10\,007. Then hash(P) = k \bmod m.

For example: given a password P = \texttt{TONY}, there are four letters a_1 = \texttt T, a_2 = \texttt O, a_3 = \texttt N, a_4 = \texttt Y; and mapped to ASCII n_1 = 84, n_2 = 79, n_3 = 78, n_4 = 89. Then k = 84\,797\,889. And m = 84\times 11 + 79\times 101 + 78\times 1009 + 89\times 10\,007 = 978\,228. So hash(\texttt{TONY}) = 84\,797\,889 \mathbin{\%} 978\,228 = 670\,281.

Note: Be aware of time constraints. Also, there are cases where multiple passwords result in the same hash. Those hashes are not a part of the test cases.

Sample Input


Sample Output


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


  • 0
    geese  commented on Nov. 14, 2018, 2:01 p.m.

    hash(TONY) should equal 84 797 889 % 978228 = 670281

    • 1
      d  commented on Dec. 28, 2018, 12:42 a.m.

      Fixed. Latex code should have been 84\,797\,889 \mathbin{\%} 978\,228 instead of 84\,797\,889 % 978228.