20.05.26 - 2015 ACM-ICPC 연습

https://www.acmicpc.net/contest/view/116

2015 ACM-ICPC 연습

오늘 늦잠 잘 정도로 컨디션도 안좋고, 오른쪽 손목이 좋지 않아서 조금만 하려고 했습니다.

하지만 막상 문제를 풀려니까 저번에 풀려고 적어 놓은 문제가 상당히 어려웠습니다.

그래서 남은 시간 문제 해석을 다 해놓고 해결방안이 기억이 난다면 메모를 해놓으려 합니다.

해석 하고 나니까 영어로 된 문제 중 쉬운 문제가 많아 슬펐습니다.

Party

문제

남성 그룹과 여성 그룹이 파티를 갖을 때마다 데이트를 1번 한다.

남성 그룹의 그룹원들이 최소 1번 이상 데이트를 할 때까지 개최되어야 하는 파티의 최소 수를 구해야 한다.만약 파티 횟수와 관계 없이 데이트가 불가능한 남성 그룹원이 발생한다면 impossible을 출력한다.

 

입력

n

m f

w1 m1 ... mw

.....

wf m1 .... mw

 

n = 테스트 횟수

m = 파티에 참여하는 남성의 수

f = 파티에 참여하는 여성의 수

w* = *번째 여성이 데이트 하고 싶은 남성의 수

m* = 여성이 데이트 하고 싶은 남성의 순번

 

출력

모든 남성들이 최소 1번 이상 데이트를 할 수 있는 파티 횟수

횟수와 관계 없이 데이트를 못하는 남성이 있을 경우 impossible 출력

 

해결방안

1. m*의 값이 0부터 m까지 모두 존재하는지 확인. 없을 경우 impossible

2. 

 

Save the computer!

문제

한 학기동안 컴퓨터를 맞췄을 때, 학기동안 파산하지 않을 확률을 구해야 한다.

컴퓨터는 여러 부품으로 되어 있는데, 하나라도 망갖기면 컴퓨터가 구동하지 않는다.

남은 돈으로 망가진 부품을 새로 교체 할 수 있다.

i번째 부품이 학기동안 k번 망가질 확률은 e^-a(i) * a(i)^k / k!이다.

a(i) = i번째 부품이 학기동안 망가지는 횟수의 기대값

k = 망가지는 횟수

 

입력

n

c b

a(0) .... a(c)

p(0) .... p(c)

 

n = 테스트 횟수

c = 부품 갯수

b = 컴퓨터 부품 구매에 투자 할 수 있는 잔액

a(i) = i번째 부품이 학기동안 망가지는 횟수의 기대값

p(i) = i번째 부품의 가격

 

출력

파산하지 않는 최고 확률

 

Fridge of Your Dream

컴퓨터 옆에 설치한 냉장고는 안에 콜라 무게를 LED로 표현한다.

이를 10진수로 변환하여 화면에 표현하자

 

입력

n

b

 

n = 테스트 횟수

b = 24자리의 이진수 숫자

 

출력

입력된 이진수 수를 십진수로 표현

 

해결방안

1. 2^0에서 2^24까지 값이 저장된 메모리를 생성한다.

2. 입력된 수를 뒤에서부터 문자 하나씩 받아 메모리 값과 곱하여 합산한다.

 

 

Scorched Earth

문제

포트리스와 같은 게임으로 적과 자신의 위치, 미사일을 쏘는 각도, 속도, 중력가속도(9.8m/s^2), 바람이 존재한다.

이 때 주어진 조건 하에 어느 속도로 쏴야 적을 맞추는지 연산해야 한다.

 

입력

n

x1 y1 x2 y2 w d

 

n = 테스트 횟수

(x1, y1) = 자신의 탱크 위치

(x2, y2) = 상대의 탱크 위치

w = 바람 세기(가속도)

d = 각도

 

출력

적을 맞출 수 있는 속도 v

제한 된 속도 내로 맞추지 못한다면 impossible을 출력한다.

 

해결방법

t1 = 포탄이 최대 높이까지 도달하는데 걸리는 시간

t2 = 포탄이 최대 높이에서 적 탱크까지 도달하는데 걸리는 시간

H = 최대 도달 높이

h = 자신의 탱크와 적의 탱크 사이의 높이 차

D = 자신의 탱크와 적의 탱크 사이의 거리 차

 

Vcos(d)(t1 + t2) + w(t1 + t2)^2 /2 = D 공식이 만족해야 함.

t1 = Vsin(d) / g

t2 = (2(H-h)/g)^0.5

H = (V sin(d))^2 / 2g

 

Free Willy

단어 두개와 몇가지 조합이 주어진다.

첫번째 단어에서 최소한의 조합을 이용해 두번째 단어를 만드는 횟수를 구하자.

만약 주어진 횟수 안에 불가능하면, whalemeat를 출력하자.

 

입력

n

N P L

W1 W2

P(0)

...

p(P)

 

n = 테스트 횟수

N = 단어 길이

P = 조합 갯수

L = 제한 횟수

P(i) = 조합

 

출력

제한 횟수보다 더 적게 맞출 수 있다면 그 횟수를 출력한다.

만약 불가능하면, whalemeat를 출력한다.