0과 1의 쉼터

문제The famous Euclidean algorithm is found in Book VII of the Elements. The Elements was written in 300 B.C.~by the Greek mathematician Euclid. It is rumored that King Ptolemy, having looked through the Elements, hopefully asked Euclid if there were not a shorter way to geometry, to which Euclid severely answered: "In geometry there is no royal road!" Probably we should not blame the King for loo..

문제N개의 소수와 자연수 M이 주어진다. M 이하의 자연수 중에서 N개의 소수 중 적어도 하나로 나누어 떨어지는 수의 개수를 세어보자.입력첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다.출력첫째 줄에 M 이하의 자연수 중에서 N개의 소수 중 적어도 하나로 나누어 떨어지는 수의 개수를 출력한다.풀이M이하의 자연수 중에서 주어진 N개의 소수 중 적어도 하나로 나누어 떨어지는 수의 개수를 구해야 한다.즉, M이하의 자연수 중 N개의 소수들에 대한 배수로 이루어진 합집합의 원소 수를 구하는 문제다.이는 포함 배제의 원리를 사용해 쉽게 풀이할 수 있다. ..

문제Consider a six-sided die, with sides labeled 1 through 6. We say the die is fair if each of its sides is equally likely to be face up after a roll. We say the die is loaded if it isn’t fair. For example, if the side marked 6 is twice as likely to come up as than any other side, we are dealing with a loaded die.For any die, define the expected result of rolling the die to be equal to the averag..

문제알고리즘 수업을 듣고 감명받은 윤이는 자신만의 정렬 알고리즘을 만들기로 했다. 윤이가 만든 정렬 알고리즘 "트리플 소트"는 다음과 같이 동작한다.배열에서 연속한 위치에 있는 세 원소를 임의로 고른다.세 원소의 순서를 뒤집는다. 예를 들어 세 원소가 순서대로 a,b,c이면 뒤집은 뒤에는 c,b,a가 된다.배열이 오름차순으로 정렬될 때까지 위 과정을 반복한다.하지만 윤이는 트리플 소트로 모든 배열을 정렬할 수 없다는 사실을 깨닫고 실망했다. 1부터 N까지의 정수가 한 번씩 등장하는 배열이 주어졌을 때, 트리플 소트로 정렬할 수 있는지 판별하는 프로그램을 작성하시오.입력첫 번째 줄에 배열의 크기를 나타내는 정수 N이 주어진다.두 번째 줄에 배열의 원소가 공백을 사이에 두고 순서대로 주어진다.출력트리플 소트..

문제In days of yore (circa 1965), mechanical calculators performed division by shifting and repeated subtraction. For example, to divide 987654321 by 3456789, the numbers would first be aligned by their leftmost digit (see (1) below), and the divisor subtracted from the dividend as many times as possible without yielding a negative number. The number of successful subtractions (in this example, 2)..

문제From the article Number Theory in the 1994 Microsoft Encarta: "If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not 1, b is called a proper divisor of a. Even integers, which include 0, are multiples of 2, for example, -4, 0, 2, 10; an odd integer is an integer that is not even, for example, -5, 1, 3, 9. A per..

문제Stanley is very prudent when it comes to his finances. He enjoys a somewhat spartan lifestyle and watches every penny he spends. Those few who call him friend view him as economical, abstemious, and parsimonious. He’s basically a miserly tightwad.Stan will never go shopping unless he has coupons. At the moment he has a bit of a conundrum. There are three items he wants to buy which have list c..

문제In this age of Internet, on-line connections, instantaneous email, etc., there are still some people who need to work with floppy disks. John is one of those. Every evening he goes home and continues what he has been doing in his office on his private UNIX system. He copies all the files he needs to floppy disks according to the following procedure:Put all files in one big SHAR file.Compress t..

문제양의 정수 N의 디지털 루트를 구하려면 N을 이루고 있는 모든 자리수를 더해야 한다. 이때, 더한 값이 한 자리 숫자라면, 그 수가 N의 디지털 루트가 된다. 두 자리 이상 숫자인 경우에는 다시 그 수를 이루고 있는 모든 자리수를 더해야 하며, 한 자리 숫자가 될 때 까지 반복한다.24의 디지털 루트를 구해보자. 2+4=6이다. 6은 한 자리 숫자이기 때문에, 24의 디지털 루트는 6이 된다. 39의 경우에는 3+9=12이기 때문에, 한 번 더 더해야 한다. 따라서, 1+2=3이 디지털 루트가 된다.양의 정수 N이 주어졌을 때, 그 수의 디지털 루트를 구하는 프로그램을 작성하시오.입력한 줄에 하나씩 양의 정수가 주어진다. 입력의 마지막 줄은 0으로 나타낸다.  수는 최대 1000자리이다.출력입력으로 ..

문제컴퓨터를 이용하면 수학 계산이 조금 쉬워진다. 다음과 같은 예를 살펴보자. 세 변의 길이가 a, b, c(c는 빗변)이면서 a2+b2=c2를 만족하는 삼각형을 직각삼각형이라고 한다. 이 공식은 피타고라스의 법칙이라고 한다.직각 삼각형의 두 변의 길이가 주어졌을 때, 한 변의 길이를 구하는 프로그램을 작성하시오.입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직각 삼각형의 세 변의 길이 a, b, c가 주어진다. a, b, c중 하나는 -1이며, -1은 알 수 없는 변의 길이이다. 다른 두 수는 10,000보다 작거나 같은 자연수이다.입력의 마지막 줄에는 0이 세 개 주어진다. 출력각 테스트 케이스에 대해서, 입력으로 주어진 길이로 직각 삼각형을 만들 ..