C++ Programmer 구인 공지

SK C&C E-PRJ팀에서는 C++ Programmer를 모집합니다.

* 담당 업무
항공 사진을 이용한 3D Mirror World Production System 개발
cluster 로 이루어진 production system 에서 동작할 대용량 이미지 처리 s/w 구현

* 지원 자격 및 우대 사항
성별/연령/학력/경력 불문
C/C++ Expert
팀 작업에 익숙하고 다른 사람들과의 커뮤니케이션에 문제가 없는 자
영문 기술 문서 읽기에 익숙하신 분
다양한 상용/공개 라이브러리를 사용해본 경험자 우대
GIS/Computer Graphics/Computer Vision/Numerical Analysis 경험자 우대

* 대우
정직원

* 연봉
추후 협의

* 복리후생
연금/보험 : 국민연금, 고용보험, 산재보험, 건강보험
휴무/휴가 : 주5일 근무, 연차, 정기 휴가
보상 제도 : 인센티브제
건강관리 지원 : 건강검진, 본인 의료비 지원
생활안정 지원 : 자녀 학자금 지원, 직원대출제도
생활편의 지원 : 사원식당, 통근버스 운행
경조사 지원 : 각종 경조금, 경조휴가제
교육/여가 지원 : 자기계발비 지원
기타 : 사내 헬스 센터/의무실/어린이집 운영

* 전형 절차
기술 필기 -> 실무자 면접 -> 임원진 면접 -> 합격자 발표

* 기술 필기
다음의 8문제 중 3문제 이상을 풀어 source code를 메일로 제출
C++ 을 사용할 것. STL/MFC 사용하지 말 것.

• The 3n + 1 problem
• Brick Wall Patterns
• Prime Ring Problem
• System Dependencies
• The Settlers of Catan
• The partition of a cake
• Anagram
• The Skyline Problem
• Wormholes

* 제출 서류 (담당자에게 이메일 제출)
기술 필기 시험 결과 (program source code)
이력서
Project 경력 기술서

* 담당자













* 기타
E-PRJ팀은 개발자를 구인 중입니다. programming을 직접 하실 분만 지원 부탁드립니다. (PM 직군은 신규 채용 예정이 없습니다.)
문의 사항이 있으신 분은 담당자에게 연락 부탁드립니다.

LC-Display

A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.

Input

The input file contains several lines, one for each number to be displayed. Each line contains two integers s, n ( ), where n is the number to be displayed and s is the size in which it shall be displayed.

The input file will be terminated by a line containing two zeros. This line should not be processed.

Output

Output the numbers given in the input file in an LC-display-style using s ``-'' signs for the horizontal segments and s ``|'' signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits.

Output a blank line after each number. (You will find a sample of each digit in the sample output.)

Sample Input

2 12345
3 67890
0 0

Sample Output

Brick Wall Patterns

If we want to build a brick wall out of the usual size of brick which has a length twice as long as its height, and if our wall is to be two units tall, we can make our wall in a number of patterns, depending on how long we want it. From the figure one observe that:

• There is just one wall pattern which is 1 unit wide - made by putting the brick on its end.
• There are 2 patterns for a wall of length 2: two side-ways bricks laid on top of each other and two bricks long-ways up put next to each other.
• There are three patterns for walls of length 3.

How many patterns can you find for a wall of length 4? And, for a wall of length 5?

Problem

Your task is to write a program that given the length of a wall, determines how many patterns there may be for a wall of that length.

Intput

Your program receives a sequence of positive integers, one per line, each representing the length of a wall. The maximum value for the wall is length 50. The input terminates with a 0.

Output

For each wall length given in the input, your program must output the corresponding number of different patterns for such a wall in a separate line.

Sample Intput

1
2
3
0

Sample Output

1
2
3

Wormholes

In the year 2163, wormholes were discovered. A wormhole is a subspace tunnel through space and time connecting two star systems. Wormholes have a few peculiar properties:

• Wormholes are one-way only.

• The time it takes to travel through a wormhole is negligible.

• A wormhole has two end points, each situated in a star system.

• A star system may have more than one wormhole end point within its boundaries.

• For some unknown reason, starting from our solar system, it is always possible to end up in any star system by following a sequence of wormholes (maybe Earth is the centre of the universe).

• Between any pair of star systems, there is at most one wormhole in either direction.

• There are no wormholes with both end points in the same star system.

All wormholes have a constant time difference between their end points. For example, a specific wormhole may cause the person travelling through it to end up 15 years in the future. Another wormhole may cause the person to end up 42 years in the past.

A brilliant physicist, living on earth, wants to use wormholes to study the Big Bang. Since warp drive has not been invented yet, it is not possible for her to travel from one star system to another one directly. This can be done using wormholes, of course.

The scientist wants to reach a cycle of wormholes somewhere in the universe that causes her to end up in the past. By travelling along this cycle a lot of times, the scientist is able to go back as far in time as necessary to reach the beginning of the universe and see the Big Bang with her own eyes. Write a program to find out whether such a cycle exists.

Input

The input file starts with a line containing the number of cases c to be analysed. Each case starts with a line with two numbers n and m . These indicate the number of star systems ( ) and the number of wormholes ( ) . The star systems are numbered from 0 (our solar system) through n-1 . For each wormhole a line containing three integer numbers x, y and t is given. These numbers indicate that this wormhole allows someone to travel from the star system numbered x to the star system numbered y, thereby ending up t ( ) years in the future.

Output

The output consists of c lines, one line for each case, containing the word possible if it is indeed possible to go back in time indefinitely, or not possible if this is not possible with the given set of star systems and wormholes.

Sample Input

2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

Sample Output

possible
not possible

The Settlers of Catan

Within Settlers of Catan, the 1995 German game of the year, players attempt to dominate an island by building roads, settlements and cities across its uncharted wilderness.

You are employed by a software company that just has decided to develop a computer version of this game, and you are chosen to implement one of the game's special rules:

When the game ends, the player who built the longest road gains two extra victory points.

The problem here is that the players usually build complex road networks and not just one linear path. Therefore, determining the longest road is not trivial (although human players usually see it immediately).

Compared to the original game, we will solve a simplified problem here: You are given a set of nodes (cities) and a set of edges (road segments) of length 1 connecting the nodes. The longest road is defined as the longest path within the network that doesn't use an edge twice. Nodes may be visited more than once, though.

Example: The following network contains a road of length 12.

Input

The input file will contain one or more test cases.

The first line of each test case contains two integers: the number of nodes n ( ) and the number of edges m ( ). The next m lines describe the m edges. Each edge is given by the numbers of the two nodes connected by it. Nodes are numbered from 0 to n-1. Edges are undirected. Nodes have degrees of three or less. The network is not neccessarily connected.

Input will be terminated by two values of 0 for n and m.

Output

For each test case, print the length of the longest road on a single line.

Sample Input

3 2
0 1
1 2
15 16
0 2
1 2
2 3
3 4
3 5
4 6
5 7
6 8
7 8
7 9
8 10
9 11
10 12
11 12
10 13
12 14
0 0

Sample Output

2
12

The partition of a cake

There is a 10001000 square cake. We use knife to cut the cake. The problem is after a series of cutting, how many partitions the cake will has.

Assumption:

1.

The number of the cutting will be no more than 8.

2.

After the cutting, the length of any edge of the partition will no less than 1.

3.

The vertex coordinates of the cake are (0,0)(0,1000)(1000,1000) (1000,0).

4.

The intersections of the cut line and the cake edge are two .

The following Graph is a sample partition. The number of the partitions is 10.

Input

The first line of the input is an integer M, then a blank line followed by M datasets. There is a blank line between datasets.The first line of each dataset is the number of the cutting . The following lines contain the information of the cut lines. Each line has 4 integer number, which represent the coordinate of the intersection of the cut line and the cake edge.

Output

The output for each dataset is the number of the partitions of the cake. Print a blank line between datasets.

Sample Input

1

3
0 0 1000 1000
500 0 500 1000
0 500 1000 500

Sample Output

6

System Dependencies

Components of computer systems often have dependencies--other components that must be installed before they will function properly. These dependencies are frequently shared by multiple components. For example, both the TELNET client program and the FTP client program require that the TCP/IP networking software be installed before they can operate. If you install TCP/IP and the TELNET client program, and later decide to add the FTP client program, you do not need to reinstall TCP/IP.

For some components it would not be a problem if the components on which they depended were reinstalled; it would just waste some resources. But for others, like TCP/IP, some component configuration may be destroyed if the component was reinstalled.

It is useful to be able to remove components that are no longer needed. When this is done, components that only support the removed component may also be removed, freeing up disk space, memory, and other resources. But a supporting component, not explicitly installed, may be removed only if all components which depend on it are also removed. For example, removing the FTP client program and TCP/IP would mean the TELNET client program, which was not removed, would no longer operate. Likewise, removing TCP/IP by itself would cause the failure of both the TELNET and the FTP client programs. Also if we installed TCP/IP to support our own development, then installed the TELNET client (which depends on TCP/IP) and then still later removed the TELNET client, we would not want TCP/IP to be removed.

We want a program to automate the process of adding and removing components. To do this we will maintain a record of installed components and component dependencies. A component can be installed explicitly in response to a command (unless it is already installed), or implicitly if it is needed for some other component being installed. Likewise, a component, not explicitly installed, can be explicitly removed in response to a command (if it is not needed to support other components) or implicitly removed if it is no longer needed to support another component. Installing an already implicitly-installed component won't make that component become explicity installed.

Input

The input will contain a sequence of commands (as described below), each on a separate line containing no more than eighty characters. Item names are case sensitive, and each is no longer than ten characters. The command names (DEPEND, INSTALL, REMOVE and LIST) always appear in uppercase starting in column one, and item names are separated from the command name and each other by one or more spaces. All appropriate DEPEND commands will appear before the occurrence of any INSTALL command that uses them. There will be no circular dependencies. The end of the input is marked by a line containing only the word END.

Command Syntax	Interpretation/Response
DEPEND item1 item2 [item3 ...]	item1 depends on item2 (and item3 ...)
INSTALL item1	install item1 and those on which it depends
REMOVE item1	remove item1, and those on which it depends, if possible
LIST	list the names of all currently-installed components

Output

Echo each line of input. Follow each echoed INSTALL or REMOVE line with the actions taken in response, making certain that the actions are given in the proper order. Also identify exceptional conditions (see Sample Output, below, for examples of all cases). For the LIST command, display the names of the currently installed components in the installation order. No output, except the echo, is produced for a DEPEND command or the line containing END. There will be at most one dependency list per item.

Sample Input 1

DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
INSTALL TELNET
INSTALL foo
REMOVE NETCARD
INSTALL BROWSER
INSTALL DNS
LIST
REMOVE TELNET
REMOVE NETCARD
REMOVE DNS
REMOVE NETCARD
INSTALL NETCARD
REMOVE TCPIP
REMOVE BROWSER
REMOVE TCPIP
END

Sample Output 1

DEPEND   TELNET TCPIP NETCARD
DEPEND TCPIP NETCARD
DEPEND DNS TCPIP NETCARD
DEPEND  BROWSER   TCPIP  HTML
INSTALL NETCARD
  Installing NETCARD
INSTALL TELNET
  Installing TCPIP
  Installing TELNET
INSTALL foo
  Installing foo
REMOVE NETCARD
  NETCARD is still needed.
INSTALL BROWSER
  Installing HTML
  Installing BROWSER
INSTALL DNS
  Installing DNS
LIST
  NETCARD
  TCPIP
  TELNET
  foo
  HTML
  BROWSER
  DNS
REMOVE TELNET
  Removing TELNET
REMOVE NETCARD
  NETCARD is still needed.
REMOVE DNS
  Removing DNS
REMOVE NETCARD
  NETCARD is still needed.
INSTALL NETCARD
  NETCARD is already installed.
REMOVE TCPIP
  TCPIP is still needed.
REMOVE BROWSER
  Removing BROWSER
  Removing HTML
  Removing TCPIP
REMOVE TCPIP
  TCPIP is not installed.
END

Sample Input 2

DEPEND A B
INSTALL A
INSTALL B
REMOVE A
END

Sample Output 2

DEPEND A B
INSTALL A
  Installing B
  Installing A
INSTALL B
  B is already installed.
REMOVE A
  Removing A
  Removing B
END

Anagram

You are to write a program that has to generate all possible words from a given set of letters.

Example: Given the word "abc", your program should - by exploring all different combination of the three letters - output the words "abc", "acb", "bac", "bca", "cab" and "cba".

In the word taken from the input file, some letters may appear more than once. For a given word, your program should not produce the same word more than once, and the words should be output in alphabetically ascending order.

Input

The input file consists of several words. The first line contains a number giving the number of words to follow. Each following line contains one word. A word consists of uppercase or lowercase letters from A to Z. Uppercase and lowercase letters are to be considered different.

Output

For each word in the input file, the output file should contain all different words that can be generated with the letters of the given word. The words generated from the same input word should be output in alphabetically ascending order. An upper case letter goes before the corresponding lower case letter.

Sample Input

3
aAb
abc
acba

Sample Output

Aab
Aba
aAb
abA
bAa
baA
abc
acb
bac
bca
cab
cba
aabc
aacb
abac
abca
acab
acba
baac
baca
bcaa
caab
caba
cbaa

The Skyline Problem

Background

With the advent of high speed graphics workstations, CAD (computer-aided design) and other areas (CAM, VLSI design) have made increasingly effective use of computers. One of the problems with drawing images is the elimination of hidden lines -- lines obscured by other parts of a drawing.

The Problem

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple where and are left and right coordinates, respectively, of building i and is the height of the building. In the diagram below buildings are shown on the left with triples (1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)

the skyline, shown on the right, is represented by the sequence: (1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0)

The Input

The input is a sequence of building triples. All coordinates of buildings are positive integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by , the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.

The Output

The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector , the such that i is an even number represent a horizontal line (height). The such that i is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the ``path'' taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.

Sample Input

1 11 5
2 6 7
3 13 9
12 7 16
14 3 25
19 18 22
23 13 29
24 4 28

Sample Output

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Prime Ring Problem

A ring is composed of n (even number) circles as shown in diagram. Put natural numbers into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input

n (0 < n <= 16)

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements.

You are to write a program that completes above process.

Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

The 3n + 1 problem

Background

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

The Problem

Consider the following algorithm:

 1.    input n

  2.    print n

  3.    if n = 1 then STOP

  4.       if n is odd then  

  5.       else  

  6.    GOTO 2

Given the input 22, the following sequence of numbers will be printed 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

It is conjectured that the algorithm above will terminate (when a 1 is printed) for any integral input value. Despite the simplicity of the algorithm, it is unknown whether this conjecture is true. It has been verified, however, for all integers n such that 0 < n <>

Given an input n, it is possible to determine the number of numbers printed (including the 1). For a given n this is called the cycle-length of n. In the example above, the cycle length of 22 is 16.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.

The Input

The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0.

You should process all pairs of integers and for each pair determine the maximum cycle length over all integers between and including i and j.

You can assume that no operation overflows a 32-bit integer.

The Output

For each pair of input integers i and j you should output i, j, and the maximum cycle length for integers between and including i and j. These three numbers should be separated by at least one space with all three numbers on one line and with one line of output for each line of input. The integers i and j must appear in the output in the same order in which they appeared in the input and should be followed by the maximum cycle length (on the same line).

Sample Input

1 10
100 200
201 210
900 1000

Sample Output

1 10 20
100 200 125
201 210 89
900 1000 174