UNSW High Schools Programming Competition 2014: Open Round

The Tasks:

Junior task: Ups ’n’ Downs (easy, 7 marks) Task 1. Murlin (easy, 7 marks) Task 2. Happy Numbers (easy to moderate, 9 marks) Task 3. Triffids (easy to moderate, 11 marks) Task 4. Shuffle (easy + moderate to hard, 14 marks) Task 5. Woodcutter (moderate, 19 marks)

Available Marks: 7

A run is a list of contiguous numbers that are either all increasing (ups) or all decreasing (downs). Up runs and down runs always alternate, and the last element of one run is the first of the next run.

Write a program that counts the number of runs in several lists of numbers. The first line of input contains the number of lists, followed by the lists, one per line.

Example

Input

3
4 1 8 12 17
2 5 9
-4 -5 -2 0 1 0

Output

 
2
1
3

Assumptions

Test Data

You should test your program on the following data:
5
23 89
5 4 3 -2 2 17 123
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1
123 -123
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9 10

Available Marks: 7

Murlin is a wizard who decodes URLs that have been encoded to disguise the true address of a malicious website. The encoding itself is legitimate, and the codes are interpreted as the equivalent normal characters in an address, but the user who clicks on one rarely knows what such a URL really refers to.

A URL-encoded string consists of ordinary characters and 3-character escape sequences. An escape sequence begins with a percent character (%) and is followed by two hexadecimal digits, using either upper or lower case. The two hex digits represent the character code. Murlin only has to deal with character codes in the printable ASCII character range, space (32 or hex 20) through to ~ (126, or hex 7E). Ordinary characters are preserved and each escape sequence is replaced by the character it represents.

Write a program to provide Murlin’s functionality. Input consists up to 10 encoded strings, one per line, with the first line containing the number of strings. Each string is up to 100 characters in length. You may assume the strings are properly constructed from printable characters.

Example

Input

3
Hello
http://%77%77%77%2E%6D%61%6C%77%61%72%65%52%75%73%2E%63%6F%6D/www.furrykittens.com
http://www.example.com.au/spaces%20%26%20funny%20%21%23%7c%20chars%20in%20name.pdf

Output

Hello
http://www.malwareRus.com/www.furrykittens.com
http://www.example.com.au/spaces & funny !#| chars in name.pdf

Hexadecimal

In case you haven’t interpreted hexadecimal (base-16) numbers before, here’s a quick summary:

Hex digit   Decimal

    0      0
    1      1
    2      2
    3      3

Hex digit   Decimal

    4      4
    5      5
    6      6
    7      7

Hex digit   Decimal

    8      8
    9      9
 A or a   10
 B or b   11

Hex digit   Decimal

 C or c   12
 D or d   13
 E or e   14
 F or f   15

The decimal value of a 2-digit number d1d2 in base b is equal to

b dec(d1) + dec(d2)

where dec returns the decimal value of a base-b digit.

Test Data

You should test your program on the following data:
8
progcomp%40cse
%3Ca%20href%3D%22www.don%27tgothere.info%22%3ETesting%3C%2Fa%3E
%77%77%77%2E%75%72%6D%79%62%2A%2A%2A%2A%2E%72%75%2F%63%6C%69%63%6B%68%65%72%65/kiddysafe.org
%66%74%70%3A%2F%2F%74%72%6F%6A%61%6E%73%34%75%2E%6F%72%67%2F%70%77%6E%65%64%21
100%5exy
ENCODED%20%25%37%34%25%37%37%25%36%39%25%36%33%25%36%35
!*%21%2a()%28%29;:%3b%3a@&%40%26=+%3d%2b$,/%24%2c?#%2f%3f%23
[]%5b%5d'%27<>%3c%3e{}%7b%7d"%22^~%5e%7e`.%60%2e

Available Marks: 9

Given any positive integer n > 1, if you square each decimal digit and add them up, you obtain a different number m. If you continue this process with m, the sequence will eventually reach one of two distinct states:

If the sequence reaches 1, then n is called a happy number, otherwise it’s an unhappy number. All unhappy numbers enter the same cycle at various points, let’s call that cycle the Circle of Despair.

For example, 49 is a happy number because it reaches 1 after 4 steps:

42 + 92 = 16 + 81 = 97;
92 + 72 = 81 + 49 = 130;
12 + 32 + 02 = 1 + 9 = 10;
12 + 02 = 1

Your Task

Write a program to test all integers from 1 to 999 for happiness. Use it to answer the questions in the box below. The program doesn’t have to display the answers, but its output should enable you to enter the answers without reference to any other data.

Available Marks: 11

The Trifid Cipher was invented in 1901 by Félix Delastelle. It shares with John Wyndham’s three-legged predatory plants in The Day of the Triffids the Latin root trifid, meaning "split into three parts".

To apply the cipher you need a table of codes. For each letter of the alphabet, plus space, there is a unique three-digit code using the symbols 1, 2 and 3. Say the code is assigned this way:

S  111
E  112
C  113
R  121
T  122
   123
A  131
B  132
D  133
F  211
G  212
H  213
I  221
J  222
K  223
L  231
M  232
N  233
O  311
P  312
Q  313
U  321
V  322
W  323
X  331
Y  332
Z  333

To encrypt a message, first write down the codes for each letter in the message, vertically:

T H E   H U N   A R E   A T T A C K I N G
1 2 1 1 2 3 2 1 1 1 1 1 1 1 1 1 1 2 2 2 2
2 1 1 2 1 2 3 2 3 2 1 2 3 2 2 3 1 2 2 3 1
2 3 2 3 3 1 3 3 1 1 2 3 1 2 2 1 3 3 1 3 2
Now read off the data in row order, three digits at a time, re-encoding them as letters using the same table:
121 => R
123 => (space)
211 => F
111 => S
...
Giving a final encoding of
R FSSEJFGWGVPLMXX TDB
This method was considered superior to simpler ones because each message character contributes to 3 encoded characters. Decoding is the reverse of the above algorithm.

Generating the Encoding Table

Given an agreed passphrase, write it down but remove the second and subsequent copy of each letter used. Append the rest of the alphabet in order, preceded by space if it wasn’t in the passphrase. Assign the codes in numeric order. The table above was generated by the passphrase "SECRET".

Your Task

Write a trifid decoder. Input consists of a line containing the number of encoded strings, then a line containing the passphrase, then one encoded string per line thereafter. There could be up to 10 strings, each up to 80 characters. Only legal characters occur.

Test Data

You should test your program on the following two data sets. The first one uses the same table as shown above, so you can get some marks if you can’t get the table generator to work and you have to use a fixed table.
4
SECRET
FESEGJCELMMYEJKK HPW
QHLAH OERSPIWFJCFLKMVOEK
EIR OA COORRA ISCSVPFLTVLFETFNXFZLIPFWMO GXXHCMOUUXVUE
RBOEWSYTQOTOFRDEEKWJOUINGTTRFWA NADGKXD TATUKUR
6
PACK MY BOX WITH FIVE DOZEN LIQUOR JUGS
ZKVNXPVNEAOBJMCIGELVXMHWXVURNVFFMWG Z
HOKHZIMAHNNSYP QUWCAZBFVNTRNIDFTKCRU IFURMRL EUMQFDHARFFDNXGWQQEUR
HNTPNNS WHM Q QUWP DYBM EDKUXHUOITU IFUUPZE HTHSFRDWTGDFHXGWQRWDDV
SSSSSSSSSPPPPPPPPPPPPPPPPPP
EX WFHTKSHYUEIKUEEOSW WTQFQH
X

Available Marks: 14

Shuffle is a simple number permutation game. Given a rectangular m x n grid, place each number from 1 to mn so that all specified row and column sums are correct. Some of the numbers are already placed.

Write a program to process a partly completed Shuffle game. The number of marks available depends on the amount of work your program does, starting with validation through to applying logical techniques to avoid simply trying all permutations.

The goals and associated rewards are as follows:

Data Format

Each file contains one game. The first line contains the number of rows and columns, in that order, separated by a space. The m lines of the grid follow, with a dot (.) to mark an empty cell, and the row total at the end of each row. The last line contains the column totals. Cell entries and totals are separated by one or more spaces, and there may be spaces at the beginning of a line to align cells.

Test Data - Completed Games

Test C1
3 3
 7  2  5 14 
 6  3  1 10 
 3  9  8 20 
16 14 14  
Test C2
3 4
 4  5  2  7 18 
 1 12  9  3 25 
11 10  6  8 35 
16 27 17 18 
Test C3
4 4
 4  9 14  6 33 
13  7  5  2 27 
 1 12 10 15 38 
 3 11  8 16 38 
21 38 37 39 

Test Data - Incomplete Games

Test P1
3 3
 .  .  2  7 
 .  6  . 18 
 5  .  7 20 
12 15 18 
Test P2
4 4
 8  .  . 10 31 
 .  1  .  . 25 
 6  .  7  . 38 
 .  3  9  . 42 
33 28 22 53 
Test P3
4 5
 7  .  . 10  . 44 
 .  .  6  .  . 50 
17  . 14  .  . 65 
 .  4  . 18  . 51 
55 18 49 54 34 

Available Marks: 19

You have a length of timber that needs to be cut into several pieces. The points where the cuts have to be made are marked on the timber, measured from one end. The only precision cutting company available at short notice charges, for each cut, a rate in dollars equal to the length of the piece in metres before cutting.

The order in which the cuts occur affects the total price. For example, a piece 10m long with cuts needed at 4m, 5m and 7m could be cut first at 5m, costing $10, leaving two 5m sections requiring one cut each, a total of $10 + $5 + $5 = $20.

However if the cuts are made at 4m, 7m and 5m the total cost is $10 + $6 + $3 = $19.

Your Task

Write a program that determines the optimal cutting cost for a piece of timber with up to 50 cuts, and, for maximum marks, the optimal cutting sequence. The cost is to be expressed to the nearest cent, as cuts need not be integral.

In general there are multiple optimal cutting sequences. Display the sequence that favours cutting at smaller positions earlier than larger numbered ones. This means that after every cut, the left-hand piece is then cut (if needed) before the right-hand piece.

Data Format

The input format for this problem contains two lines: the length of the timber on the first line, and the cutting positions, in numeric order, on the second line. Cuts lie strictly between 0 and the total length and are all different.

Input

10
4 5 7

Output

$19.00 4 7 5

Analysis and Design

There is no shortcut computational strategy that can generate the optimal cost in all cases, though heuristics may work sometimes. Instead you should try all possible cut sequences. Small-scale problems can be solved by a simple recursive design, but will take an inordinate amount of time for larger numbers of cuts as the number of small, repeated subproblems escalates exponentially.

Solving large problems of this kind requires a technique called dynamic programming, where the the first time each small subproblem is solved, the solution is stored in an array or hash, representing a solution cache. When the same subproblem needs to be solved again the cache is first inspected, thus avoiding possibly thousands of recalculations.

Test Data

You should test your program on the following four data sets separately. The # character introduces a comment before each data set.
# Solvable without dynamic programming.
20
4 5 7 8 10 13 15

# Cuts need not be integers, direct solution still possible.
56.325
3.9 11.7 15.2 17.2 19.3 23.8 28.6 31.0 37.9 48.3 48.9 52.4

# The first 25 of Euler’s “lucky numbers” (see Wolfram Mathworld). Direct methods are impractical.
384.88
1 3 7 9 13 15 21 25 31 33 37 43 49 51 63 67 69 73 75 79 87 93 99 105 111

# 50 pseudorandom values. Direct methods are impossible.
1000
6 13 17 55 75 90 105 126 127 177 203 233 244 248 256 296 306 363 411 418 430 462 466 470 475 481 486 494 509 533 555 597 605 608 625 629 659 668 761 775 814 815 823 833 842 845 850 898 906 946

Marking Scheme

8 for finding the minimum cost for the first two data sets.
7 for finding the minimum cost for the second two data sets.
1 for each correct cutting sequence.