You are hereProgramming Problems / 2012 Programming Problems

# 2012 Programming Problems

#
Table of contents

## Print Diamond

Discussion Forum: http://aispc.computing.dcu.ie/forums/1st-round-problem1-print-diamonds

Write a program called Diamond which will ask the user to enter a positive odd integer n that is between 3 and 19.

## Palindrome

Discussion Forum: http://aispc.computing.dcu.ie/forums/1st-round-problem2-palindrome

A palindrome is a word, phrase, number, or other sequence of units that can be read the same way

backwards as it can be forwards. Write a program called Palindrome that will be able to detect if

the word entered is a palindrome or not.

The program should work when there is an even and odd number of characters, for example

a palindromes with an even number of character would be noon and palindrome with an odd

number of character would be racecar.

The program can be written in c, c++, java, perl, python, ruby or shell. If the program was written

in java it would be compiled and run as described below;

>javac Palindrome.java

>java Palindrome

Please enter a word: noon

The word noon is a palindrome

>java Palindrome

Please enter a word: moon

The word moon is not a palindrome

>java Palindrome

Please enter a word: racecar

The word racecar is a palindrome

>java Palindrome

Please enter a word: racecars

The word racecars is not a palindrome

## Prime Numbers

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem1-prime-numbers

A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.

A natural number greater than 1 that is not a prime number is called a composite number. For example, 5 is prime, as only 1 and 5 divide into it, whereas 6 is composite, since it has the divisors 2 and 3 in addition to 1 and 6.

Write a program called p1 that will read in two positive integers where the first interger will be between 10 and 50 and the second integer will between 50 and 100. The program should print the sum of all the prime numbers between the two numbers.

If the first number is not between 10 and 50 it should just display the message "The first number is not between 10 and 50".

A similar check should be done to make sure that the second number is between 50 and 100 and print the message "The second number is not between 50 and 100" if it was less than 50 or greater than 100.

The program can be written in c , c++ , java or python and should be named p1.c, p1.cpp , p1.java or p1.py respectively.

If the input file was that shown below, the correct output will be the sum of all the prime numbers between 15 and 62 which are

17 19 23 29 31 37 41 43 47 53 59 61.

p1_input.txt

------------

15 62

If the the program was written in java it would be compiled and run as described below;

>javac p1.java

>java p1 < p1_input.txt

460

or

>java p1 < p1_input.txt > p1_output.txt

when you open the p1_output.txt file it should contain the number below the dashed lines;

p1_output.txt

-------------

460

## DNA Sequence

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem2-dna-sequence

Write a program called p2 that will read in a dna sequence for example GTTCAG .

Then the program will search for this dna sequence in a String in the p2 program called dnaDatabase.

It will print out the characters that occur directly before and after this sequence whenever it occurs

in the dnaDatabase String.

The program can be written in c , c++ , java or python and should be named p2.c, p2.cpp , p2.java

or p2.py respectively.

String dnaDatabase = "CCTGTATTAGGTTCAGAATTCGTTCAGCAGCAGATTCGATTAGCTTTACAACAATTCAATA"+

"AAATAGCTTCGCGCTAAATTTTTAACTTTTCTCTGTCGTCGCACAATCGACTTTCTCTGTT"+

"TTCTTGTTCAGGGGTTTACCGGAATTGTTTCTGCTGCGATGAGGTATTGCTCGTCAGCCTG"+

"AGGCTGAAAATAAAATCCGTGGTCACACCCAATAAGTTAGAGAGAGTACTTTGACTTGGAG"+

"CTGGAGGAATTTGACATAGTCGAGTTCAGTTCTTCTCCAAGACGCATCCACGTGAACCGTT"+

"GTAACTATGTTCTGTGCCCACACCAAAAAAACTTTCCACGTGAACCGAAAACGAAAGTCTT"+

"TGGTTTTAATCAATAAGTGCTCTCTTCTCGGAGAGAGAAGGTGGGCTGCTTGTCTGCCGAT"+

"GTACTTTATTAAATCCAATAACCACACCAAAAAAACTTTCCACGTGTGAACTATACTCCAA"+

"AAACGAAGTATTGGTTTATCATAATCTGAAAAGTGCAAAGAACGATGATGATGATGATAGA"+

"GGAACCTGAGCAGCCATGTCTGAACCTATAGCGTATTGGTCGTCGTGCGACTAAATTAGGT"+

"AAAAAAGTAGTTCTAAGAGATTTTGATGATTCAATGCAAAGTTCTATTAATCGTTCAATTG";

note: the String variable dnaDatabase can also be a character array.

p2_input.txt

------------

GTTCAG

If the input file was that shown above and the program was written in java it would be compiled

and run as described below;

>javac p2.java

>java p2 < p2_input.txt

G A

C C

T G

A T

or

>java p2 < p2_input.txt > p2_output.txt

when you open the p2_output.txt file it should contain the text below the dashed lines;

p2_output.txt

-------------

G A

C C

T G

A T

------------------------------------------------------------------------------------------

To check this select Edit -> Find, Find What GTTCAG

CCTGTATTAG GTTCAG AATTC GTTCAG CAGCAGATTCGATTAGCTTTACAACAATTCAATA

AAATAGCTTCGCGCTAAATTTTTAACTTTTCTCTGTCGTCGCACAATCGACTTTCTCTGTT

TTCTT GTTCAG GGGTTTACCGGAATTGTTTCTGCTGCGATGAGGTATTGCTCGTCAGCCTG

AGGCTGAAAATAAAATCCGTGGTCACACCCAATAAGTTAGAGAGAGTACTTTGACTTGGAG

CTGGAGGAATTTGACATAGTCGA GTTCAG TTCTTCTCCAAGACGCATCCACGTGAACCGTT

you can see below the dna sequence with letters that occur before and after it.

G GTTCAG A

C GTTCAG C

T GTTCAG G

A GTTCAG T

-----------------------------------------------------------------------------------------

## Zero Duplicates

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem3-zero-duplicates

Write a program called p3 that will read in a list of numbers and will then print out the same list

except numbers that have already been printed will be printed as a zero instead.

The program can be written in c , c++ , java or python and should be named p3.c, p3.cpp , p3.java or p3.py respectively.

p3_input.txt

------------

1 2 2 3 3 4 5 5 3 2 6

If the input file was that shown above and the program was written in java it would be compiled and run as described below;

>javac p3.java

>java p3 < p3_input.txt

1 2 0 3 0 4 5 0 0 0 6

or

>java p3 < p3_input.txt > p3_output.txt

when you open the p3_output.txt file it should contain the text below the dashed lines;

p3_output.txt

-------------

1 2 0 3 0 4 5 0 0 0 6

## Averages

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem4-averages

The mean, median, and mode are three kinds of "averages". There are many "averages" in statistics,

but these are the three most common.

The mean is what is usually called the average, where you add up all the numbers and then divide by the

number of numbers.

The median is the middle value in the list of numbers. To find the median, you will first have to

rewrite the list in numerical order (ie ascending order). If there is an odd number of numbers the

median will be the middle value but if there is an even number of numbers then the median will be

the mean of the middle two values, so you sum the two middle values and divided by 2.

The mode is the number that is repeated the most often.But if there is no one number that is repeated

more than any other numbers then the mode can be a list of numbers that are repeated the most often

provided that they occur more than once in the list.If there is no mode for the list then print

the word none.

The range is just the difference between the largest and smallest values.

Write a program called p4 that will read in a list of numbers with a minus 1 to indicate the end of the

input. It will then print out values for the mean, median, mode and range of the list of numbers.

Your program should work with an even and odd number of numbers in the list.

Example 1:

----------

To find the mean, median, mode, and range for the following list of values;

13, 18, 13, 14, 13, 16, 14, 21, 13

mean = (13 + 18 + 13 + 14 + 13 + 16 + 14 + 21 + 13) / 9 = 135 / 9 = 15

median = 13, 13, 13, 13, 14, 14, 16, 18, 21

= 13, 13, 13, 13, 14, 14, 16, 18, 21

= 14

mode = 13 (because 13 occurs 4 times)

range = largest value in the list is 21, and the smallest is 13, so the range is 21 - 13

= 8

Example 2:

----------

To find the mean, median, mode, and range for the following list of values:

8, 9, 10, 10, 10, 11, 11, 11, 12, 13

mean = ( 8 + 9 + 10 + 10 + 10 + 11 + 11 + 11 + 12 + 13 ) / 10 = 105 / 10 = 10.5

median = 8, 9, 10, 10, 10, 11, 11, 11, 12, 13

= 8, 9, 10, 10, 10, 11, 11, 11, 12, 13

= (10 + 11) / 2 = ( 21 ) / 2

= 10.5

mode = 10 11 (these two values are repeated three times)

range = largest value in the list is 13, and the smallest is 8, so the range is 13 - 8

= 5

The program can be written in c , c++ , java or python and should be named p4.c, p4.cpp , p4.java or p4.py respectively.

If the program was written in java it would be compiled and run as described below;

Example 1:

==========

The list of number in the file p4_input_ex1.txt below will have the following averages;

The mean = 15

The median = 14

The mode = 13

The range = 8

p4_input_ex1.txt

----------------

13 18 13 14 13 16 14 21 13 -1

>javac p4.java

>java p4 < p4_input_ex1.txt

15

14

13

8

or

>java p4 < p4_input_ex1.txt > p4_output_ex1.txt

when you open the p4_output_ex1.txt file it should contain the text below the dashed lines;

p4_output_ex1.txt

-----------------

15

14

13

8

Example 2:

==========

The list of number in the file p4_input_ex2.txt below will have the following averages;

The mean = 10.5

The median = 10.5

The mode = 10 11

The range = 5

p4_input_ex2.txt

----------------

8 9 10 10 10 11 11 11 12 13 -1

>javac p4.java

>java p4 < p4_input_ex2.txt

10.5

10.5

10 11

5

>java p4 < p4_input_ex2.txt > p4_output_ex2.txt

when you open the p4_output_ex2.txt file it should contain the text below the dashed lines;

p4_output_ex2.txt

-----------------

10.5

10.5

10 11

5

## Cube Chaos

Discussion Forum: http://aispc.computing.dcu.ie/forums/problem5-cube-chaos

Little Matty liked playing with his blocks very much. He always constructed his `buildings' in the same way: he made stacks of one or more blocks, and he put those stacks on a square table that was exactly K blocks wide (K = 8 for his largest table, so it could contain up to 8 x 8 block stacks). He didn't put the stacks randomly on the table. No, he always made a nice `square' pattern. In most buildings, there was no pattern visible in the heights of the stacks. However, since Little Matty himself was only eight blocks tall, a single stack of blocks never consisted of more than eight blocks.

This is an example of one of his buildings. It was built on a table that could contain 4 x 4 block stacks.

He liked drawing too. To record his block buildings for future generations, he would draw them on paper. Since drawing a three-dimensional block building just was too hard for him, he made two drawings of a building: one straight from the front (you could only see the front of the blocks), and one from the right (you could only see the right side of the blocks). The drawings were in fact two-dimensional projections of the block building, showing only its outline on the front or on the right side.

These are the drawings he made of the building shown above.

Front Right side

He thought that such a pair of drawings would give enough information to be able to re-build the block building later (but he never tried it).

Years later, looking again at the drawings, he realized that this was not the case: from most pairs of drawings, he was able to construct more than one building that had the same outlines (front and right side) as the original one. He found out that from every (front, side)-pair of drawings that he had made, he could construct a `minimal' building, one that has the same outlines as the original building and contains a minimal number of blocks N (so it was not possible to construct a building with the same outlines with less than N blocks). Furthermore, he could add more blocks to this minimal building, so that the outlines remained the same, up to the point that he had added M () blocks and he had a `maximal' building, one that still had the same outlines as his minimal one, and adding one extra block would result in a building with a different outline (so there are no buildings with the same outlines that contain more than N + M blocks).

As an example, these are minimal and maximal buildings for the drawings shown above. In this case, N = 7 and M = 10.

Minimal Building Maximal Building

Matty started determining the N and M for every pair of drawings he had made, but soon he found this task to be tedious. Now he asks you to write a program that does the job for him!

**Input Specification**

The input contains on the first line the number of test cases. Each test case starts with a line containing only the size of the table K. The next pair of lines each contain the description of one drawing. Each description consists of K non-negative integers separated by spaces. Each number indicates the height of the corresponding projection of a stack of blocks in the drawing. The description of the front drawing always precedes the description of the right side drawing. From each pair of drawings at least one block building can be constructed.

**Output specification**

For each test case output the following line:

Matty needs at least N blocks, and can add at most M extra blocks.

**Sample Input**

2

4

2 0 3 1

1 1 2 3

1

1

1

**Sample Output**

Matty needs at least 7 blocks, and can add at most 10 extra blocks.

Matty needs at least 1 blocks, and can add at most 0 extra blocks.