Archives project euler - Pavol Pidanič

Hackerrank – Project Euler+ #067 – Maximum path sum II

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Riešenie je rovnaké ako Maximum Path Sum I.

Hackerrank – Project Euler+ #036 – Double-base palindromes

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Postup je zadaný v popise úlohy. Java Všetky riešenia sú dostupné aj na mojom GitHub profile. Java

public class DoubleBasePalindromes 
{
	public static void main(String[] args)
	{
		Scanner stdin = new Scanner(System.in);
		int n = stdin.nextInt();
		int base = stdin.nextInt();
		long sum = 0;
		for(int i = 1; i < n; i++)
		{
			String decimalString = Integer.toString(i, 10);
			String kBaseString = Integer.toString(i, base);
			if(isPalindrome(decimalString) && isPalindrome(kBaseString))
			{
				sum += i;
			}
		}
		System.out.println(sum);
		stdin.close();
	}
	
	
	private static boolean isPalindrome(String n)
	{
		for(int i = 0; i < n.length() / 2; i++)
		{
			char first = n.charAt(i);
			char last = n.charAt(n.length() - i - 1);
			if(first != last)
			{
				return false;
			}
		}
		return true;
	}
}

public class DoubleBasePalindromes

{

public static void main(String[] args)

{

Scanner stdin = new Scanner(System.in);

int n = stdin.nextInt();

int base = stdin.nextInt();

long sum = 0;

for(int i = 1; i < n; i++)

{

String decimalString = Integer.toString(i, 10);

String kBaseString = Integer.toString(i, base);

if(isPalindrome(decimalString) && isPalindrome(kBaseString))

{

sum += i;

}

System.out.println(sum);

stdin.close();

}

private static boolean isPalindrome(String n)

{

for(int i = 0; i < n.length() / 2; i++)

{

char first = n.charAt(i);

char last = n.charAt(n.length() - i - 1);

if(first != last)

{

return false;

}

return true;

}

Hackerrank – Project Euler+ #022 – Name scores

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Postup je zadaný v popise úlohy. Java Všetky riešenia sú dostupné aj na mojom GitHub profile. Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class NameScores
{
    private static Map<Character, Integer> alphabet;
    static
    {
        alphabet = new HashMap<>(26);
        alphabet.put('A', 1);
        alphabet.put('B', 2);
        alphabet.put('C', 3);
        alphabet.put('D', 4);
        alphabet.put('E', 5);
        alphabet.put('F', 6);
        alphabet.put('G', 7);
        alphabet.put('H', 8);
        alphabet.put('I', 9);
        alphabet.put('J', 10);
        alphabet.put('K', 11);
        alphabet.put('L', 12);
        alphabet.put('M', 13);
        alphabet.put('N', 14);
        alphabet.put('O', 15);
        alphabet.put('P', 16);
        alphabet.put('Q', 17);
        alphabet.put('R', 18);
        alphabet.put('S', 19);
        alphabet.put('T', 20);
        alphabet.put('U', 21);
        alphabet.put('V', 22);
        alphabet.put('W', 23);
        alphabet.put('X', 24);
        alphabet.put('Y', 25);
        alphabet.put('Z', 26);
    }

    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int namesCount = Integer.parseInt(scanner.nextLine());
        List<String> namesList = new ArrayList<>(namesCount);
        for (int i = 0; i < namesCount; i++)
        {
            String name = scanner.nextLine();
            namesList.add(name);
        }
        Collections.sort(namesList);
        Map<String, Integer> names = new HashMap<>();
        for (int i = 1; i <= namesList.size(); i++)
        {
            names.put(namesList.get(i - 1), i);
        }
        int queries = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < queries; i++)
        {
            String query = scanner.nextLine();
            int score = nameScore(names, query);
            System.out.println(score);
        }
        scanner.close();
    }

    private static int nameScore(Map<String, Integer> names, String name)
    {
        int result = 0;
        for (int i = 0; i < name.length(); i++)
        {
            result += alphabet.get(name.charAt(i));
        }
        result *= names.get(name);
        return result;
    }
}

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

import java.util.Scanner;

public class NameScores

{

private static Map<Character, Integer> alphabet;

static

{

alphabet = new HashMap<>(26);

alphabet.put('A', 1);

alphabet.put('B', 2);

alphabet.put('C', 3);

alphabet.put('D', 4);

alphabet.put('E', 5);

alphabet.put('F', 6);

alphabet.put('G', 7);

alphabet.put('H', 8);

alphabet.put('I', 9);

alphabet.put('J', 10);

alphabet.put('K', 11);

alphabet.put('L', 12);

alphabet.put('M', 13);

alphabet.put('N', 14);

alphabet.put('O', 15);

alphabet.put('P', 16);

alphabet.put('Q', 17);

alphabet.put('R', 18);

alphabet.put('S', 19);

alphabet.put('T', 20);

alphabet.put('U', 21);

alphabet.put('V', 22);

alphabet.put('W', 23);

alphabet.put('X', 24);

alphabet.put('Y', 25);

alphabet.put('Z', 26);

}

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int namesCount = Integer.parseInt(scanner.nextLine());

List<String> namesList = new ArrayList<>(namesCount);

for (int i = 0; i < namesCount; i++)

{

String name = scanner.nextLine();

namesList.add(name);

}

Collections.sort(namesList);

Map<String, Integer> names = new HashMap<>();

for (int i = 1; i <= namesList.size(); i++)

{

names.put(namesList.get(i - 1), i);

}

int queries = Integer.parseInt(scanner.nextLine());

for (int i = 0; i < queries; i++)

{

String query = scanner.nextLine();

int score = nameScore(names, query);

System.out.println(score);

}

scanner.close();

}

private static int nameScore(Map<String, Integer> names, String name)

{

int result = 0;

for (int i = 0; i < name.length(); i++)

{

result += alphabet.get(name.charAt(i));

}

result *= names.get(name);

return result;

}

Hackerrank – Project Euler+ #020 – Factorial digit sum

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Potrebné mať jazyk, ktorý podporuje operácie s veľkými číslami. Urobiť faktoriál a spočítať číslice. Ruby Všetky riešenia sú dostupné aj na mojom GitHub profile. Ruby

def factorial(n)
  fact = 1
  for i in 2..n do
    fact *= i
  end
  return fact
end


def sum_digits(number)
  chars = number.to_s.chars
  sum = 0
  chars.each { |char| sum += char.to_i }
  return sum
end
 
gets.chomp.to_i.times do
  n = gets.chomp.to_i
  puts sum_digits(factorial(n))
end

def factorial(n)

fact = 1

for i in 2..n do

fact *= i

end

return fact

end

def sum_digits(number)

chars = number.to_s.chars

sum = 0

chars.each { |char| sum += char.to_i }

return sum

end

gets.chomp.to_i.times do

n = gets.chomp.to_i

puts sum_digits(factorial(n))

end

Hackerrank – Project Euler+ #019 – Counting Sundays

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Implementácia je špecifická pre každý jazyk. Podľa toho, aké operácie s dátumom podporuje. Zo zadaného dátumu som si zistil, kedy je najbližšia nedeľa. Potom som zvyšoval dni o 7, aby som dostal nasledujúcu nedeľu. Tu si treba dať pozor na prípady, keď vyjde […]

Hackerrank – Project Euler+ #018 – Maximum path sum I

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Načítam si všetky čísla v zadnom trojuholníku a uložím ich do zoznamu po riadkoch. Začínam od konca a zoberiem posledné 2 riadky. Pre každé číslo na hornom riadku urobím súčet s číslom na spodnom riadku pre ľavú a pravú stranu. Zistím, ktoré číslo […]

Hackerrank – Project Euler+ #017 – Number to words

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Pre detailnejšie informácie pozri implementáciu. Urobil som základné prevody čísel do slov. Potom pre zadané číslo som robil, koľkokát sa nachádza jednotlivý násobok základných prevodov. Napr. 12 324. obsahuje 12 x 1000 teda „twelve thousand“. Zvyšná časť je očistená o 12 000 je […]

Hackerrank – Project Euler+ #016 – Power digit sum

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Na riešenie je potrebné mať podporu programovancieho jazyka pre veľké čísla. Nie je problém pri umocňovaní. Urobiť mocninu a spočítať číslice výsledku. Vytvoril som riešenie v týchto programovacích jazykoch: Java Všetky riešenia sú dostupné aj na mojom GitHub profile. Java

import java.math.BigInteger;
import java.util.Scanner;

public class PowerDigitSum
{
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int tests = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < tests; i++)
        {
            BigInteger base = new BigInteger("2");
            int exp = Integer.parseInt(scanner.nextLine().trim());
            base = base.pow(exp);
            long result = sumDigits(base);
            System.out.println(result);
        }
        scanner.close();
    }

    private static long sumDigits(BigInteger num)
    {
        long result = 0;
        char[] digits = num.toString().toCharArray();
        for (char digit : digits)
        {
            result += Character.digit(digit, 10);
        }
        return result;
    }
}

import java.math.BigInteger;

import java.util.Scanner;

public class PowerDigitSum

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int tests = Integer.parseInt(scanner.nextLine());

for (int i = 0; i < tests; i++)

{

BigInteger base = new BigInteger("2");

int exp = Integer.parseInt(scanner.nextLine().trim());

base = base.pow(exp);

long result = sumDigits(base);

System.out.println(result);

}

scanner.close();

}

private static long sumDigits(BigInteger num)

{

long result = 0;

char[] digits = num.toString().toCharArray();

for (char digit : digits)

{

result += Character.digit(digit, 10);

}

return result;

}

Hackerrank – Project Euler+ #015 – Lattice paths

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Riešenie je postavené na článku Vytvoril som riešenie v týchto programovacích jazykoch: Java Všetky riešenia sú dostupné aj na mojom GitHub profile. Java

import java.math.BigInteger;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class LatticePaths
{
    // http://www.robertdickau.com/lattices.html
    public static void main(String[] args)
    {
        Scanner scanner = new Scanner(System.in);
        int tests = Integer.parseInt(scanner.nextLine());
        for (int i = 0; i < tests; i++)
        {
            String[] numbers = scanner.nextLine().split("\\s+");
            int n = Integer.parseInt(numbers[0]);
            int m = Integer.parseInt(numbers[1]);
            Set<Integer> nFactorialMembers = new HashSet<>();
            for (int j = 1; j <= n; j++)
            {
                nFactorialMembers.add(j);
            }
            Set<Integer> mFactorialMembers = new HashSet<>();
            for (int j = 1; j <= m; j++)
            {
                mFactorialMembers.add(j);
            }
            Set<Integer> mnFactorialMembers = new HashSet<>();
            for (int j = 1; j <= m + n; j++)
            {
                mnFactorialMembers.add(j);
            }
            // (m+n) chose m === (m+n)!/m!n!
            // divided n!
            mnFactorialMembers.removeAll(nFactorialMembers);

            BigInteger result = BigInteger.ONE;
            for (Integer k : mnFactorialMembers)
            {
                result = result.multiply(new BigInteger(k.toString()));
            }
            for (Integer k : mFactorialMembers)
            {
                result = result.divide(new BigInteger(k.toString()));
            }
            System.out.println(result.mod(new BigInteger("1000000007")));
        }
        scanner.close();
    }
}

import java.math.BigInteger;

import java.util.HashSet;

import java.util.Scanner;

import java.util.Set;

public class LatticePaths

{

// http://www.robertdickau.com/lattices.html

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

int tests = Integer.parseInt(scanner.nextLine());

for (int i = 0; i < tests; i++)

{

String[] numbers = scanner.nextLine().split("\\s+");

int n = Integer.parseInt(numbers[0]);

int m = Integer.parseInt(numbers[1]);

Set<Integer> nFactorialMembers = new HashSet<>();

for (int j = 1; j <= n; j++)

{

nFactorialMembers.add(j);

}

Set<Integer> mFactorialMembers = new HashSet<>();

for (int j = 1; j <= m; j++)

{

mFactorialMembers.add(j);

}

Set<Integer> mnFactorialMembers = new HashSet<>();

for (int j = 1; j <= m + n; j++)

{

mnFactorialMembers.add(j);

}

// (m+n) chose m === (m+n)!/m!n!

// divided n!

mnFactorialMembers.removeAll(nFactorialMembers);

BigInteger result = BigInteger.ONE;

for (Integer k : mnFactorialMembers)

{

result = result.multiply(new BigInteger(k.toString()));

}

for (Integer k : mFactorialMembers)

{

result = result.divide(new BigInteger(k.toString()));

}

System.out.println(result.mod(new BigInteger("1000000007")));

}

scanner.close();

}

Hackerrank – Project Euler+ #014 – Longest Collatz sequence

Hackerrank – Popis problému Celý popis zadania sa nacháza – Hackerrank. Riešenie Máme zadané pravidlá, ako sa mení zadané číslo cez Collatzovú postupnosť: ak je n párne, urobím n/2 ak je n nepárne, urobím 3n + 1 Zadanie problému obsahuje mnoho čísel, teda počítať každý samostatne nám zaberie množstvo času. Moje riešenie spočíva v predvýpočítaní […]

Pavol Pidanič

Dokážem na 10 prstoch napočítať do 1023

Značka: project euler

Hackerrank – Project Euler+ #067 – Maximum path sum II

Hackerrank – Project Euler+ #036 – Double-base palindromes

Hackerrank – Project Euler+ #022 – Name scores

Hackerrank – Project Euler+ #020 – Factorial digit sum

Hackerrank – Project Euler+ #019 – Counting Sundays

Hackerrank – Project Euler+ #018 – Maximum path sum I

Hackerrank – Project Euler+ #017 – Number to words

Hackerrank – Project Euler+ #016 – Power digit sum

Hackerrank – Project Euler+ #015 – Lattice paths

Hackerrank – Project Euler+ #014 – Longest Collatz sequence