Проблем с решението на Catalan Numbers - JAVA


0

Здравейте,

От няколко часа е опитвам да стигна до решение в задачата Catalan Numbers.
Решението до което стигнах, без да ми дава грешка в judge - Test case #1:  TLE  [>0.100s,  40.70 MB]  (0/0) - e следното:

import java.util.Scanner;

public class CatalnNumber {
public static void main(String[] args) {
Scanner scaner = new Scanner(System.in);
byte n = scaner.nextByte();
int factorielN = 1, factoriel2N = 1, factorielNplus1 = 1;

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

for (int i = 1; i <= (2 * n); i++)
factoriel2N *= i;

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

System.out.println(factoriel2N / (factorielN * factorielNplus1));
}
}

При ръчна проверка в Intellij за input 0 и 5 ми дава верен отговор, след което нещата не се получават, както в дадените примери. В началото мислех, че проблема идва от int n = scanner... като го замених с byte n = ... но за съжаление промяна няма. Пробвах и други варианти, като с BigInteger но кода ми тотално се счупи...

Всъщност проверявайки и този тип решение даде същата грешка - Тest case #1:  TLE  [>0.100s,  40.70 MB]  (0/0) 

Някой да ме посъветва къде бъркам? 
Лошото е че дори кода да работи точно, отново няма да влезна в Time Limit-а на задачата. 




Отговори



0
using System; using System.Numerics; class NthCatalanNumbers { static void Main() { int n = int.Parse(Console.ReadLine()); if (1 <= n && n <= 100) { BigInteger numerator = 1; for (int i = 1; i <= (2 * n); i++) { numerator *= i; } BigInteger denominator = 1; for (int i = 1; i <= (n + 1); i++) { denominator *= i; } for (int i = 1; i <= n; i++) { denominator *= i; } Console.WriteLine(numerator / denominator); } else { Console.WriteLine(1); } } }




0

Много благодаря за решението, почти веднага се опитах да го преработя в Java, но срещнах няколко трудности с пресмятането и като цяло форматирането на BigInteger. Имайки в предвид, че изпита наближава, реших да оставя детайлите за по-късно и да се върна към задачата, когато ми е по-спокойно. Проблема в решението ми дойде от това, че за разлика от C#, то при Java, когато използваме BigInteger не може да използваме директно */ за умножение или деление, както не може и да събираме/умножаваме/делим BigInteger с Int. В това отношение C# определено е по-улеснен, но пък като се заровиш в малко документация нещата вече не са толкова страшни. Прилагам за сравнение същото решение, но написано на Java:

import java.math.BigInteger; import java.util.Scanner; public class CatalanNumbers { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); if (1 <= n && n <= 100) { BigInteger numerator = BigInteger.valueOf(1); for (int i = 1; i <= (2 * n); i++) { numerator = numerator.multiply(BigInteger.valueOf(i)); } BigInteger denominator = BigInteger.valueOf(1); for (int i = 1; i <= (n + 1); i++) { denominator = denominator.multiply(BigInteger.valueOf(i)); } for (int i = 1; i <= n; i++) { denominator = denominator.multiply(BigInteger.valueOf(i)); } System.out.println(numerator.divide(denominator)); } else { System.out.println(1); } } }

Поздрави.



0

Здравей!

Относно BigInteger в Java намерих ТОЗИ линк. Тук е доста добре обяснено и също така дават хубави примери. Препоръчвам ти да го разгледаш!

Поздрави.