We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #45: Triangular, pentagonal, and hexagonal
Project Euler #45: Triangular, pentagonal, and hexagonal
Contest ends in
+ 0 comments 100/- points python3, mathematical solve
def triangular(n): return (n)*(n+1)//2 def pentagonal(n): return n*(3*n-1)//2 def hexagonal(n): return n*(2*n-1) def lint(n): if int(n)==n: return int(n) else: return int(n)+1 triangulars=set() pentagonals=set() hexagonals=set() item=input().split() n=int(item[0]) a=int(item[1]) i=1 if a==3: for i in range(1,lint((-1+(8*n)**0.5)/2)): y=(1+12*(i)*(i+1))**0.5 if int(y)==y: if (1+int(y)) % 6 == 0: print(triangular(i)) else: for i in range(1,lint((1+(24*n)**0.5)/6)): y=(4+16*i*(3*i-1))**0.5 if int(y)==y: if (2+int(y)) % 8 == 0: print(pentagonal(i))
+ 0 comments why is this getting timed out?
import math def checkTriangular(num): return (math.sqrt(8*num+1)-1)%2==0 def checkpentagonal(num): return (math.sqrt(24*num+1)+1)%6==0 def checkhexagonal(num): return (math.sqrt(8*num+1)+1)%4==0 n,a,b=map(int,input().split(" ")) if a==3 and b==5: for i in range(1,n): if checkTriangular(i) and checkpentagonal(i): print(i) else: for i in range(1,n): if checkpentagonal(i)and checkhexagonal(i): print(i)
+ 0 comments C++ Solution :
#include <bits/stdc++.h> using namespace std; #define all(v) (v).begin(), (v).end() #define debug(x) cout << #x << " = " << x << endl typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; inline ll Mod(ll x, ll mod) { return x % mod >= 0 ? x % mod : x % mod + mod; } ll *tri = new ll[20000001]; ll *penta = new ll[20000001]; ll *hexa = new ll[20000001]; const ll N = 20000000; int main() { ios_base::sync_with_stdio(false); cin.tie(0); tri[0] = penta[0] = hexa[0] = 0; for (ll i = 1; i <= N; i++) { tri[i] = i * (i + 1) / 2; penta[i] = i * (3 * i - 1) / 2; hexa[i] = i * (2 * i - 1); } vector<ll> ans; ans.reserve(1000); ll n, a, b; cin >> n >> a >> b; if (a == 3) { ll i = 1; while (tri[i] < n) { if (binary_search(penta, penta + N + 1, tri[i])) ans.emplace_back(tri[i]); i++; } } else if (a == 5) { ll i = 1; while (hexa[i] < n) { if (binary_search(penta, penta + N + 1, hexa[i])) ans.emplace_back(hexa[i]); i++; } } sort(all(ans)); for (ll i : ans) cout << i << '\n'; delete[] penta, hexa, tri; }
+ 0 comments First generate all pentagonal, triangle and hexagonal numbers below 2*10^14 . Then for each test case, use binary search to find the answer.
+ 0 comments you can find my java solution here
Load more conversations
Sort 25 Discussions, By:
Please Login in order to post a comment