9._.coding

좌표평면의 점들의 좌표가 주어지고, 모든 점들을 포함하는 가장 작은 볼록 다각형인 Convex Hull을 찾는 문제이다. Jarvis March Algorithm(=Gift Wrapping - 선물 포장 알고리즘)으로 문제를 해결한다. Problem One day, a lawn in the centre of campus became infested with Frosh. In an effort to beautify the campus, one of our illustrious senior classmen decided to round them up using a length of pink silk. Your job is to compute how much silk was required to complet..

입력 파일이 좌표(x,y)로 주어지고 가장 가까운 두 점을 찾는 문제. Divide-conquer 기법을 사용한 Closest-pair problem(최근접 점의 쌍)으로 문제를 해결한다. Problem A telephone company seeks to claim they provide high-speed broadband access to customers. It will suffice for marketing purposes if they can create just one such link directly connecting two locations.  As the cost for installing such a pair of locations are the shortest distance ap..

Problem One day, a lawn in the centre of campus became infested with Frosh. In an effort to beautify the campus, one of our illustrious senior classmen decided to round them up using a length of pink silk. Your job is to compute how much silk was required to complete the task. The senior classman tied the silk to a telephone post, and walked around the perimeter of the area containing the Frosh,..

Problem A number of students are members of a club that travels annually to exotic locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven. The group agrees in advance to share expenses equally, but it is not practical to have them share every expense as it occurs. So individu..

LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. LCS의 개념 : [알고리즘] 최장 공통 부분수열 / LCS - Longest Common Subsequences Longest Common Subsequence, ..

Problem I have some (say, n) marbles (small glass balls) and I am going to buy some boxes to store them. The boxes are of two types: T ype 1: each box costs c1 Taka and can hold exactly n1 marbles T ype 2: each box costs c2 Taka and can hold exactly n2 marbles I want each of the used boxes to be filled to its capacity and also to minimize the total cost of buying them. Since I find it difficult ..

Problem In an episode of the Dick Van Dyke show, little Richie connects the freckles on his Dad’s back to form a picture of the Liberty Bell. Alas, one of the freckles turns out to be a scar, so his Ripley’s engagement falls through. Consider Dick’s back to be a plane with freckles at various (x, y) locations. Your job is to tell Richie how to connect the dots so as to minimize the amount of ink..

Problem Problems that require minimum paths through some domain appear in many different areas of computer science. For example, one of the constraints in VLSI routing problems is minimizing wire length. The Traveling Salesperson Problem (TSP) — finding whether all the cities in a salesperson’s route can be visited exactly once with a specified limit on travel time — is one of the canonical exam..

Problem A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally, given a sequence X = x1x2 . . . xm, another sequence Z = z1z2 . . . zk is a subsequence of X if there exists a strictly increasing sequence of indices of X such that for all j = 1, 2, . . . , k, we have xij = zj . For example, Z = bcdb is a subsequenc..

Shoemaker has N jobs (orders from customers) which he must make. Shoemaker can work on only one job in each day. For each i-th job, it is known the integer Ti (1 ≤ Ti ≤ 1000), the time in days it takes the shoemaker to finish the job. For each day of delay before starting to work for the i-th job, shoemaker must pay a fine of Si (1 ≤ Si ≤ 10000) cents. Your task is to help the shoemaker, writing..