You are hereProgramming Problems / 2008 Programming Problems

2008 Programming Problems

By gconway - Posted on 17 April 2012

TASK 1: Magic Cups

Marvo the magician can dazzle his audiences with his card tricks and disappearing rabbits, but he is most famous for his follow-the-ball routine. He starts with a series of N identical cups, lined up in a row in positions 1..N. The cups are placed upside down. He places a small ball under one of them. He then swaps pairs of cups and challenges his audience to follow where the ball has gone.

Due to his high hand speed, no one is able to guess correctly which cup the ball is under. However, using a high-speed camera you have managed to capture each of his cup-swaps. Given a list of these swaps, your program should determine the final position of the ball.


The first line of input contains a single integer, N, which is the number of cups. Note: The ball will start under cup N.

4 <= N <= 100

Each further line of input contains a pairs of integers, i and j

1 <= i,j <= N

Indicating that cups in positions i and j are swapped.

If the ball was at position i, then it is now at position j.

If the ball was at position j, then it is now at position i.

The input is terminated by i = -1

Note: there can be up to 1,000,000 ball swaps


A single integer, C (the position of the ball), followed immediately by a newline character. i.e. The ball is under the cup in position C.

Example 1 input


1 2

3 4

4 1

2 3

-1 -1

Example 1 output


Example 1 explanation: the ball start in position 4 (since N=4). Swap 2 moves the ball to position 3 and swap 4 moves the ball to position 2.

Example 2 input


5 2

2 1

1 2

2 1

3 4

4 1

-1 -1

Example 2 output


Example 2 explanation: the ball start in position 5 (since N=5). It goes to position 2, then to position 1, then back to 2, then back to 1. Finally it finishes in position 4.


TASK 2: Number mix

By mixing round the digits of a number, you can make new numbers.

Write a computer program to determine how many unique numbers can be made by reordering the digits of a given positive integer.


A single positive integer, N, followed by a newline.

1 <= N <= 2,000,000,000


A single integer, C, followed by a newline.

C is the number of unique ways to reorder the digits of N.


Here are some sample digit reorderings (explanation of examples below):

323 -> 233, 323, 332

9988 -> 8899, 8989, 8998, 9889, 9898, 9988

4444 -> 4444

1000 -> 0001, 0010, 0100, 1000


example input


example output



example input


example output



example input


example output



example input


example output



Task 3: Object Detection

CCTV cameras are now very common in cities and busy areas. However, it is usually too expensive to pay someone to watch the video all day and usually they simply record the video for later viewing if there is a crime.

Therefore, it would be useful if computers could be used to automatically detect things happening in the video. One simple technique is known as "background subtraction". The computer keeps one "background image" (a picture of the scene with nothing moving). Then when it gets a new image from the CCTV camera, it compares each pixel in the image with the corresponding pixel in the background image. If the colour is very similar, the pixel is marked as "background", otherwise it is marked as foreground. This is known as a foreground image. Larger regions of foreground pixels indicate something is happening (such as a person coming into the camera view, or an object left behind).

The importance of a rectangular region (within the foreground image) can be measured by:

I = f x f / A

Where 'f' is the number of foreground pixels in the region and A is the area of the region.

Your task is to write a program to find the rectangular region with the highest importance value, within a given foreground image.



W, H: the width and height of the foreground image

The next H lines contain W characters per line (0=background, 1=foreground)

4 <= W,H <= 50



X, Y, A, B

X = x-coordinate of top left corner of the rectangle

Y = y-coordinate of top left corner of the rectangle

A = width of the rectangle

B = height of the rectangle


You should output the rectangle with the highest importance score. If there are multiple rectangles with the same highest score, output the one with the smallest Y value. If there are multiple rectangles with the highest score and same Y value, output the one with the smallest X value. If there are still multiple solutions, output the one with smallest width.


Example input

8 9











Example output

2 8 4 1


The rectangle at position (2,8) with width 4, height 1 has an importance of 4

f = 4

A = 4

I = 16/4 = 4


Task 4: Non-fixed permutations

Given a set of 5 items, one possible reordering of the items can be given by:

5 3 2 4 1

This means that item 1 goes to position 5, item 2 goes to position 3, ..., item 5 goes to position 1. For some reorderings, there are some items that do not move. In the case above, item 4 remains in the same position.

Write a program to count how many unique reorderings of N items can be found, where no item stays in the same position.

Since this number can be very large, print out your answer modulus 1,073,676,287 (modulus means "remainder after dividing by"). Modulus can be computed using the "%" operator. For example,  "x = y % 100". If y = 231, then x = 31.



A single integer, N, followed immediately by a newline character.

1 <= N <= 1200


A single integer, R, followed immediately by a newline character.

R= the number of possible reorderings mod 1,073,676,287.


Example input:


Example output:



Example input:


Example output:




N = 2

R = 1 ....(2,1)

N = 4

R = 9 ....(2,1,4,3), (2,3,4,1), (2,4,1,3), (3,1,4,2), (3,4,1,2), (3,4,2,1), (4,1,2,3), (4,3,1,2), (4,3,2,1)