gshscs

시간 제한 2초

메모리 제한 65536KB

문제 설명

1742년 아마추어 수학자 크리스티앙 골드바흐는 레온하르트 오일러에게 이 가설이 탄생되게 된 한 편지를 보냈

다.

"4보다 큰 모든 짝수는 홀수인 두 소수의 합으로 나타낼 수 있다."

예를 들어서 8=3+5, 20=3+17=7+13, 42=5+37=11+31=13+29=19+23

아직까지 이 추측이 맞는지는 증명되지 않았다.

100만보다 작은 모든 짝수에 대해서 골드바흐의 추측이 맞다는 것을 증명하시오.

입력

입력으로 여러개의 테스트케이스가 주어진다.

각 테스트케이스에는 짝수 n이 주어진다.(6<=n<1,000,000)

0이 입력될 때 종료한다.

출력

각 테스트케이스에 대해서, "n = a + b" 꼴로 추측에 맞게 한 줄에 한개씩 출력한다. 숫자와 연산자 사이는 공백 

한 칸으로 띄어져 있다. 답이 여러 개일 경우, b-a가 최대가 되는 값을 출력한다. 답이 존재하지 않는 경우, "Goldbach's conjecture is wrong."를 출력한다.

입력 예제

8

20

42

0

출력 예제

8 = 3 + 5

20 = 3 + 17

42 = 5 + 37

http://poj.org/problem?id=2262

시간 제한 1초

메모리 제한 65536K

문제 설명

어떤 바이러스가 행성 X를 공격하여 수많은 생명체가 감염되었다. 몇 주 동안의 연구 끝에 CHO(Creature Healthy Organization)은 이 바이러스는 101과 111 두 가지의 간단한 DNA로 구성되어 있음을 발견했다. 불행히도, 행성의 생명체들도 0과 1로 구성된 DNA를 가진다. 만약 생명체의 DNA가 바이러스의 DNA를 포함하면, 그 생명체는 감염당할 것이다. 포함하지 않으면 감염되지 않는다. 정수 L이 주어졌을 때, DNA의 길이가 L인 2^L개의 생명체 중 감염당하지 않는 생명체의 수를 구하여라.

입력

정수 L(1<=L<=10^8)이 여러개 주어진다.

출력

감염당하지 않는 생명체의 수를 2005로 나눈 나머지를 출력한다.

입력 예제

4

출력 예제

9

http://poj.org/problem?id=2440

시간 제한 1초

메모리 제한 65536K

문제 설명

FJ는 N개의 칸으로 구성되어 있는 기다란 헛간을 만들었다.

FJ의 C마리 소들은 헛간의 설계를 싫어한다. 그래서 헛간 안에 집어 넣으면 공격적으로 변해버린다. 소들이 서로를 공격하는 것을 막기 위해, FJ는 두 소 사이의 최소 거리가 가장 크도록 소들을 집어 넣으려고 한다. 이 최소 거리의 최대값을 구하여라,

입력

첫번째 줄에 두 정수 N, C가 주어진다.(2<=C<=N<=100,000)

두번째 줄부터 N개의 줄에 칸의 위치 xi가 주어진다.

출력

최소 거리의 최대값을 출력하라.

입력 예제

5 3

1

2

8

4

9

출력 예제

3

http://poj.org/problem?id=2456

시간 제한 1초

메모리 제한 65536K

문제 설명

소가 먹을 건초가 바닥났다. 이런 긴급 상황에는 발빠른 조치가 필요하다. 그래서 Bessie는 다른 농장으로 가서 건초가 얼마나 있는지 조사하고자 한다. N가의 농장이 있으며 베시는 1번 농장부터 방문할 것이다. 베시는 농장 간에 연결된 M개의 왕복 도로(도로의 길이는 1,000,000,000을 초과하지 않음) 중 일부 또는 모두를 건너다닐 것이다. 어떤 농장은 각각 다른 길이의 길로 다양하게 연결되어 있을 수도 있다. 모든 농장은 1번 농장과 하나 이상의 길로 연결되어 있다.

 Bessie는 얼마나 큰 가죽 물통이 필요한지 결정하려고 하고 있다. 그녀는 한 유닛의 길에 1온스의 물이 필요하다는 것을 안다. 각 농장에서 물은 더 구할 수 있기 때문에 가장 긴 거리의 길에 대해서 걱정하고 있다. 물론, Bessie는 농장간의 경로를 미리 정해서 운반하는 물의 양을 최소화할 것이다.

 베시가 다음의 사실을 알 수 있도록 도와주어라. Bessie가 최대 얼마만큼의 물을 들고 가야 하는가? 그리고 Bessie가 최소의 거리를 선택할 것이라는 가정 하에 Bessie가 가게 될 두 농장간의 거리 중 가장 먼 거리는 얼마인가? 물론 Bessie는 지나가야 하는 길의 경로를 최소화하기 위하여 왔던 길을 되돌아 갈 수도 있다.

입력

Line 1:두 정수 N,M(2<=N<=2,000, 1<=M<=10,000)

Line 2~M+1:세 정수 A_i,B_i,L_i. A_i에서 B_i까지 가는데 L_i만큼의 거리를 가야한다는 것

출력

길을 가로지르기 위해 필요한 가장 긴 거리를 나타내는 하나의 정수를 출력한다.

입력 예제

3 3

1 2 23

2 3 1000

1 3 43

출력 예제

43

http://poj.org/problem?id=2395

시간 제한 1초

메모리 제한 30MB

문제 설명

좀비는 뇌를 좋아해요

입력

Line 1:숫자들의 쌍의 갯수 n

Line 2~n+1:뇌의 갯수 X와 좀비가 사는데 필요한 뇌의 갯수 Y

출력

좀비가 살 수 있을 정도로 뇌가 있으면 "MMM BRAINS", 없으면 "NO BRAINS"를 출력한다.

입력 예제

3

4 5

3 3

4 3

출력 예제

NO BRAINS

MMM BRAINS

MMM BRAINS

http://poj.org/problem?id=2027