gshscs

시간 제한 1초

메모리 제한 65536K

문제 설명

K마리의 소들이 FJ의 읽기 대회에 참가한다. 소들은 N 페이지의 책 한권을 최대한 빨리 읽어야 한다.

소 i가 1분에 읽는 속도 Si, 쉬지 않고 읽을 수 있는 최대의 시간 Ti, 쉬어야 하는 최도의 시간 Ri가 주어진다. 소는 1분에 최대 Si 페이지를 읽을 수 있지만, Ti분 동안만 읽을 수 있다. 쉬려고 책 읽는 것을 중단하면 무조건 Ri분 동안 쉬어야 한다.

각 소가 책을 읽는데 걸리는 시간을 구하시오.

입력

첫번째 줄에는 정수 N, K가 주어진다.(1<=K<=1,000, 1<=N,=100,000)

두번째 줄부터 K개의 줄에 세 정수 Si, Ti, Ri가 주어진다.(1<=Si, Ti, Ri<=100)

출력

K개의 줄에 각 소가 책을 읽는데 걸리는 시간을 출력한다.

입력 예제

10 3

2 4 1

6 1 5

3 3 3

출력 예제

6

7

7

예제 설명

1번 소는 처음 4분 동안 2페이지씩 8페이지를 읽고 1분 쉰 후, 다음 1분 동안 2페이지를 읽는다.

2번 소는 처음 6페이지를 읽고, 5분 쉰 후, 남은 4페이지를 읽는다.

3번 호는 3페이지를 3분 동안 읽고 3분 쉰 후, 남은 1페이지를 읽는다.

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

시간 제한 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초

메모리 제한 10000KB

문제 설명

S=s1 s2 ... s2n가 괄호로 구성되어 있는 잘 만들어진 문자열이라고 하자. S는 두 가지 방법으로 암호화할 수 있다.

1. pi가 i번째 오른쪽 괄호 왼쪽에 있는 왼쪽 괄호의 개수인 수열 P=p1 p2 ... pn

2. wi가 i번째 오른쪽 괄호와 짝인 왼쪽 괄호부터 오른쪽 괄호의 개수인 수열 W=w1 w2 ... wn

이 때, 수열 P를 수열 W로 바꾸는 프로그램을 작성하시오.

입력

첫번째 줄에 테스트 케이스의 개수 t(1<=t<=10)가 주어진다.

각 테스트 케이스에 대해서

첫번째 줄에 수열의 길이 n(1<=n<=20),

두번째 줄에 잘 만들어진 길이 n의 수열 P가 주어진다.

출력

각 테스트 케이스에 대해서 수열 W를 출력한다.

입력 예제

2

6

4 5 6 6 6 6

9

4 6 6 6 6 8 9 9 9

출력 예제

1 1 1 4 5 6

1 1 2 4 5 1 1 3 9

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

시간 제한 2초

메모리 제한 65536KB

문제 설명

 매년 소를 위한 특이한 형태의 징검다리 건너기 축제가 열리는데, 이것은 강에서 한 바위에서 다른 바위 위로 조심스럽게 뛰어다니는 것이다. 길고 직선인 강에서 출발점의 바위에서부터 L 유닛의 거리를 지나 결승점의 바위로 가는 것이다. 출발점의 바위에서부터 Di의 거리만큼 동일하게 간격을 두고 있다.

 경기는 각 소들이 차례로 출발점에서 시작하여 결승점까지 도달하는 것인데 바위에서 바위로 점프해야만 한다. 물론 민첩하지 못한 소들은 결승점까지 갈 수 없을 것이며 대신 강 속에 빠지고 말 것이다.

 FJ는 자신의 소를 매우 자랑스럽게 여기기 때문에 매년 이 경기를 지켜본다. 하지만 시간이 갈수록 다른 농부들의 소심한 소들이 다닥다닥 붙어있는 짧은 거리에서조차도 뒤뚱거리는 경기를 관람하는 것이 지겨워졌다. 그래서 그는 소가 점프해야하는 최단거리를 늘리기 위해 몇 개의 바위를 없애기로 결심했다. 물론 출발점과 결승점의 바위는 없애면 안된다. 하지만 그는 M개의 바위를 제거하려고 계산하고 있다.

 FJ는 바위를 제거하기 "전에" 최단거리를 얼마나 증가시킬 수 있는지 알고 싶어한다. 적절한 M개의 바위를 없앤 뒤에 소가 점프해야 하는 최단거리의 최대값을 구할 수 있도록 FJ를 도와라.

입력

Line 1:공백으로 구분된 정수 L,N,M이 온다.(1<=L<=1,000,000,000, 0<=M<=N<=50,000)

Line 2~Line N+1:각 줄에 출발점으로부터 바위들이 얼마나 멀리 떨어져 있는지를 나타내는 하나의 정수가 온다. 두 바위는 같은 위치에 있을 수 없다.

출력

M개의 바위를 치운 뒤 소가 점프할 수 있는 최단거리의 최대값을 나타내는 하나의 정수가 온다.

입력 예제

25 5 2

2

14

11

21

17

출력 예제

4

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

시간 제한 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

a,b를 입력받아서 a+b를 출력하면 된다.

#include <stdio.h>
int main(){
    int a,b;
    scanf("%d %d",&a, &b);
    printf("%d\n",a+b);
    return 0;
}


번역:http://gshscs.tistory.com/1