Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Horné ohraničenie problému je veľmi veľké. Musíme si to zjednodušiť. Pre zadané čísla a a b nájdeme všetky square numbers rovnicou:
![\[\lfloor a \rfloor - \lceil b \rceil + 1\]](https://pidanic.com/wp-content/ql-cache/quicklatex.com-5066abff22b68a1f8bcfde16f660dd6a_l3.png "Rendered by QuickLaTeX.com")
.
Existuje špeciálny prípad keď sa a a b rovnajú. Potom si stačí vybrať a a b a skontrolovať, či je square number.
Vytvoril som riešenie v týchto programovacích jazykoch:
Všetky riešenia sú dostupné aj na mojom GitHub profile.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
import java.util.*; public class SherlockAndSquares { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int tests = Integer.parseInt(stdin.nextLine()); for(int i = 0; i < tests; i++) { String[] parts = stdin.nextLine().split(" "); int lower = Integer.parseInt(parts[0]); int upper = Integer.parseInt(parts[1]); int squareNumbers; if(lower == upper) { if (Math.sqrt(lower) == Math.ceil(Math.sqrt(lower))) { squareNumbers = 1; } else { squareNumbers = 0; } } else { squareNumbers = (int)(Math.floor(Math.sqrt(upper)) - (Math.ceil(Math.sqrt(lower))) + 1); } System.out.println(squareNumbers); } stdin.close(); } } |
JavaScript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
'use strict'; const processData = input => { const lines = input.split('\n').slice(1); for(let i = 0; i < lines.length; i++) { const parts = lines[i].split(' '); const lower = parts[0]; const upper = parts[1]; let squareNumbers = 0; if(lower === upper) { if (Math.sqrt(lower) === Math.ceil(Math.sqrt(lower))) { squareNumbers = 1; } else { squareNumbers = 0; } } else { squareNumbers = parseInt(Math.floor(Math.sqrt(upper)) - (Math.ceil(Math.sqrt(lower))) + 1) } console.log(squareNumbers); } }; process.stdin.resume(); process.stdin.setEncoding("ascii"); let _input = ""; process.stdin.on("data", input => _input += input); process.stdin.on("end", () => processData(_input)); |
Scala
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
object SherlockAndSquares extends App { val tests = Source.stdin.getLines().drop(1) val numberIntervals = tests.map(line => line.splitAt(line.indexOf(" "))) .map(tuple => (tuple._1.trim.toInt, tuple._2.trim.toInt)) val squareNumbers = numberIntervals.map(getSquareNumbers) println(squareNumbers.mkString("\n")) def getSquareNumbers(interval: (Int, Int)): Int = { val lower = interval._1 val upper = interval._2 if(lower == upper) if(Math.sqrt(lower) == Math.ceil(Math.sqrt(lower))) 1 else 0 else (Math.floor(Math.sqrt(upper)) - (Math.ceil(Math.sqrt(lower))) + 1).toInt } } |
Ruby
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
tests = gets.to_i tests.times do (lower, upper) = gets.split(" ").map {|i| i.to_i} square_numbers = 0 if(lower == upper) if (Math.sqrt(lower) == (Math.sqrt(lower)).ceil) puts 1 else puts 0 end else puts ((Math.sqrt(upper)).floor - (Math.sqrt(lower)).ceil + 1).to_i end end |