스터디 - 씨앗
공지 커리큘럼
씨앗 11월 10일
using namespace std;
class Step5When
{
private:
int N; // 위원회원 수
int Q; // 의사 정족수
int days[101];
public:
Step5When(void) : days() {}
int Solve(void)
{
cin >> N >> Q;
int result = 0;
int maxQ = Q;
while ( N-- )
{
int M; // 가능한 날 수
cin >> M;
while ( M-- )
{
int date;
cin >> date;
days[date]++;
if (days[date] > maxQ)
{
maxQ = days[date];
}
}
}
for (int i=1; i<=100; i++)
{
if (days[i] >= maxQ)
{
result = i;
break;
}
}
return result;
}
};
int main(void)
{
Step5When prob;
cout << prob.Solve() << endl;
return 0;
}
ICPC 위원회는 다음 대회 회의를 위하여 가능한 빨리 미팅을 가지려고 한다. 그런데 , 멤버회원들이 너무 바빠 회의날짜를 잡는 것이 쉽지 않다.
위원회는 미팅 날짜를 잡기 위해서 회원들에게 만날수 있는 날을 이메일로 부쳐줄 것을 요구했다.
당신이 해야 할 일은 이메일 리스트를 보고 가능한 많은 사람이 참여할 수 있는 날짜를 구하는 것이다.
입력
입력의 첫 줄은 두 개의 수가 주어진다.
- 첫 수 N (50 이하의 양의 정수)은 위원회원 수이고,
- 다음 Q 는 의사 정족수이다 , Q 는 N 보다 같거나 작은 양의 정수이다.
다음 N 라인의 입력 형식은
- 첫 수는 각 회원의 가능한 날 수 M ( 0 이상 양의 정수) 이 주어지고,
- 다음 M ( 1 이상 100 이하의 양의 정수) 개의 가능한 일자가 주어진다.
M Date1 Date2 ... DateM
가능한 날의 1 은 내일 , 2 는 내일의 내일 , 3 은 내일의내일의내일 , .... 을 의미한다.
날은 중복없이 오름차순으로 입력된다.
출력
가장 많은 인원이 참가할 수 있는 날을 출력한다.
단, 의사 정족수를 채울수 있는 날이 없다면 0 을 출력하고 , 답이 여러 개인 경우 빠른 날을 출력한다.
입출력 예
입력 3 2 2 1 4 0 3 3 4 8 출력 4 입력 3 2 4 1 5 8 9 3 2 5 9 5 2 4 5 7 9 출력 5 입력 3 3 2 1 4 3 2 5 9 2 2 4 출력 0 입력 3 3 2 1 2 3 1 2 9 2 2 4 출력 2
보충 설명
입력 데이터
3 2 4 1 5 8 9 3 2 5 9 5 2 4 5 7 9 1 2 3 4 5 6 7 8 9 ----------------- * * * * * * * * * * * *
5 , 9 중 빠른 날 5 가 답이다.
출처: Asia - Aizu (Japan) 2003 Preliminary
씨앗 11월 3일
생일 파티에 n 명의 참석자가 있을 때 같은 생일(같은 달,같은 일)을 가질 확률을 구하라.
일년은 365 일이라 가정하고 어떤 사람도 특정한 날을 선택해서 태어나는 경우는 없다.
입력
n 이 입력으로 주어진다.
출력
출력은 소수이하 6 자리(7자리에서 반올림)까지 출력한다.입출력 예
입력 365 출력 1.000000 입력 0 출력 0.000000 입력 23 출력 0.507297
출처:XXIII Colombian Programming Contest Warmup
int main(void)
{
int n,i;
scanf("%d",&n);
double ans=1.0;
for(i=1;i<n;++i)
ans *= (double)(365-i)/(double)365;
printf("%0.6lf\n",(double)1-(double)ans);
}
프로그램 명: profit
물건의 원가가 a 이고 , 원가에 b % 이윤을 붙여서 정가를 정했으나 물건이 잘 팔리지 않아 정가의 c% 를 할인해서 팔았다. 이 물건을 팔았을때의 이윤을 구하여라.
입력
a,b,c 가 입력으로 주어진다. (모두 자연수이고 a < 100000 , b,c < 100)
출력
이윤을 소수 첫째 자리에서 반올림하여 출력한다. 손해를 볼 경우에는 loss 를 출력한다.
입출력 예
입력 100 10 10 출력 loss 입력 100 10 8 출력 1
int main(void)
{
int a,b,c;
double aa,bb,ans;
scanf("%d %d %d",&a,&b,&c);
aa = (float)a + (float)a * ((float)b / 100);
bb = aa - ((float)aa * ((float)c / 100));
ans = bb - a;
if(ans < 0)
printf("loss\n");
else
printf("%1.0lf\n",ans);
}
씨앗 10월 6일
반 인원수와 점수가 주어질 때 반 평균 초과인 사람의 백분률을 구하는 문제이다.
백분률 = 반평균초과인사람수 / 전체인원수 * 100
입력
첫 번째 수는 반 인원 수 N 이고 , 다음 N 명의 학생의 점수가 정수로 주어진다.인원 수는 1000 이하이고 , 점수는 0 이상 100 이하이다.
출력
소수 3 자리까지(4 번째 자리에서 반올림) 출력한다.입출력 예
입력 7 100 95 90 80 70 60 50 출력 57.143%
출처: Waterloo local 2002.09.28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <stdio.h> int main(void){ int N; int* scores; int sum = 0; int cnt = 0; double avg = 0; scanf("%d", &N); scores = new int[N]; for (int i = 0; i < N; i++) { scanf("%d", &scores[i]); sum += scores[i]; } avg = sum / (double)N; for (int i = 0; i < N; i++) { if (scores[i] > avg) { cnt++; } } printf("%.3lf%%\n", cnt * 100.0 / N); delete[] scores;} |
씨앗 9월 29일
한 마리벌레가 n 인치 깊이의 우물 바닥에 있다. 벌레는 매 분당 u 인치를 오를수 있고 다시 일분을 쉬고 다시 오르고를 반복한다. 쉬는 동안은 d 인치를 미끄러진다.
이 벌레가 우물 밖으로 빠져 나오는데는 얼마나 걸릴까? 분 단위로 계산하고 바닥에서 꼭대기까지 올라오면 다 빠져 나왔다고 간주한다.
입력
여러개의 테스트 데이터가 입력으로 주어진다. 각 테스트 데이터는 3 개의 양의 정수 n,u,d 가 입력으로 주어진다. 이 변수들은 위에서 설명한 그대로 이다. ( d < u , n <100 )n 이 0 이면 입력의 끝이다.
출력
매 입력당 벌레가 우물을 빠져 나오는 필요한 분을 출력한다.입출력 예
입력 10 2 1 20 3 1 0 0 0 출력 17 19
출처: East Central North America Region 2002
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | #include <stdio.h> float solve(int n, int u, int d){ if (n <= u) { return 1; } float res = (float)(n - d) / (float)(u - d); if (res - (int)res > 0) { res = (int)res + 1; } res = res * 2 - 1; return res;} int main(void){ int n, u, d; scanf("%d %d %d", &n, &u, &d); while (n != 0) { printf("%d\n", (int)solve(n, u, d)); scanf("%d %d %d", &n, &u, &d); } } |
씨앗 9월 22일
[2014 KAIST ACM-ICPC 모의대회] Problem.A 문제 순서는 난이도 순이 아닙니다.
문제
알고리즘 문제를 푸는 프로그래밍 대회에서, 문제 순서는 난이도와 관계가 없다. 이 문제는 앞에서부터 풀다가 뒤쪽에 있는 쉬운 문제를 놓치는 팀을 막기위해 출제되었다.
프로그래밍 대회에서 N개의 문제가 출제되었을 때, 난이도는 1이상 N이하인 자연수로 결정되고, 모든 문제는 서로 다른 난이도를 가진다. 또한, 숫자가 높을수록 어려운 문제를 의미한다. 그러므로 난이도 1이면 가장 쉬운 문제, N이면 가장 어려운 문제가 된다.
k번째로 쉬운 문제가 k번째에 배치되었다면, 이것을 "난이도 순으로 배치되었다."라고 한다. 역대 대회 문제들의 난이도가 입력으로 주어진다. 각 대회에 몇 문제가 난이도 순으로 배치되었는지 세어보자.
입력
입력의 첫 줄에는 대회의 횟수를 나타내는 자연수 T가 주어지고, 두 번째 줄부터 1회 대회부터 T회 대회까지 각 대회에 대한 문제 정보가 주어진다.
각 대회에 대한 문제 정보는 두 줄로 구성된다. 첫 번째 줄에는 출제된 문제 개수 N이 주어지고, 두 번째 줄에는 첫 번째 문제부터 N번째 문제까지 각각의 난이도가 주어진다. (10 <= N <= 12)
출력
각 대회에 대해 난이도 순으로 배치된 문제의 개수를 출력한다.
예제 입력
2 12 9 11 4 2 6 3 10 8 1 12 7 5 12 1 7 9 10 2 11 6 4 3 12 5 8
예제 출력
1 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <iostream> using namespace std;#include <cstdio>#include <algorithm>#include <cstdlib>int main(void){ int n, t, su[100], test[100], cnt = 0; cin >> t; while(t --> 0) { cnt = 0; cin >> n; for(int i = 0 ; i < n ; ++i) { test[i] = i+1; } for(int i = 0 ; i < n ; ++i) { cin >> su[i]; } for(int i = 0 ; i < n ; ++i) { if(test[i] == su[i]) { ++cnt; } } cout << cnt; } return 0;} |
제 4회 KAIST ACM-ICPC 모의대회: Problem B
K모 대학의 한 교수님께서는 대회에 사용되는 M 개의 문제들이 있을 때 다음의 조건을 만족해야 '좋은 문제 집합' 이라고 정의하신다.
- 모든 참가자는 적어도 한 문제를 풀어야 한다.
- 모든 문제를 푼 참가자는 없어야 한다.
- 각 문제는 적어도 한 참가자에 의해 풀려야 한다.
경근이는 KAIST ACM-ICPC 모의대회의 검수를 하게 되었다. 그는 대회에 참가할 N 명의 참가자가 어떤 문제들을 풀지 문제들의 수준을 보고 예상 하였다. 그 예상한 결과가 실제로 이루어졌을 때 과연 문제들은 '좋은 문제 집합' 의 기준을 만족할까?
입력
첫 줄에는 테스트 케이스의 수 T 가 주어진다.
각 테스트 케이스마다 첫 번째 줄에는 참가자의 수 N(1≤N≤500) 과 문제의 수 M(1≤M≤500) 이 주어진다. 다음 N개의 줄에는 각 참가자들이 풀 수 있다고 예상된 문제들에 대한 정보들이 주어진다. 각 줄에는 i 번째 참가자가 풀 수 있다고 예상되는 문제들의 개수 X i (1≤X i ≤M) 가 먼저 주어지고 뒤이어 참가자가 풀 수 있다고 보이는 문제의 번호들을 나타내는 서로 다른 X i 개의 수가 주어진다. (모든 문제는 1,2,⋯,M 으로 숫자가 매겨진다)
출력
각 테스트케이스마다 문제 집합이 ‘좋은 문제 집합’이면 YES, 아니면 NO를 한 줄에 출력한다.
예제 입력
2
3 4
2 3 4
3 1 2 3
1 1
3 3
3 3 2 1
2 2 1
1 1
예제 출력
YES
NO
노트
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #include <stdio.h>int num[501] = {0};int main(void) { int T, N, M, P, t; int i, j, k, sw_yn; scanf("%d", &T); for(i = 0; i < T; i++) { scanf("%d %d", &N, &M); sw_yn = 0; for(j = 0; j < N; j++) { scanf("%d", &P); if(P == 0 || P == M) sw_yn = -1; for(k = 0; k < P; k++) { scanf("%d", &t); num[t] = 1; } } if(sw_yn == -1) printf("NO\n"); else { for(j = 1; j <= M; j++) { if(num[j] == 0) { sw_yn = -1; break; } } if(sw_yn == -1) printf("NO\n"); else printf("YES\n"); } for(j = 1; j <= M; j++) { num[j] = 0; } } return 0;} |
5월 4주차
입력
주어지는 수는 3 이상 40 이하의 홀수이다.출력
입출력 예
입력 5 출력 ****$ **$ $ $** $**** 입력 7 출력 ******$ ****$ **$ $ $** $**** $******
#include <stdio.h>intmain(void){intn,i,j;scanf("%d",&n);for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i+j==n+1){printf("$");}elseif( (i>j) && (i<=n/2) ){printf(" ");}elseif( (i<=j) && (i<=n/2) && (i+j<=n+1)){printf("*");}elseif( (i>=j) && (i>n/2) && (i+j<=n+1) ){printf(" ");}elseif( (i>=j) && (i>n/2) ){printf("*");}}printf("\n");}return0;}
프로그램 명: dfs제한시간: 1 초그래프의 정보(vertex 수, edge 정보)와 시작 정점의 번호가 주어질 때, 깊이우선탐색(DFS)으로 방문할 때 정점의 방문 순서를 출력하는 프로그램을 작성하시오.
입출력 예에서 주어진 그래프는 다음과 같은 형식이다.
입력 형식
입력의 첫째 줄에는 정점의 수와 시작정점의 번호가 입력되고, 다음 부터는 정점의 쌍으로 간선(edge)을 표현한다.
정점 수는 최대 10 개이고 , 1 부터 순차적으로 번호가 부여되어 있다.
입력의 끝은 EOF 이다.
출력 형식
시작정점에서 방문되는 정점번호를 출력한다. 답이 여러개 존재하는 경우 사전식 순으로 먼저 나오는 것을 출력한다.
입출력 예
입력 8 1 1 2 1 3 2 4 2 5 3 6 3 7 4 8 5 8 6 8 7 8 출력 1 2 4 8 5 6 3 7#include <stdio.h>int graph[100][100];int visit[11];int allnode;void dfs(int i);int main(void){int start,i,j,v1,v2,check;scanf("%d %d",&allnode,&start);for(i=0;i<10;++i)visit[i] = 0;while(1){check = scanf("%d %d",&v1,&v2);if(check == EOF)break;graph[v1][v2] = graph[v2][v1] = 1;}dfs(start);}void dfs(int i){int j;visit[i] = 1;printf("%d ",i);for(j=1;j<=allnode;j++)if (graph[i][j] == 1 && visit[j]==0)dfs(j);}
5월 3주차
5월 1주차는 목요일부터 시작이었고
5월 2주차는 연휴여서 모임이 없었습니다.
어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1 번부터 N번까지 번호가 매겨져 있다.
공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.
예를 들어서, 입장권에 5 번이 써 있으면 5 번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7 번 입장권을 가진 사람은 7 번 좌석은 물론이고, 6 번 좌석이나 8 번 좌석에도 앉을 수 있다. 그러나 5 번 좌석이나 9 번 좌석에는 앉을 수 없다.
그런데 이 극장에는 “고정석 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.
오늘 공연은 입장권이 매진되어 1 번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. 고정석 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.
예를 들어서, 그림과 같이 좌석이 9 개이고, 4 번 좌석과 7 번 좌석이 고정석인 경우 가능한 경우와 가능하지 않는 경우의 몇가지 예이다.
1 2 3 4 5 6 7 8 9 좌석번호1 2 3 4 5 6 7 8 9(o) 2 1 3 4 6 5 7 8 9(o) 3 1 2 4 5 6 7 8 9(x) 1 2 3 5 4 6 7 8 9(x)
입력
- 첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다.
- 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다.
- 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.
출력
주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000, 000을 넘지 않는다.
입출력 예
입력 9 2 4 7 출력 12
출처:koi 초등 기출
#include int fivo[41] = {0};void calFivo(void) { int i; fivo[0] = 1; fivo[1] = 1; for(i = 2; i < 41; i++) { fivo[i] = fivo[i-1] + fivo[i-2]; }}int main(void) { int N, M; int preBuf = 0, latBuf = 0; int i; int sum = 1; calFivo(); scanf("%d %d", &N, &M); for(i = 0; i < M; i++) { scanf("%d", &latBuf); sum *= fivo[latBuf - preBuf - 1]; preBuf = latBuf; } sum *= fivo[N - preBuf]; printf("%d", sum);}
|
씨앗 4월 3주차
Problem A. Magic Trick
| Small input 6 points |
Note: To advance to the next rounds, you will need to score 25 points. Solving just this problem will not give you enough points.
Problem
Recently you went to a magic show. You were very impressed by one of the tricks, so you decided to try to figure out the secret behind it!
The magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.
Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose. Amazing, right?
You decide to write a program to help you understand the magician's technique. The program will be given the two arrangements of the cards, and the volunteer's answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.
Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there's no card consistent with the volunteer's answers (the volunteer cheated).
Solving this problem
Usually, Google Code Jam problems have 1 Small input and 1 Large input. This problem has only 1 Small input. Once you have solved the Small input, you have finished solving this problem.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing an integer: the answer to the first question. The next 4 lines represent the first arrangement of the cards: each contains 4 integers, separated by a single space. The next line contains the answer to the second question, and the following four lines contain the second arrangement in the same format.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1).
If there is a single card the volunteer could have chosen, y should be the number on the card. If there are multiple cards the volunteer could have chosen, y should be "Bad magician!", without the quotes. If there are no cards consistent with the volunteer's answers, y should be "Volunteer cheated!", without the quotes. The text needs to be exactly right, so consider copying/pasting it from here.
Limits
1 ≤ T ≤ 100.
1 ≤ both answers ≤ 4.
Each number from 1 to 16 will appear exactly once in each arrangement.
Sample
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | #include <stdio.h>int main(void){ int card[4][4],comp[4],comp1[4],check[100]={0}; int i,j,select,test,cnt,ans,flag=0; scanf("%d",&test); while(test != 0) { scanf("%d",&select); for(i=0;i<4;++i) for(j=0;j<4;++j) scanf("%d",&card[i][j]); for(i=0;i<4;++i) comp[i] = card[select-1][i]; scanf("%d",&select); for(i=0;i<4;++i) for(j=0;j<4;++j) scanf("%d",&card[i][j]); for(i=0;i<4;++i) comp1[i] = card[select-1][i]; for(i=0,cnt=0;i<4;++i) for(j=0;j<4;++j) if(comp[i] == comp1[j]) { ans = comp[i]; ++cnt; } if(cnt==1) check[flag++] = ans; else if(cnt > 1) check[flag++] = 17; else check[flag++] = 18; --test; } for(i=0;i<flag;++i) if(check[i] < 17) printf("Case #%d: %d\n",i+1,check[i]); else if(check[i] == 17) printf("Case #%d: Bad magician!\n",i+1); else printf("Case #%d: Volunteer cheated!\n",i+1);} |
씨앗 4월 1주차
남자화장실의 소변기는 일렬로 쭉 이어져있다. 다른 사람들이 이용하는 곳을 제외하면 어느 곳에서나 볼일을 볼 수는 있지만, 옆자리에 아무도 없을 때 마음 편하게 볼일을 볼 수 있다.
예를 들어, 5개의 변기가 일렬로 서있을 때, 서로를 배려하며 마음 편하게 볼일을 볼 수 있는 최대 인원은 3명이 된다.
■□■□■하지만 몇몇 심술궂은 사람들은 다음과 같은 배치로 많은 사람들이 마음 편하게 볼일을 보지 못하도록 해버린다.
□■□□■
여러분은 변기가 N개가 있다면, 모두가 마음편히 볼 수 있는 최대 인원수와, 최소 인원수를 구하면 된다.
#include <stdio.h>int main(void){ int max, min, n; printf("입력:"); scanf("%d",&n); max=n/2+n%2; if(n%3==0) { min=n/3; } else { min=n/3 + 1; } printf("변기가 %d개 있을때\n",n); printf("최대 인원수:%d / 최소 인원수:%d", max, min); return 0;}
프로그램 명: catch_cow
농부 존의 소 중에서 한 마리가 집이 싫어 도망갔다. 그는 이 소를 즉시 잡아들이고 싶어한다.
그는 1 에서 N ( 0 <= N <= 100,000 ) 지점중에서 시작하고 소는 K ( 0 <= K <= 100,000) 번째 지점에 위치한다.
존은 두가지의 능력을 가지고 있고 이를 하는데 1 분이 걸린다.
- 걷거나 ... 현재 지점-1 혹은 현재지점+ 1
- 순간이동 ... 현재지점 * 2 배 위치로 이동
소는 존이 잡으러 오는 것을 눈치채지 못해서 다른 장소로 이동하지 않는다고 가정한다.
입력
N , K 가 입력으로 주어진다.
출력
소들을 잡는데 걸리는 최소 시간(분)을 출력한다.
입출력 예
입력 5 17 출력 4
보충 설명
10 9 18 17, which takes 4 minutes...
출처:USACO 2007 Open Silver
#include <iostream>#include <queue>using namespace std;int n = 0,k = 0;int minv = 10001;class data{public : int pos; int cnt; data(int iPos, int iCnt){ pos = iPos; cnt = iCnt; }};int main(){ int arr[100001] = {0}; data tmp(0,0); queue <data> dq; cin>>n>>k; int tPos = 0; int cnt = 0; if(k <= n){ cout<<n-k; }else{ for(int i = 0 ; i < 100001 ; i++){ arr[i] = -1; } dq.push(data(n, 0)); while(!dq.empty()){ tmp = dq.front(); dq.pop(); if(tmp.pos == k){ if(minv > tmp.cnt) minv = tmp.cnt; }else if(tmp.pos > k){ if(tmp.pos > 1) if(arr[tmp.pos -1 ] == -1 || tmp.cnt+1 < arr[tmp.pos -1 ]) { arr[tmp.pos -1 ] = tmp.cnt+1; dq.push(data(tmp.pos-1,tmp.cnt+1)); } }else if(tmp.pos < k){ if(tmp.pos*2 != 0 && tmp.pos*2 <= 100000){ if(arr[tmp.pos * 2 ] == -1 || tmp.cnt+1 < arr[tmp.pos*2 ]) { arr[tmp.pos *2 ] = tmp.cnt+1; dq.push(data(tmp.pos*2,tmp.cnt+1)); } } if(tmp.pos+1 <= 100000){ if(arr[tmp.pos +1 ] == -1 || tmp.cnt+1 < arr[tmp.pos+1 ]) { arr[tmp.pos +1 ] = tmp.cnt+1; dq.push(data(tmp.pos+1,tmp.cnt+1)); } } if(tmp.pos > 1){ if(arr[tmp.pos -1 ] == -1 || tmp.cnt+1 < arr[tmp.pos -1 ]) { arr[tmp.pos -1 ] = tmp.cnt+1; dq.push(data(tmp.pos-1,tmp.cnt+1)); } } } } cout<<minv; } return 0;}
2014 1학기 1주차 알고리즘 스터디
어떤 해 M월 어떤 주의 A1,A2,...,AN요일의 날짜의 합이 K일때, 12월 31일이 무슨 요일인지 구하는 프로그램을 작성하라.
(일요일은 0, 월요일은 1, 화요일은 2, ..., 토요일은 6)
단, 이 해는 윤년이 아니다.
예시
5월 2주의 월요일(4일),화요일(5일),토요일(9일)의 합은 18이라고 가정할 때,
5월 4일이 월요일이므로, 12월 31일은 목요일이다.
입력
- 첫 번째 줄에는 M과 N이 주어진다.
- 두 번째 줄에는 A1,A2,... 이 공백으로 구분되어 주어진다. (2≤N≤7)
- 세 번째 줄에는 K가 주어진다.
불가능한 경우는 주어지지 않는다.
출력
그 해 12월 31일이 무슨 요일인지 출력한다.
(일요일은 0, 월요일은 1, 화요일은 2, ..., 토요일은 6)
입출력 예
입력 5 3 1 2 6 18 출력 4
출제:tncks0121
#include <iostream> using namespace std; int main(){ int m,n,i,sum = 0,k,r; int sd = 0; int mon[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; int tmp= 0; cin>>m>>n; for(i= 0 ; i<n; i++){ cin>>tmp; sum += tmp; } cin>>k; sd = (k - sum) / n; //날짜 추가 값 r = mon[m] - (tmp + sd) ; for( i = m+1 ; i<= 12 ; i++) r +=mon[i]; cout<<(tmp+r)%7; return 0; }프로그램 명: josephus제한시간: 1 초카메롯 성에서는 회의가 열리고 있다. 밤마다 용이 나타나서 백성들을 괴롭히기 때문 이다.
원탁의 기사 모두가 용과 싸우고 싶어 하지만 많은 군대를 이끌고 가 면 용이 미리 알아채기 때문에 기사 한 명만이 갈 수 있다. 아더왕은 과연 누구를 보내야 하는 가 고민에 빠졌다.
그러던 중 란슬러트가 묘안을 제시하였다.
- 원탁에 둘러앉아 있는 기사 n 명에게 시계방향으로 차례대로 1 번부터 n 번의 번호를 부여한다.
- 그 중 임의의 숫자 m 을 선택하여 그 번호의 기사를 제외 시킨다
- 다음 그 기사로부터 시계 방향으로 k 번째 있는 기사를 선택하여 제외시킨다.
- 이렇게 제외된 기사로부터 k 번째 있는 기사를 제외시키는 작업을 단 한 명이 남을 때까지 계속한 뒤 그 결과 마지막으로 남은 기사가 용과 싸우러 가는 것이다.
예를 들어 n=8, m=2, k=3 인 경우 2 가 먼저 제외된 후 이어 5 번 8 번 기사가 차례대로 제외된다.
원탁의 기사의 수, 처음 선택한 기사의 번호 , 다음으로 몇 번째 기사를 제외시킬 것인가 하는 가 주어질 때 제외되는 기사들의 번호를 순서대로 출력 한다.
입력 형식
n,m,k 가 차례대로 입력된다. n , m , k 은 2 이상 1000 이하인 정수이다.출력 형식
제외되는 기사들의 번호를 제외되는 순서대로 출력한다. 마지막에 출력된 기사가 선택되는 것이다.입출력 예
입력 8 2 3 출력 2 5 8 4 1 7 3 6
권장 사항
linked list 로 구현출처:
#include <iostream>#include <string>#include <vector>usingnamespacestd;intmain(){vector<int> vt;vector<int> ::iterator it;intn,m,k;inti,j;cin>>n>>m>>k;for(i = 1; i<= n ; i++){vt.push_back(i);}m -=1;for(i = 0;!vt.empty();){if(i == m){cout<<vt[i]<<" ";vt.erase(vt.begin() + i, vt.begin()+i+1);if(vt.empty())break;m += k-1;j = vt.size();m %= j;}i++;if(i >= vt.size()) i = 0;}return0;}
프로그램 명: se(open)제한시간: 1 초1부터 순서대로 입력된 긴 숫자가 있다.
123456789101112131415161718192021...맨 왼쪽의 1을 첫 번째 자리로 시작하여, n 번째 자리에 무슨 숫자가 있는지 출력하시오.
위의 수열에서 예를 들면, 1을 첫 번째 자리로 하였을 때, n=3이면 3이고, n=25일 경우 7임을 알 수 있다.
입력
정수 n 이 입력된다. 1 <= n < 1,000,000출력
n 번째 수를 출력한다.입출력 예
입력 3 출력 3 입력 25 출력 7출처+채점데이터:20103324#include <iostream>#include <cmath>usingnamespacestd;intmain(){intn,cnt = 0,i,j;cin>>n;if(n<=9) cout<<n;else{for(i= 1,j=1; i<1000000;i++){if(i >= (int)pow(10.0,j)) j++;cnt += j;//cout<<cnt<<" "<<i<<endl;if(cnt > n){cout<<(i%(int)pow(10.0,(cnt-n+1)))/(int)pow(10.0,(cnt-n));break;}elseif(cnt == n){cout<<i%(int)pow(10.0,1);break;}}}return0;}
8주차 씨앗
정수 n 의 제곱 근을 구하는 문제이다.
입력
정수 n ( 0 <= n <2^63) 이 입력으로 주어진다.출력
q^2 >= n 을 만족하는 음이 아닌 정수 값중 최소 q 를 출력한다.입출력 예
입력 122333444455555 출력 11060446
출처:boi 2006 practice session
#include <stdio.h> #include <math.h> int main() { long long int a,b; scanf("%lld", &a); if(a==0) printf("0"); else if(sqrt((double)a) == (long long)sqrt((double)a)) printf("%lld", (long long)sqrt(a)); else printf("%lld", (long long int)sqrt(a)+1); }
프로그램 명: dcomplete제한시간: 2 초완전수란 자신을 제외한 약수의 합이 자신이 되는 수를 완전수라 한다.6 은 완전수이다. 6 의 약수는
이 중 자신을 제외한 약수의 합 1 + 2 + 3 = 6 즉 6 은 완전수이다.1 2 3 6자연수 n 을 입력으로 받아 , 1 부터 n 까지 수 중 완전수를 모두 출력하는 프로그램을 작성하시오.
입력
10000 이하의 자연수가 입력으로 주어진다.출력
완전수를 크기 순으로 한 줄에 하나씩 출력한다.입출력 예
입력 10 출력 6 입력 30 출력 6 28#include <stdio.h> int main() { int a,sum=0; int i,j; scanf("%d", &a); for(i=2 ; i<=a ; i++) { for(j=1 ; j<i ; j++) if(i%j == 0) sum += j; if(sum == i) printf("%d\n", i); sum=0; } }프로그램 명: catalan제한시간: 1 초1부터 n 까지의 정수가 차례로 스택에 push 된다.
push 가 이루어지는 중간에, 또는 모든 숫자들이 push 된 이 후에 언제든지 임의로 숫자들을 pop 할 수 있다. 이렇게 pop 된 숫자들을 차례로 나열한 수열을 catalan number 라 한다.
예를 들어, n 이 4 라면 1,2,3,4 가 차례로 push 된다. 1,2,3,4 가 모두 push 된 뒤 네 번 pop 하면 4,3,2,1 이라는 수열이 만들어 진다. 반면에 1,2 가 push 된 두 번 pop을 하고, 나머지 3,4 가 push 된 뒤 또 두 번 pop을 하면 2,1,4,3 이라는 수열이 만들어 진다.
따라서 앞서 말한대로 4,3,2,1 과 2,1,4,3 은 둘다 catalan number 이다. 하지만 이렇게 pop을 해도 3,4,1,2 이라는 수열은 만들어 질 수 없는데 따라서 이는 catalan number 가 아니다.
n 과 1부터 n 까지의 숫자로 이루어진 수열이 주어질 때 , 그 수열이 catalan number 인지 아닌지를 알아내는 프로그램을 작성하시오.
입력 형식
첫 번째 줄에 100 이하의 자연수 n 이 주어진다. 두 번 째 줄에는 1부터 n 까지의 수로 이루어진 수열이 주어진다.출력 형식
입력으로 주어진 수열이 catalan number 라면 YES ,아니면 NO를 출력한다.입출력 예
입력 4 2 1 4 3 출력 YES#include <iostream> using namespace std; #include <cstdio> #include <cstdlib> #include <stack> #include <queue> #include <cmath> int main(void) { stack <int> st; queue <int> q; int n, temp, cnt; cin >> n; for(int i = 0 ; i < n ; ++i) { cin >> temp; q.push(temp); } cnt = 1; for( ; ; ) { if(cnt == q.front()) { q.pop(); if(cnt < n) { ++cnt; } } else if(cnt < q.front()) { st.push(cnt); ++cnt; } else if(cnt > q.front()) { if(st.empty() == 0) { if(st.top() == q.front()) { st.pop(); q.pop(); } else { cout << "NO" << endl; break; } } } if(q.empty() == 1) { if(st.empty() == 1) { cout << "YES" << endl; break; } else { cout << "NO" << endl; break; } } } return 0; }
7주차 씨앗
J.P. Flathead 아저씨의 가게에 점원을 고용했는데 조금 띨띨해서 잔돈을 거슬러주는 것을 잘 하지 못한다. 구두쇠인 아저씨는 이로 인해서 손해가 나는 것을 알았다.
그래서 당신에게 손님에게 거슬러 줄 돈을 계산하는 프로그램을 만들어 달라고 부탁했다.
화폐 단위는 다음과 같다.
- quartes $0.25
- dimes $0.10
- nickels $0.05
- pennies $0.01
예를 들어, $1.24 인 경우 거슬러 줄 돈은
- 4 quarters
- 2 dimes
- 0 nickels
- 4 pennies
입력
입력으로 cents C 가 주어진다.(1 <= C <= 500)출력
아래와 같은 형식으로 출력한다.Q QUARTER(S), D DIME(S), n NICKEL(S), P PENNY(S)
Q,D,N,P 는 각각 quarter, dimes , nickels, pennys 수 이다.
입출력 예
입력 124 출력 4 QUARTER(S), 2 DIME(S), 0 NICKEL(S), 4 PENNY(S) 입력 25 출력 1 QUARTER(S), 0 DIME(S), 0 NICKEL(S), 0 PENNY(S) 입력 194 출력 7 QUARTER(S), 1 DIME(S), 1 NICKEL(S), 4 PENNY(S)
출처: Greater New York 2006
#include <stdio.h> int main() { int c; int chan[4] = {25, 10, 5, 1}; int a[4]; scanf("%d", &c); for(int i=0 ; i<4 ; i++) for(int j=1 ; ; j++ ) if(c < j*chan[i]) { a[i] = j-1; c = c- (j-1)*chan[i]; break; } printf("%d QUARTER(S), %d DIME(S), %d NICKEL(S), %d PENNY(S)", a[0], a[1], a[2], a[3]); }
프로그램 명: d_f(open)제한시간: 1 초
n 을 정수부 , α 를 소수부라 한다.
N 을 입력으로 받아 정수부와 소수부를 출력하는 프로그램을 하시오.
입력
소수 이하 2 자리수가 입력으로 주어진다.출력
한 줄에 정수부, 소수부를 출력한다. 소수부는 소수 이하 두자리까지 출력한다.입출력 예
입력 1.58 출력 1 0.58 입력 -1.58 출력 -2 0.42
#include<stdio.h> int main() { double n,j; int i; scanf("%lf", &n); if(n>0) { i = (int)n; j = n-i; printf("%d %.2lf", i, j); } else { i = (int)n-1; j = n-i; printf("%d %.2lf", i, j); } }프로그램 명: eratosthenes제한시간: 1 초n 이 입력으로 주어진다. 2 부터 n 까지의 소수(prime number)를 출력하는 문제이다.
입력
입력되는 수 n 은 2 이상 10000 이하의 자연수이다.출력
2 부터 n 까지( 2 와 n 포함 )의 모든 소수를 한 줄에 출력한다.입출력 예
입력 10 출력 2 3 5 7#include<stdio.h> int main() { double n,j; int i; scanf("%lf", &n); if(n>0) { i = (int)n; j = n-i; printf("%d %.2lf", i, j); } else { i = (int)n-1; j = n-i; printf("%d %.2lf", i, j); } }
6주차 씨앗
남자화장실의 소변기는 일렬로 쭉 이어져있다. 다른 사람들이 이용하는 곳을 제외하면 어느 곳에서나 볼일을 볼 수는 있지만, 옆자리에 아무도 없을 때 마음 편하게 볼일을 볼 수 있다.
예를 들어, 5개의 변기가 일렬로 서있을 때, 서로를 배려하며 마음 편하게 볼일을 볼 수 있는 최대 인원은 3명이 된다.
■□■□■하지만 몇몇 심술궂은 사람들은 다음과 같은 배치로 많은 사람들이 마음 편하게 볼일을 보지 못하도록 해버린다.
□■□□■여러분은 변기가 N개가 있다면, 모두가 마음편히 볼 수 있는 최대 인원수와, 최소 인원수를 구하면 된다.
입력
변기의 수 N ( 0 < N ≤ 100 ) 이 주어진다.출력
최대 인원수와 최소 인원수를 공백으로 구분하여 출력한다.입출력 예
입력 5 출력 3 2
그림 출처:www.9gag.com 출처:Fate
#include <stdio.h> int main() { int i; int n; scanf("%d", &n); printf("%d %d",(n+1)/2, (n+2)/3); }
프로그램 명: coci_note제한시간: 1 초C 장조의 음계는 8 개로 나타내어진다(c d e f g a h C). 이를 1 에서 숫자 8 로 약속을 한다.
1 에서 8 까지의 수가 임의의 순서로 한 번 나오는 수열이 주어질 때 이 수열이 오름차순(ascending)인지 내림차순(descending)인지 아니면 섞여(mix) 있는지 를 알아내는 문제이다.
입력
1 에서 8 까지의 수가 임의의 순서로 한 번 나타난다.출력
ascending , descending , mixed 중 하나를 출력한다.입출력 예
입력 1 2 3 4 5 6 7 8 출력 ascending 입력 8 7 6 5 4 3 2 1 출력 descending 입력 8 1 7 2 6 3 5 4 출력 mixed출처: coci 2009/2010 contest1 1/6#include <stdio.h> int main() { int a[8] = {1,2,3,4,5,6,7,8}; int i,count[2] = {0}; int b[8]; for(i=0 ; i<8 ; i++) scanf("%d", &b[i]); for(i=0 ; i<8 ; i++) { if(b[i] == a[i]) count[0]++; if(b[7-i] == a[i]) count[1]++; } if(count[0] == 8) printf("ascending"); else if(count[1] == 8) printf("descending"); else printf("mixed"); }프로그램 명: ft제한시간: 1 초자연수가 입력으로 주어진다. 이 수의 약수를 출력하고 , 다음 줄에는 약수의 개수 , 다음 줄에는 약수의 총합 , 다음 줄에는 약수의 곱의 일의 자리수를 출력한다.
입력
주어지는 수는 1000 이하의 자연수이다.출력
입출력 예
입력 6 출력 1 2 3 6 4 12 6#include <stdio.h> int main() { int a,i,sum=0,prod=1,count=0; scanf("%d", &a); for(i=1 ; i<=a ; i++) { if(a%i == 0) { printf("%d ", i); count++; sum += i; prod *= i; prod = prod%10; } } printf("\n%d\n%d\n%d", count, sum, prod%10); }
5주차 씨앗
두 수의 공약수가 1 만이 존재하는 수 즉 최대 공약수가 1 인 수서로 소인 예를 들면
4 와 9 , 5 와 8 , 8 과 9 ...
입력
두 수가 입력으로 주어진다. 두 수는 1000 이하의 자연수이다.출력
서로 소이면 yes 아니면 no 를 출력한다.입출력 예
입력 4 9 출력 yes 입력 4 7 출력 yes 입력 6 8 출력 no
#include <stdio.h> int main() { int i; int a,b; int x=0; scanf("%d%d", &a, &b); for(i=2 ; i<1000 ; i++) if(a%i == 0 && b%i == 0) x++; if(x==0) printf("yes"); else printf("no"); }프로그램 명: swimming제한시간: 1 초컴돌이는 월,수,금 수영을 신청했습니다.만약의 경우를 위해 수영장 가는 날인지 아닌지를 체크해 주는 프로그램을 다음과 같이 작성하기로 했습니다.
- 월요일
- 화요일
- 수요일
- 목요일
- 금요일
- 토요일
- 일요일
입력
1 에서 7 사이의 자연수가 입력으로 주어진다.출력
수영장 가는 날이면 enjoy , 아니면 oops 를 출력입출력 예
입력 1 출력 enjoy 입력 4 출력 oops#include <stdio.h> int main() { int i; scanf("%d", &i); if(i==1 || i==3 || i==5) printf("enjoy"); else printf("oops"); }
4주차 씨앗
560 * 400 밀리미터 이미지를 표준 용지( 218 * 280 mm) 로 복사하려고 한다.
이 복사기는 축소 기능이 있어 용지에 맞게 가능한 크게 복사하려고 하는 경우 50 % 축소 복사하면 된다. 물론 90 도 회전 할수도 있다.( 랜드스케이프 모드)
문제는 복사할 이미지와 복사용지가 주어질 때 이 이미지를 복사용지에 잘림이 없이 최대로 넣기 위한 위한 축소 % 를 구하는 문제이다.
입력
4 개의 정수가 입력으로 주어진다. 처음 두 수는 복사할 이미지의 크기이고 다음 두 수는 복사용지의 크기이다.출력
답은 1 에서 100% 사이의 정수이다.입출력 예
입력 560 400 218 280 출력 50% 입력 10 25 88 10 출력 100% 입력 8 13 5 1 출력 12% 입력 199 333 40 2 출력 1%
출처:Mid-Central USA 2005#include <stdio.h>프로그램 명: kangaroo
int main()
{
int a[2],b[2],c[2],d[2];
int i;
int max,min;
scanf("%d", &a[0]);
scanf("%d", &a[1]);
scanf("%d", &c[0]);
scanf("%d", &c[1]);
max = a[0];
min = a[0];
for(i=0 ; i<2 ; i++)
{
if(a[i] >= max)
max = a[i];
else
min = a[i];
}
b[0] = max;
b[1] = min;
max = c[0];
min = c[0];
for(i=0 ; i<2 ; i++)
{
if(c[i] >= max)
max = c[i];
else
min = c[i];
}
d[0] = max;
d[1] = min;
if(b[0]>=d[0] || b[1]>=d[1])
{
if((double)d[0]/b[0] >= (double)d[1]/b[1])
printf("%d%%", 100*d[1]/b[1]);
else
printf("%d%%", 100*d[0]/b[0]);
}
else
printf("100%%");
}제한시간: 1 초캥거루 세 마리가 게임을 하고 있다.
한 줄로 서서 자기가 위치한 곳의 유일한 번호를 가지고 바깥에 있는 캥거루는 두 캥거루 사이로 점프를 할 수 있다.
가장 많은 점프를 할수 있는 점프 수를 구하는게 문제이다.
입력
처음 위치한 곳의 위치가 정수 A,B,C 로 주어진다.(0 < A < B < C < 100)출력
최대 점프 수를 출력한다.입출력 예
입력 2 3 5 출력 1 입력 3 5 9 출력 3입출력 보충
첫번째 입출력 예에서
- 처음 2 , 3 , 5 에서 2 번 캥거루가 3 , 5 사이 4 로 점프할 수 있고, 그러면 3 , 4 , 5 ..... 3 , 5 번 캥거루가 더 이상 점프할 공간이 없다.
- 처음 2 , 3 , 5 에서 5 번 캥거루는 2 , 3 사이로 점프 할 수가 없다.
답은 1 출처: COCI 2008/2009 Contest1 1 #include <stdio.h> int main() { int a,b,c; int x; int i; scanf("%d%d%d", &a, &b, &c); for(i=0 ; ; i++) { if(b-a >= c-b) { if(b-1==a) break; else { c = b-1; x = b; b = c; c = x; } } else { if(c-1==b) break; else { a = c-1; x = a; a = b; b = x; } } } printf("%d", i); }
3주차 씨앗
어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 1시간에 한 블럭으로 이동하며, 물의 양은 무한하다 가정하자. 물은 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다.
당신은 댐이 터진 순간 이 마을의 지도를 받았다. 당신이 도와줘야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 물이 더 이상 진행하지 못하도록 하는 것이다.
입력
- 첫 줄에는 배열의 크기인 T(1 ≤ T ≤100)가 주어지고
- 다음 줄부터 배열의 값이 주어진다. 0은 텅 빈 길, 1은 건물이다. (물은 건물을 뒤덮지 못한다고 가정한다.)
- 그리고 그 다음 줄에는 호수의 좌표 x, y가 주어지고,
- 다음 줄에는 댐이 지어지는 시간인 K가 주어진다.
출력
지어야 하는 댐의 숫자를 출력한다. 만약, 마을이 전부 잠길 때까지 댐을 지을 수 없거나 건물에 둘러쌓여 물이 더이상 진행을 못할 경우엔 "OH, MY GOD"을 출력한다. (좋은 의미로든, 나쁜 의미로든....)입출력 예
입력 5 0 1 0 0 1 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 1 0 1 1 1 5 출력 3 입력 5 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 5 2 3 출력 2
입출력 설명
첫 번째 입력에서 (1,1) 위치에서 물이 터졌다면, 물은 시간마다 다음과 같이 진행된다. (B는 건물의 위치) 0 B 4 5 B 1 2 3 4 5 B B B 5 B 9 8 7 6 7 B 9 B 7 B 그러므로 5 시간인 세군데를 막아 물이 진행하지 못하게 하는 것이 최선이다. 그러므로 출력이 3
출처:Ceil#include <iostream>
#include <queue>
using namespace std;
class point{
public:
int x;
int y;
int n;
point (){
}
point ( int px, int py, int pn){
x = px;
y = py;
n = pn;
}
};
int main(){
int arr[101][101] = {-1};
int n ;
point d;
int dt;
queue<point> pQ;
cin>> n ;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
cin>>arr[i][j];
if(arr[i][j] == 1) arr[i][j] = -1;
}
}
cin >> d.y >> d.x;
cin >> dt;
d.n = 1;
point tmp;
pQ.push(d);
int kd = 0;
while(!pQ.empty()){
tmp = pQ.front();
pQ.pop();
arr[tmp.x][tmp.y] = tmp.n;
if((tmp.x-1) >= 1){ //상
if(arr[tmp.x-1][tmp.y] == 0){
arr[tmp.x-1][tmp.y] = -1;
pQ.push(point(tmp.x-1,tmp.y,tmp.n+1));
}
}
if((tmp.x+1) <= n){ //하
if(arr[tmp.x+1][tmp.y] == 0){
arr[tmp.x+1][tmp.y] = -1;
pQ.push(point(tmp.x+1,tmp.y,tmp.n+1));
}
}
if((tmp.y-1) >= 1){ //좌
if(arr[tmp.x][tmp.y-1] == 0){
arr[tmp.x][tmp.y-1] = -1;
pQ.push(point(tmp.x,tmp.y-1,tmp.n+1));
}
}
if((tmp.y+1) <= n){ //우
if(arr[tmp.x][tmp.y+1] == 0){
arr[tmp.x][tmp.y+1] = -1;
pQ.push(point(tmp.x,tmp.y+1,tmp.n+1));
}
}
}
int cnt = 0;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
//printf("%3d",arr[i][j]);
if(arr[i][j] == (dt+1)) cnt++;
}
//cout<<endl;
}
if(cnt == 0){
cout<<"OH, MY GOD"<<endl;
}else{
cout<<cnt<<endl;
}
return 0;
}
프로그램 명: coci_kornislav제한시간: 1 초[요약] 숫자 네개가 주어질 때 네 수의 조합으로 한 방향 90 도 꺽는 동작으로 닫힌 사각형을 만들 때 이 중 최대 면적을 구하는것이 문제이다.
예를 들어 , 1 2 3 4 가 주어진다면 최대 면적은 3 이다.
Kornislav the turtle never has anything interesting to do. Since he's going to live for three hundred years, he keeps trying to find way to kill time. This weekend he started playing "enclose the largest rectangle".To start with, Kornislav needs four positive integers. He tries to enclose a rectangle by moving in one direction, then turning 90 degrees, then walking in the new direction etc. Kornislav makes a total of three 90-degree turns and walks four segments.
When walking in some direction, the number of steps he takes must be equal to one of the four chosen integers and each integer must be used exactly once. Depending on the order in which Kornislav uses the integers, his walk will make various shapes, some of which don't contain enclosed rectangles.
Write a program that calculates the largest rectangle the turtle can enclose with its walk.
입력
The first line contains four positive integers A, B, C and D (0 < A, B, C, D < 100), the four chosen integers.출력
Output the largest area.입출력 예
input 1 2 3 4 output 3 input 4 4 3 4 output 12In the first example
one possible way for Kornislav to enclose a rectangle of area 3:
- Make 4 steps forward;
- Turn right;
- Make 1 step forward;
- Turn right;
- Make 3 steps forward;
- Turn right;
- Make 2 steps forward.
출처: coci 2008/2009 1/6
#include <stdio.h>
int main()
{
double a[4],b[4];
double max=0;
int i,j;
scanf("%lf", &a[0]);
scanf("%lf", &a[1]);
scanf("%lf", &a[2]);
scanf("%lf", &a[3]);
for(i=0 ; i<4 ; i++)
{
for(j=0 ; j<4 ; j++)
{
if(a[j] >= max)
max = a[j];
}
for(j=0 ; j<4 ; j++)
{
if(max == a[j])
{
a[j] = 0;
break;
}
}
b[i] = max;
max = 0;
}
printf("%lf", b[1]*b[3]);
}
2주차 씨앗
A와 B가 주어질 때, A 에서부터 B까지의 약수가 홀수인 수의 개수와 그 합을 구하는 문제이다.
입력
첫 줄에는 범위를 나타내는 A,B(1<=A,B<=1,000,000,000,000[1조])가 주어진다.출력
맨 첫줄에 약수가 홀수인 수의 개수와 그의 합을 출력하라. 단 합이 커질 수 있으므로 1,000,000,003(10억 3) 으로 나눈 나머지를 출력하여라.입출력 예
입력 2300 2410 출력 2 4705
출처:CONANKUN
#include <stdio.h>
#include <math.h>
int main(){
long long a,b;
long long sum = 0;
long long i;
long long ia,ib;
scanf("%lld %lld",&a,&b);
ia = (sqrt((double)a)+0.9)*10 /10; //소수점 한자리 올림
ib = sqrt((double)b);
for( i= ia; i<=ib ; i++){
sum += (i*i);
}
sum%=1000000003;
printf("%lld %lld\n",ib - ia+1,sum);
return 0;
}
프로그램 명: cantoring제한시간: 1 초n 을 입력으로 받아 아래와 같은 처리를 하는 프로그램을 작성하시오.
n 이 3 인 경우
- 입력으로 받은 n 으로 3 n 개의 - 를 그린다.
- 중간의 3 n-1 개의 - 를 모두 지운다.
- 앞 , 뒤 부분의 - 를 - 가 하나 남을 때 까지 2 번 작업을 반복한다.
123456789012345678901234567 --------------------------- --------- --------- --- --- --- --- - - - - - - - -입력
n ( 0 <= n <= 12 ) 이 입력으로 주어진다.출력
- 사이에는 공백이다.입출력 예
입력 0 출력 - 입력 1 출력 - - 입력 3 출력 - - - - - - - - 입력 2 출력 - - - -출처:Mid-Atlantic 2002#include <iostream>
#include <cmath>
using namespace std;
void devide(int low,int high,int d){
int t1, t2;
int k = 1;
if(low < high){
t1 =low + (high - low+1)/3;
t2 = t1 +(high - low+1)/3;
if(d == 2) k = 2;
devide(low,t1-1,k); //1-9
devide(t1, t2-1,2);
devide(t2, high,k);
}else if(low == high){
if(d ==2) cout<<" ";
else cout<<"-";
}
}
int main(){
int n;
cin>>n;
devide(1,(int)pow(3,(double)n) ,1);
return 0;
}
1주차 씨앗
3 을 입력으로 받으면
1 + 2 + 3 = 66 을 출력한다.
입력
1000 이하의 자연수가 입력으로 주어진다.출력
입출력 예
입력 5 출력 15
참고
누적합의 기호 시그마(sigma)는 고등학교에서 나오는 기호이지만 어렵지 않으니 이 표현을 이해 하도록 하자.
using namespace std;
int main()
{
int n;
cin>>n;
cout<<(n*(n+1))/2;
return 0;
}
프로그램 명: fibonacci
피보나치 수열은 여러분도 잘 알고 있을 것이다.
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...
이제 피보나치 수열을 이용하여 직사각형을 만드려고 한다.
만드는 방법은 조금 복잡하다. 설명을 돕기 위하여, 피보나치 수열의 집합을 F라고 하겠다.
- 처음 1cm짜리 정사각형을 붙인다.
- 만들어진 직사각형의 세로의 길이와 가로의 길이를 조사한다.
- 만약 세로의 길이가 Fi와 같을 경우 Fi㎝를 한 변의 길이로 하는 정사각형을 세로의 변에 붙인다.
- 만약 가로의 길이가 Fi와 같을 경우 Fi㎝를 한 변의 길이로 하는 정사각형을 가로의 변에 붙인다.
- 세로의 길이와 가로의 길이가 같을 경우, 세로를 우선으로 한다.
- 이 조건에서 벗어나는 경우는 없다.
- 2번 과정을 반복한다.
F₁~ Fn 까지의 피보나치 수열을 가지고 직사각형을 만들었을 때, 이 직사각형의 세로와 가로 길이를 구하라.
입력
여러 개의 테스트 데이터가 한꺼번에 입력된다. 테스트 데이터의 개수는 주어지지 않으며, 피보나치 수들의 개수 n (1＜n≤40) 이 입력된다. n이 2 미만일 경우, 프로그램을 종료한다.
출력
"Case #N:"를 출력하고 개행을 한 뒤, 케이스별 세로와 가로 길이를 콤마와 공백으로 (", ") 구분하여 출력하고 2번 개행한다.
입출력 예
입력 6 2 4 3 -2 출력 Case #1: 13, 8 Case #2: 2, 1 Case #3: 5, 3 Case #4: 2, 3
출처+채점데이터:tncks0121(박수찬) 그림참조:http://upload.wikimedia.org/wikipedia/commons/8/83/FibonacciBlocks.png
#include <math.h>
using namespace std;
int main(){
for(int i =1;;i++)
{
int n, n1 = 1,n2 = 1, tmp = 0;
cin>>n;
if(n<2) break;
for(int j = 2; j<n;j++)
{
tmp = n1+n2;
n1 = n2;
n2 = tmp;
}
printf("Case #%d:\n",i);
if(n%2) printf("%d, %d\n\n",n2,n2+n1);
else printf("%d, %d\n\n",n1+n2,n2);
}
return 0;
}
프로그램 명: koi_watch
KOI 전자에서는 건강에 좋고 맛있는 훈제오리구이 요리를 간편하게 만드는 인공지능 오븐을 개발하려고 한다. 인공지능 오븐을 사용하는 방법은 적당한 양의 오리 훈제 재료를 인공지능 오븐에 넣으면 된다. 그러면 인공지능 오븐은 오븐구이가 끝나는 시간을 초 단위로 자동적으로 계산한다.
또한, KOI 전자의 인공지능 오븐 앞면에는 사용자에게 훈제오리구이 요리가 끝나는 시각을 알려 주는 디지털 시계가 있다.
훈제오리구이를 시작하는 시각과 오븐구이를 하는 데 필요한 시간이 초 단위로 주어졌을 때, 오븐구이가 끝나는 시각을 계산하는 프로그램을 작성하시오.
입력
- 첫 째 줄에는 현재 시각이 나온다.
- 시 A (0 <= A <= 23)
- 분 B ( 0 <= B <= 59)
- 초 C ( 0 <= C <= 59)
- 두 번째 줄에는 요리하는 데 필요한 시간 D ( 0 <= D <= 500 000)가 초 단위로 주어진다.
출력
첫째 줄에 종료되는 시각의 시, 분, 초을 공백을 사이에 두고 출력한다. (단, 시는 0부터 23까지의 정수이며, 분, 초는 0부터 59까지의 정수이다. 디지털 시계는 23시 59분 59초에서 1초가 지나면 0시 0분 0초가 된다.)
입출력 예
입력 14 30 0 200 출력 14 33 20 입력 17 40 45 6015 출력 19 21 0 입력 23 48 59 2515 출력 0 30 54
출처:2012 지역 본선 중등 1/5
#include <iostream>
#include <math.h>
using namespace std;
int main(){
int h,m,s;
int n;
cin>>h>>m>>s;
cin>>n;
s =(s + (n%3600)%60);
m = (m + (n%3600)/60) + s/60;
h = h + (n/3600) + m/60;
cout<<h%24<<" ";
cout<<m%60<<" ";
cout<<s%60 <<" ";
return 0;
}
5월 3주차 강의
C 기초입니다.
5월 2주차 알고리즘
어떤 커피 캔 속에 검은 콩과 하얀 콩이 섞여 들어가 있다. 그리고 당신에게는 무한 개의 검은 콩이 주어져 있다.
당신은 캔에 콩이 하나가 남을 때까지 다음 과정을 반복한다.(최종적으로 하나의 콩이 남는다는 것은 보장된다.)
- 캔에서 콩 두개를 아무렇게나 집는다.
- 두 콩의 색이 같으면, 둘 다 캔에서 빼내고 별도로 검은 콩 하나를 캔에 넣는다. 두 콩의 색이 다르면, 하얀 콩은 다시 캔에 넣고 검은 콩만 빼낸다.
입력
캔에 든 검은 콩의 개수와 하얀 콩의 개수가 순차적으로 주어진다. 각 콩의 개수는 2^31-1 이하이다.출력
최종적으로 남은 콩의 색깔이 하얀색이면 white, 검은색이면 black을 출력한다.int main()
{
int a,b;
scanf("%d%d",&a,&b);
if(b%2==0) printf("black");
else printf("white");
return 0;
}