http://codeforces.com/contest/821/problem/E E. Okabe and El Psy Kongrootime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOkabe likes to take walks but knows that spies from the Organization could be anywhere; that's why he wants to know how many different walks he can take in his city safely. Okabe's city can be represented as all points (x, y)..

http://codeforces.com/contest/821/problem/C C. Okabe and Boxestime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOkabe and Super Hacker Daru are stacking and removing boxes. There are n boxes numbered from 1 to n. Initially there are no boxes on the stack.Okabe, being a control freak, gives Daru 2n commands: n of which are to add a box to the to..

http://codeforces.com/contest/821/problem/B B. Okabe and Banana Treestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputOkabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.Consider the point (x, y) in the 2D plane such that x and y are integers and 0 ≤ x, y. There is a tr..

동기모임 봄철을 맞아 종현이는 동기들과 동기모임을 진행하려고 한다. N명의 동기들은 “S로” 라는 일직선 대로위에 거주하고 있다. 따라서 모임장소도 “S로”중 한군데에서 만나려고 한다. 동기들은 각각 이동할 수 있는 최대속도가 주어지며 동기들은 한번 출발하면 일정한 속도와 일정한 방향으로 목적지를 향해 이동한다. 종현이는 동기모임을 빨리 진행하고 싶기 때문에 최대한 빠른시간에 모든 동기들이 모일 수 있는 장소를 결정하고 싶다. “S”로를 수평선이라 가정했을 때 가장 빠른시간에 동기모임을 할 수 있는 시간을 출력하는 프로그램을 작성하시오. [제한사항] 1. 각 동기들은 한번 출발하면 일정한 방향과 속도로 목적지 까지 이동한다. 즉, 방향이나 속도를 변화시킬 수 없다. 2. 각 동기들의 처음 위치와 최대 속..

지뢰 설치 이등병 종현이는 지뢰를 설치하는 임무를 부여받고 외나무다리에 K개의 지뢰를 설치하려 한다. 외나무다리의 각 지점은 1번부터 차례대로 N번까지 번호가 매겨져 있고, 최초 지뢰는 아무곳에나 설치하여도 상관없다. 다만 각 지점사이의 외나무다리의 상태나 주위 환경이 다르기 때문에 이동할때 드는 피로도가 출발지와 목적지에 따라 천차만별이다. a에서 b지점으로 이동할 때의 피로도와 b지점에서 a지점으로 이동할 때의 피로도가 다른 경우도 존재하며, 심지어 아예 이동이 불가능한 경로도 있다. 또한 외나무다리에 지뢰를 설치하기 때문에 한번 지뢰가 설치된 곳을 지나서 이동하는 것은 불가하다. 종현이가 느끼는 피로도를 최소로 하여 K개의 지뢰를 설치하는 방법을 찾는 프로그램을 작성하자. 단, K개의 지뢰를 설치하..

업그레이드 평소 게임을 즐겨하는 종현이는 이번에 자신이 하던 게임에 “아이템 업그레이드” 시스템이 도입되어 이를 이용해 보려 한다. 종현이는 N개의 서로 다른 아이템을 가지고 있고, 이 아이템들은 모두 1부터 M단계까지의 등급이 존재한다. 아이템을 업그레이드에 필요한 강화석을 한 개 사용하면 아이템의 등급이 1만큼 증가한다. 즉, i등급의 아이템에 강화석을 한 개 이용하여 업그레이드하면 i+1등급이 된다. 강화석을 사용하면 아이템은 무조건 업그레이드가 되지만, 만약 어떤 아이템이 M등급이라면 이미 최고 등급이기 때문에 더 이상 강화석을 사용할 수 없다. 종현이는 최대 M등급까지 존재하는 서로 다른 N개의 1등급 아이템을 가지고 있을 때, K개의 강화석을 모두 사용하여 만들 수 있는 아이템 등급의 경우는 ..

http://codeforces.com/contest/816/problem/D a_1부터 a_N까지 N개의 수열이 있을 때, b_1 = a_1 + a_2, b_2 = a_2 - a_3 ... 이런 식으로 그 다음 줄에 b_n을 만든다. 같은 과정을 반복하여 수열의 수가 1개가 될 때 까지 진행했을 때 나오는 수가 뭔지 구하는 문제이다. (말보다는 그림이 이해하기 편하니 아래그림 참조) 첫번째 줄 부터 계산하다 보면 4번째 줄에 와서 규칙성을 찾을 수 있는데, 바로 이항계수이다. 구체적으로 말하면, 1번째 수열들을라 하면, 5번째 줄에 나타나는 수열들은 형태를 띈다. 즉, 첫 번째 줄에 있는 수열을 라 하면, 4줄 아래있는 5번째 줄에 나타나는 수열은 이 되고, 다시 4줄 아래에 있는 9번째 줄에 나타나는..

유적지 여행 유근이는 N개의 도시와 M개의 도로로 연결된 유적지를 여행하려고 한다. 유근이는 사실 도시를 방문하는 것 보다 드라이브하는 것에 더 관심이 많아서 N개의 도시를 모두 방문하지 못하더라도 M개의 도로를 모두 지나가길 원한다. 다만 유근이는 M개의 도로 중 2개의 도로는 한번씩만 지나고, 나머지 M-2개의 도로는 정확히 2번씩 방문하는 여행루트를 만들려 한다. 도로로 연결되어있지 않은 곳은 서로 이동할 수 없기 때문에 한 번 여행을 시작하면 시작점과 연결된 도시들만 여행할 수 있다. 또한 여행 루트에서 출발지와 목적지 도시는 중요하지 않고, 어떤 도로를 한번씩만 지나는지, 어떤 도로를 두 번씩 지나는지에 따라 각기 다른 루트로 간주한다고 한다. 유근이가 모든 M개의 도로를 여행할 수 있는 여행루..

http://hongjun7.tistory.com/64

http://codeforces.com/contest/791/problem/B 임의의 세점 X,Y,Z에 대해 X-Y && Y-Z 이면 X-Z를 만족하는가를 묻는 문제이다. 한점 X와 연결되어있는 Xi 들은 모두 서로 연결되어있어야 한다는 것을 알 수 있고, 따라서 임의의 점 X를 잡고 그것과 연결된 노드들 X1 ~ Xk 의 개수를 k라 하면 X에 연결된 노드 개수와 X1~Xk에 연결된 노드 개수들의 합이 k*(k-1)인지를 확인하면 된다. 주의할 점은for(int i=1;i