본문 바로가기

problem solving

Problem 19 - How many Sundays fell on the first of the month during the twentieth century? 링크 You are given the following information, but you may prefer to do some research for yourself. 1 Jan 1900 was a Monday. Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible b.. 더보기
Problem 18 - Find the maximum sum travelling from the top of the triangle to the base. 링크 By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23. 3 7 4 2 4 6 8 5 9 3 That is, 3 + 7 + 4 + 9 = 23. Find the maximum total from top to bottom of the triangle below: 75 95 64 17 47 82 18 35 87 10 20 04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 67 99 65 04 28 06 16 70 92 41 41 26 56 83 40 80 70 33 41 48 72.. 더보기
Problem 16 - What is the sum of the digits of the number 2^1000? 링크 215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26. What is the sum of the digits of the number 21000? python sum([int(x) for x in str(2**1000)]) 더보기
Problem 15 - Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner? 링크 Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner. How many routes are there through a 2020 grid? 40 C 20 (combination) 을 구하면 된다. python pascal = [[1, 0]] for i in range(1, 41): nextrow = [1] for j in range(1, i+1): nextrow.append(pascal[i-1][j] + pascal[i-1][j-1]) nextrow.append(0) pascal.append(nextrow) print pascal[40][20] 더보기
Problem 14 - Find the longest sequence using a starting number under one million. 링크 The following iterative sequence is defined for the set of positive integers: n n/2 (n is even) n 3n + 1 (n is odd) Using the rule above and starting with 13, we generate the following sequence: 13 40 20 10 5 16 8 4 2 1 It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting.. 더보기
Problem 13 - Find the first ten digits of the sum of one-hundred 50-digit numbers. 링크 Work out the first ten digits of the sum of the following one-hundred 50-digit numbers. 37107287533902102798797998220837590246510135740250 46376937677490009712648124896970078050417018260538 ... 53503534226472524250874054075591789781264330331690 이건 그냥 코딩 연습용 문제인듯 python file = open("./data") s = file.read().split("\n") ans = 0 for ss in s: if ss == "": break; ans += int(ss) print str(ans)[:10] 더보기
Problem 12 - What is the value of the first triangle number to have over five hundred divisors? 링크 The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the factors of the first seven triangle numbers: 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 We can see that 28 is the first triang.. 더보기
Problem 11 - What is the greatest product of four numbers on the same straight line in the 20 by 20 grid? 링크 In the 2020 grid below, four numbers along a diagonal line have been marked in red. 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60.. 더보기
Problem 10 - Calculate the sum of all the primes below two million. 링크 The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below two million. python - sieve of Eratosthenes def sieve(n): l = range(n+1) l[1] = 0 sqn = int(round(n**0.5)) for i in range(2, sqn + 1): if l[i] == i: l[2*i:n+1:i] = [i] * (n/i-1) return l n = 2000000 sum = 0 siv = sieve(n) for i in range(n): if siv[i] == i: sum += i print sum 더보기
Problem 9 - Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000. 링크 A Pythagorean triplet is a set of three natural numbers, a b c, for which, a2 + b2 = c2 For example, 32 + 42 = 9 + 16 = 25 = 52. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc. python for a in range(1, 999): for b in range(a, 999): c = 1000 - (a+b) if (a*a + b*b == c*c): print a*b*c python - more efficient A Pythagorean triplet (a,b,c) has gcd(a,.. 더보기

티스토리툴바