Posts

Showing posts from June, 2016

Project Euler 155 Counting Capacitor Circuits

Image
It was very complicated and hard problem when I saw this problem for the first time.
at that time I thought I could not solve this one.
and actually gave up to solve it. because I can't come up with any idea and Algorithm.

after one year from that time with algorithm study.
I have confidence and retry to solve it.
I got an answer of that problem.

Hint is dynamic problem and bruteforce and hashset

that is all
If you have more detail of it reply plz~


https://projecteuler.net/problem=155

An electric circuit uses exclusively identical capacitors of the same value C.
The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit. Using this simple procedure and up to n identical capacitors, we can make circuits having a range of different total capacitances. For example, using up to n=3 capacitors of 60 F each, we can obtain…

Project Euler 200 prime-proof sqube

We shall define a sqube to be a number of the form, p2q3, where p and q are distinct primes.
For example, 200 = 5223 or 120072949 = 232613. The first five squbes are 72, 108, 200, 392, and 500. Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008. Find the 200th prime-proof sqube containing the contiguous sub-string "200".


this problem is not hard but for fun~!
hint is generate numbers until 10^13

Project Euler 201 Subsets with a unique sum

For any set A of numbers, let sum(A) be the sum of the elements of A.
Consider the set B = {1,3,6,8,10,11}.
There are 20 subsets of B containing three elements, and their sums are: sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29. Some of these sums occur more than once, others are unique.
For a set A, let U(A,k) be the set of unique sums of k-element subsets of A, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} and sum(U(B,3)) = 156. Now consider the 100-element set S = {12, 22, ... , 1002}.
S has 100891344545564193334812497256 50-element subsets. Determine the sum of all integers which are the sum of exactly one of the 50-element subsets of S, i.e. fi…

Project Euler 401 Sum of squares of divisors

The divisors of 6 are 1,2,3 and 6.
The sum of the squares of these numbers is 1+4+9+36=50. Let sigma2(n) represent the sum of the squares of the divisors of n. Thus sigma2(6)=50. Let SIGMA2 represent the summatory function of sigma2, that is SIGMA2(n)=∑sigma2(i) for i=1 to n.
The first 6 values of SIGMA2 are: 1,6,16,37,63 and 113.
Find SIGMA2(1015) modulo 109.

I have to found SIGMA2(10^15) for bruteforce I cant't solve in my life time
hint  1^2 + 2^2 + 3^2 + 4^2+ 5^2 + .... N^2 = n(n+1)(2n+1)/6
and what you can do is find answer.~!!!!!!

Project Euler 110

In the following equation x, y, and n are positive integers. 1
x + 1
y = 1
n It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred. What is the least value of n for which the number of distinct solutions exceeds four million?

My solution~!

1/x + 1/y = 1/n
n/x + n/y = 1
n + nx/y = x
ny + nx = xy
xy - ny -nx =0
xy -ny -nx + n^2 = n^2
(x-n)(y-n) = n^2

if I change x-n = A
               y-n = B

AB = n^2
A and B is divisor of n^2
so we can calculate count of divisors of n^2.

just find n that divisorCount/2 exceeds four million.






Project Euler 148 Pascal's triangle

I solved this one by looking at pattern. Triangular number fractal??? anyway I just used triangular function. from F(1) to F(7) = n(n+1)/2 F(7^2) = F(7)*F(7) F(7^3) = F(7)*F(7)*F(7) what is if F(7^a-3) ? we know that the power of 7 grater than (7^a)-3 is a so we can find this val v = 7^a/7^(a-1) r = 7^a mod 7^(a-1) and finally got recursive function F(7^a-1) = if (r >0) F(v)*F(7)*F(7) + (v+1) * F(r) else F(v)*F(7)*F(7) and Finally I got answer quickly index : 1 1 index : 2 11 index : 3 111 index : 4 1111 index : 5 11111 index : 6 111111 index : 7 1111111 index : 8 1......1 index : 9 11.....11 index : 10 111....111 index : 11 1111...1111 index : 12 11111..11111 index : 13 111111.111111 index : 14 11111111111111 index : 15 1......1......1 index : 16 11.....11.....11 index : 17 111....111....111 index : 18 1111...1111...1111 index : 19 11111..11111..11111 index : 20 111111.111111.111111 index : 21 1111111111111111111…

Project Euler 169

I sovled thinking about more than 10hours.

anyway sovled it.

hint
1. binary
2. even number , odd number

Project Euler 277 A Modified Collatz sequence

My answer was
left - right and right - left brute force

any good idea is expand sequence and find x

anyway I success

Project Euler 162 Hexadecimal numbers

This problem I thought about more than 2 hours.
My access was combination~!
and Finally got answer O(n^3)
16length ^ 3
Other people solved it O(n)

Project Euler 387 Harshad Numbers

This is an easy problem.
when we solve problem there are something to be considered.
I will tell you one tip.


1. from small number to Big number
 - problem give us find big number for example sum of over 10^14. just find the answer of smaller number ex) 10^3, 10^4 and check your logic if it is working fine.

I solve this problem by using dp.

Project Euler 500

I thought much time and finally got hint

min heap

Project Euler 501 Eight Divisors

I think much time to solve this problem. but easily i got depressed because finding primes under 10^12 is too big. my computer can only 10^9 by using Prime sieve.
so I had to find how to count primeCount under some number.
finally I solved it~!