충북대학교 개신문화관에서 전국대회 개최.
전국에서 선발된 367명(초등부102명 중등부134명 고등부131명) 열띤 경합중!
http://www.ajunews.com/kor/view.jsp?newsId=20130801000585
http://www.boannews.com/media/view.asp?idx=37186&kind=1
작년에 이어 다시 저기 어딘가에...
보이긴 하는데... 뒷통수만 봐도 알겟는데... 맘으로만 응원할 수밖에...
더운 날 애쓰네. 4시간 4문항. 곧 끝나겟네.
실시간 타전된 알림은 1번 70점, 2번 100점, 3번 4번은 진행 중????
(올해는 시험장에서 제출된 답안에 대한 문항별 채점이 실시간으로 띄워짐으로
바깥에서 대기하는 부모들의 눈망울은 주식 시황판을 바라보는 심정일 터)
참고로 이 아이들이 풀고 있는 문제가 이렇다
제30회 KOI 지역본선 고등부 문제
회전 초밥
회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.
9 7 30
7 2
25 9 7
새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.
1. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 4개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
2. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.
위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.
회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최대값을 구하는 프로그램을 작성하시오.
실행 파일의 이름은 FISH.EXE로 하고, 프로그램의 실행시간은 1초를 넘을 수 없다. 부분 점수는 없다.
입력 형식
입력 파일의 이름은 INPUT.TXT로 한다. 입력의 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k,쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다.
두 번째 줄부터개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d이하의 정수가 각 줄마다 하나씩 주어진다.
출력 형식
출력 파일의 이름은 OUTPUT.TXT로 한다. 주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의최대값을 하나의 정수로 출력한다.
입력과 출력의 예 (1)
입력 (INPUT.TXT)
8 30 4 30
7
9
7
30
2
7
9
25
|
출력 (OUTPUT.TXT)
5
|
입력과 출력의 예 (2)
입력 (INPUT.TXT)
8 50 4 7
2
7
9
25
7
9
7
30
|
출력 (OUTPUT.TXT)
4
|
위 문제들에 대한 답안은 아니지만 위 문제들의 답안 형식은 대략 아래와 같은
형식의 컴퓨터 언어로 구현된다.
문제를 풀었더라도 입력 후 출력까지의 제한시간을
초과하면(타임오버) 0점 처리됨으로 최상의 결과물을 만들지 않으면 안되는
고도의 사고력과 창의력이 요구되는 전문영역이다.
#include
void clear(char q[][101]){
int i,j;
for(i=0;i<100 i="" span="">
{
for(j=0;j<100 j="" span="">
q[i][j]=0;
}
}
bool d2comp(char a1[][101],char a2[][101],int n1,int n2)
{
int i,j;
for(i=0;i
{
for(j=0;j
{
if(a1[i][j] != a2[i][j])
return 0;
}
}
return 1;
}
bool prev(int array[][2],int a, int b,int n)
{
int i;
for(i=0;i
{
if(array[i][0]==a && array[i][1]==b)
return 0;
}
return 1;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int i,j,k,l,n,m,pn,pm,res=0;
char s[101][101]={0},p[101][101]={0},w[101][101]={0},h[101][101]={0},wh[101][101]={0},temp[101][101]={0};
int chk[10000][2]={0};
scanf("%d %d",&n,&m);
for(i=0;i
scanf("%s",s[i]);
scanf("%d %d",&pn,&pm);
for(i=0;i
scanf("%s",p[i]);
for(i=0;i
{
for(j=0;j
w[i][j]=p[i][pm-j-1];
}
for(i=0;i
{
for(j=0;j
h[i][j]=p[pn-i-1][j];
}
for(i=0;i
{
for(j=0;j
wh[i][j]=p[pn-i-1][pm-j-1];
}
for(i=0;i
{
for(j=0;j
{
clear(temp);
for(k=0;k
{
for(l=0;l
temp[k][l]=s[i+k][j+l];
}
if((d2comp(temp,p,pn,pm) || d2comp(temp,w,pn,pm) || d2comp(temp,h,pn,pm) || d2comp(temp,wh,pn,pm)) && prev(chk,i+pn,j+pm,res))
{
chk[res][0]=i+pn;
chk[res][1]=j+pm;
res++;
}
}
}
clear(temp);
for(i=0;i
{
for(j=0;j
{
clear(temp);
for(k=0;k
{
for(l=0;l
temp[k][l]=s[i+l][j+k];
}
if((d2comp(temp,p,pn,pm) || d2comp(temp,w,pn,pm) || d2comp(temp,h,pn,pm) || d2comp(temp,wh,pn,pm)) && prev(chk,i+pn,j+pm,res))
{
chk[res][0]=i+pn;
chk[res][1]=j+pm;
res++;
}
}
}
printf("%d",res);
return 0;
}
알고리즘 프로그래밍이 생소한 이들은 문제를 해석하는 일조차 난감^^;;