# CMPT 360 Assignment 1

\$30.00

## Description

A. Palindrome (Time limit: 10 seconds)
Problem Description
A palindromic number is an integer that is the same when the digits are reversed. For
example, 121 and 625526 are palindromic, but 625 is not a palindromic number.
Input:
The input is in ‘palindrome.txt’. The first line of the input contains the line count m (1 ≤
m ≤ 1, 000), which is the number of lines that follows the first line. Each of the following
lines contains an integer of n digits (1 ≤ n ≤ 5, 000).
Sample input:
3.
12333.
92837465.
1000000000000000123.
Output:
The output consists of m lines. Each line transforms the corresponding input line into
a palindrome by concatenating the input and its digits in reversed order. To minimize
the output length, you must not repeat the trailing digit (or, digits if there are multiple
occurrences of the same digit) of the input integer.
Sample output:
1
Assignment 1 — Posted September 9, 2019— Submission Deadline: See Moodle
1233321.
928374656473829.
1000000000000000123210000000000000001.
1. The expected complexity is O(n).
Write a code ‘A.YourNSID.java’ that reads ‘palindrome.txt’ and writes the output in a
file called ‘A.YourNSID.txt’. Only submit the file ‘A.YourNSID.java’ in Moodle.
3. The score will be 0 if your program does not terminate within 10 seconds. If your
output is correct for k out of m inputs, then you will receive a score of ⌈
k
m
· 10⌉.
Every palindrome of 4 digits is divisible by 11 (good to know, but not related to this
assignment). Can you prove it in a midterm question?
B. Beer Time (Time limit: 3 seconds)
Problem Description
A group of n students of CMPT360 is standing around a circle, but there are (n − 1) bottles
of water and only 1 bottle of beer. They came up with an algorithm to solve their problem
(yes, this is how those students are). They will start counting clockwise, starting at position
1, removing every second remaining person to get out of the circle and have a bottle of
water. As the process goes on, the circle becomes smaller and smaller, until only one lucky
student remains, who can have that only bottle of beer. A smart student quickly computes
the position J(n) that would get the bottle of beer and stand in that position.
For example, if there are 10 people numbered 1 to 10 in clockwise order around the circle,
then the order of getting a water bottle is 2, 4 , 6, 8, 10, 3, 7, 1, 9, as follows (* indicates the
position where the counting starts):
*1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (initial state)
1, *3, 4, 5, 6, 7, 8, 9, 10
1, 3, *5, 6, 7, 8, 9, 10
1, 3, 5, *7, 8, 9, 10
1, 3, 5, 7, *9, 10
*1, 3, 5, 7, 9
1, *5, 7, 9
1, 5, *9
*5, 9
2
Assignment 1 — Posted September 9, 2019— Submission Deadline: See Moodle
*5 (survivor)
Here the person at the 5th position survives. Therefore, J(10) = 5. A quick way to find the
J(n) is to use the following:
J(1) = 1
J(2m + x) = 2x + 1,