안녕하세요. 현재 외국에서 대학 다니고 있는 학생입니다. 자바 알고리즘 수업 처음 듣고 있는데 교수가 말도 안되는 숙제를 내줬습니다. 1주일동안 풀려고 끙끙 앓고 있다가 숙제 내야하는 기간이 20시간도 안남았는데 도저히 답이 안보여서 혹시 도움 받을 수 있을까 해서 여기에 글 올립니다. 문제에 따른 코딩 해주시는 분께는 제가 바로 20만원 계좌이체 해드리겠습니다. 


문제: 간호사 시프트를 정하려고 하는데 한명의 간호사는 한타임에 꼭 들어가야한다. 첫번째 line에 있는 숫자 N은 간호사 숫자를 뜻한다. 두번쨰 줄에 있는 알파벳과 숫자는 알파벳은 간호사 이름을 뜻하고 숫자는 그 간호사가 일할 수 있는 타임의 갯수를 뜻한다. 세번째 라인은 그 간호사가 일할 수 있는 시간대를 말한다. 예를 들면 첫번째 input을 보면 간호사 숫자는 2명이며, A 간호사는 2타임 중 하나를 들어갈 수 있는데, 0시와 1시이다. B 간호사는 한타임만 일할 수 있으며 0시밖에 일하지 못한다. 그랬을 때 output은 A간호사는 1시에 일해야하면 B 간호사는 0시에 일해야한다 입니다. 꼭 문제를 풀때 Recursion을 써서 풀어야한다고 합니다ㅠㅠㅠ. 


바로 밑에 수도code도 첨부하겠습니다. 

solve(Nurses) Check if all nurses are assigned a shift, if so, then return success Let N be a nurse without a shift for each shift s if N can do s, and no one else is assigned s, then Assign N to s if solve(Nurses) is success then return success return "impossible"

제발 도와주세요ㅠㅠㅠㅠㅠ


input

2 A 2 0 1 B 1 0outputA 1 B 0

input

2 A 1 0 B 1 0

output

impossible

input

3 A 1 1 B 2 1 2 C 2 0 2

output

A 1 B 2 C 0

input

8 A 2 0 4 B 4 0 2 5 7 C 3 1 4 6 D 3 1 2 4 E 2 4 6 F 2 2 7 G 1 0 H 3 1 3 5

output

A 4

B 5 C 1 D 2 E 6 F 7 G 0 H 3