소문난 칠공주 문제 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히 현재의 체제를 포기하고, ‘소문난 칠공주’를 결성하는 것이 유일한 생존 수단임을 깨달았다. ‘소문난 칠공주’는 다음과 같은 규칙을 만족해야 한다. 이름이 이름인 만큼, 7명의 여학생들로 구성되어야 한다. 강한 결속력을 위해, 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다. 화합과 번영을 위해, 반드시 ‘이다솜파’의 학생들로만 구성될 필요는 없다. 그러나 생

다이어트 문제 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각각 합이 최소 100, 70, 90, 10가 되도록 하는 경우를 생각해보자. 이 경우 모든 재료를 선택하면 쉽게 해결되지만, 우리는 조건을 만족시키면서도 비용이 최소가 되는 선택을 하려고 한다. |재료|단백질|지방|탄수화물|비타민|가격| |---|---|---|---|---|---| |1|30|55|10|8|100| |2|60|10|10|2|70| |3|10|80|50|0|50| |4|40|30|30|8|60| |5|60|10|70|2|120| |6|20|70|50|4|40| 예를 들어, 식재료 1, 3, 5를 선택하면 영양분은 100, 145, 130, 10으로 조건을 만족하지만 가격은 270이

문제 어른 상어 코드

딸기와 토마토 문제 즈티와 레오가 사는 집 앞마당에는 $N\times M$ 크기의 작은 텃밭이 있다. 텃밭의 좌측 상단의 좌표는 $(1, 1)$이며, 우측 하단의 좌표는 $(N, M)$이다. 텅 빈 텃밭이 허전해 보인 둘은 각자 원하는 작물을 텃밭에 심고 예쁘게 키워보기로 했다. 즈티는 $K$칸 이상인 가로 또는 세로 줄 하나를 고른 후 그 줄에서 임의의 연속한 $K$개의 칸에 모두 딸기 씨앗을 심었고, 레오는 같은 방법으로 토마토 씨앗을 심었다. 텃밭을 벗어나서 씨앗을 심을 수는 없다. 텃밭의 각 칸에 종류와 상관없이 씨앗이 존재하는지가 주어질 때, 딸기와 토마토가 같이 자랄 칸의 좌표를 전부 구해보자. 단, 씨앗에서 작물이 자라지 않는 경우는 없으며, 조건에 맞는 입력만 주어진다. 입력 첫 번째 줄에 $N, M, K$가 공백으로 구분되어 주어진다. $(1 \le N,M \le 2\,000,