Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1441
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1441
Hailstone Sequences
UruguayTimelimit: 1
Consider the sequence formed by starting from a positive integer h0 and iterating with n = 1, 2, . . . the following definition until hn = 1:
hn = { ½ × hn-1 if hn-1 is even;
hn = { 3 × hn-1 + 1 if hn-1 is odd.
For instance, if we start with h0 = 5 the following sequence is generated: 5, 16, 8, 4, 2, 1. If we start with h0 = 11, the sequence generated is 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
As you can see from these examples, the numbers go up and down, but eventually comes down to end in 1 (at least for all numbers that have ever been tried). These sequences are called Hailstone sequences because they are similar to the formation of hailstones, which get carried upward by the winds over and over again before they finally descend to the ground.
In this problem, given a positive integer, your task is to compute the highest number in the Hailstone sequence which starts with the given number.
Input
Each test case is described using a single line. The line contains an integer H representing the starting value to build the sequence (1 ≤ H ≤ 500).
The last test case is followed by a line containing one zero.
Output
For each test case output a line with an integer representing the highest number in the Hailstone sequence that starts with the given input value.
| Sample Input | Sample Output |
|
5 |
16 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
int hr(int n) {
if (n % 2 == 0)
return n / 2;
else
return 3 * n + 1;
}
int main(void) {
int n, m;
while (scanf("%d", &n) == 1 && n != 0) {
m = n;
while (n != 1) {
if (m < n) m = n;
n = hr(n);
}
printf("%d\n", m);
}
return 0;
}
Input
11
27
0
Output
52
9232
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
using namespace std;
int hr(int n) {
if (n % 2 == 0)
return n / 2;
else
return 3 * n + 1;
}
int main(void) {
int n, m;
while (cin >> n && n != 0) {
m = n;
while (n != 1) {
if (m < n) m = n;
n = hr(n);
}
cout << m << endl;
}
return 0;
}
Input
11
27
0
Output
52
9232
#3 Code Example with Javascript Programming
Code -
Javascript Programming
//// READING FILE | STREAMS ////
const { createReadStream } = require("node:fs")
const { createInterface } = require("node:readline")
const PATH = "/dev/stdin"
const ENCODING = "utf8"
/**
* @param {string} path
* @param {BufferEncoding} encoding
*/
function createReadLineInterface(path, encoding) {
return createInterface({
input: createReadStream(path, encoding),
crlfDelay: Infinity,
terminal: false
})
}
const RLI = createReadLineInterface(PATH, ENCODING)
/** @param {import("readline").Interface} readLineInterface */
const processLineByLine = function (readLineInterface) {
let EOF = false
const nextLineGenerator = (async function* () {
for await (const line of readLineInterface) yield line
EOF = true
})()
return {
hasNextLine: () => !EOF,
nextLine: async (fn) => {
const { value } = (await nextLineGenerator.next())
return (typeof fn === "function") ? fn(value) : value
}
}
}
//// UTILS ////
const isOdd = (num = 0) => Math.abs(Number(num)) % 2 === 1
const isEven = (num = 1) => Math.abs(Number(num)) % 2 === 0
//// GRANIZO CLASS ////
class Granizo {
static #memo = {}
/**
* Returns the max value of the given sequence initialized for the given `h`
* @param {number} h The initial value of the granizo's sequence
*/
static max(h) {
// If the maximum value of the sequence already calculated, then return it
if (Reflect.has(Granizo.#memo, h)) return Reflect.get(Granizo.#memo, h)
const H = h
let maximum = 1
while (h != 1) {
// hn = { ½ x hn-1 se hn-1 é par;
// hn = { 3 x hn-1 + 1 se hn-1 é ímpar.
// The biggest value in sequence always will be an even number
if (h > maximum) maximum = h
if (isEven(h)) { h /= 2 }
else if (isOdd(h)) { h = 3 * h + 1 }
if (Reflect.has(Granizo.#memo, h)) {
maximum = Math.max(maximum, Reflect.get(Granizo.#memo, h))
break
}
}
return (Reflect.set(Granizo.#memo, H, maximum), Reflect.get(Granizo.#memo, H))
}
// static get memo() { return Granizo.#memo }
}
//// MAIN ////
async function main() {
const output = []
const readLineInstance = processLineByLine(RLI)
const readLine = readLineInstance.nextLine.bind(undefined, (n = "") => Number.parseInt(n, 10))
while (readLineInstance.hasNextLine()) {
const H = await readLine()
if (H === 0) break
else if (1 <= H && H <= 500) output.push(Granizo.max(H))
else continue
}
console.log(output.join("\n"))
}
main()
Input
11
27
0
Output
52
9232
#4 Code Example with Python Programming
Code -
Python Programming
def hr(n):
if n % 2 == 0: return int(n // 2)
else: return 3 * n + 1
while True:
n = int(input())
if n == 0: break
m = n
while n != 1:
if m < n: m = n
n = hr(n)
print(m)
Input
11
27
0
Output
52
9232