글 읽기 - 1089 엘리베이터 문제 어디서 틀렸는지 모르겠습니다

martinok1103 3년 전 0

우선 오버플로우로 인한 틀린 것은 아닌 것 같습니다 (모두 공백으로 한 경우 49...9.5가 잘 나옵니다)

-1이 나오는 경우의수 ( (1, 1), (3, 1)자리에 LED가 켜진 경우, 4n+3(n>=0) 자리에 불이 켜진 경우)는 모두 전처리 하였습니다

각각의 숫자들별로 가능한 숫자들을 모두 구조체 내부의 배열에 저장해 놓고 계산을 진행합니다.

어떤 테스트케이스에서 오류가 발생했는지 찾아주시면 감사하겠습니다

#include<cstdio>
typedef long long int lint;

int n;
char led[6][36];
typedef struct ledinfo {
    int ons[6][4];
    lint cnt;
    int avail[11];
} LEDI;

LEDI leds[11];
lint sum;

lint ten(int dig) {
    switch(dig) {
        case 1:
            return 1L;
        case 2:
            return 10L;
        case 3:
            return 100L;
        case 4:
            return 1000L;
        case 5:
            return 10000L;
        case 6:
            return 100000L;
        case 7:
            return 1000000L;
        case 8:
            return 10000000L;
        case 9:
            return 100000000L;
        case 10:
            return 1000000000L;
        default:
            return 0L;
    }
}


int main()
{
    scanf("%d",&n);
    for(int i=0 ; i<5 ; i++) {
        scanf(" %s",led[i]);
    }
    for(int i=0 ; i<5 ; i++) {
        for(int j=0 ; j<4*n-1 ; j++) {
            if(j%4==3) {
                if(led[i][j] == '#') {
                    printf("-1");
                    return 0;
                }
                continue;
            }
            leds[j/4].ons[i][j%4] = (led[i][j]=='#'?1:0);
            if(i%2==1 && j%2==1 && led[i][j]=='#') {
                printf("-1");
                return 0;
            }
        }
    }
    for(int i=0 ; i<n ; i++) {
        if (leds[i].ons[1][1] + leds[i].ons[2][1] + leds[i].ons[3][1] == 0) {
            leds[i].avail[0] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[0][0] + leds[i].ons[0][1] + leds[i].ons[1][0] + leds[i].ons[1][1] +
            leds[i].ons[2][0] + leds[i].ons[2][1] + leds[i].ons[3][0] + leds[i].ons[3][1] +
            leds[i].ons[4][0] + leds[i].ons[4][1] == 0) {
            leds[i].avail[1] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[1][0] + leds[i].ons[1][1] + leds[i].ons[3][1] + leds[i].ons[3][2] == 0) {
            leds[i].avail[2] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[1][0] + leds[i].ons[1][1] + leds[i].ons[3][0] + leds[i].ons[3][1] == 0) {
            leds[i].avail[3] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[0][1] + leds[i].ons[1][1] + leds[i].ons[3][0] + leds[i].ons[3][1] +
            leds[i].ons[4][0] + leds[i].ons[4][1] == 0) {
            leds[i].avail[4] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[1][1] + leds[i].ons[1][2] + leds[i].ons[3][0] + leds[i].ons[3][1] == 0) {
            leds[i].avail[5] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[1][1] + leds[i].ons[1][2] + leds[i].ons[3][1] == 0) {
            leds[i].avail[6] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[1][0] + leds[i].ons[1][1] + leds[i].ons[2][0] + leds[i].ons[2][1] +
            leds[i].ons[3][0] + leds[i].ons[3][1] + leds[i].ons[4][0] + leds[i].ons[4][1] == 0) {
            leds[i].avail[7] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[1][1] + leds[i].ons[3][1] == 0) {
            leds[i].avail[8] = 1;
            leds[i].cnt++;
        }
        if (leds[i].ons[1][1] + leds[i].ons[3][0] + leds[i].ons[3][1] == 0) {
            leds[i].avail[9] = 1;
            leds[i].cnt++;
        }
    }
    lint tcase = 1;
    for(int i=0 ; i<n ; i++) tcase *= leds[i].cnt;
    for(int i=0 ; i<n ; i++) {
        lint ocase = 1;
        for(int j=0 ; j<n ; j++) {
            if(i==j) continue;
            ocase *= leds[i].cnt;
        }
        lint tsum = 0;
        for(int j=0 ; j<10 ; j++) {
            tsum += j*leds[i].avail[j]*ten(n-i);
        }
        sum += (tsum*ocase);
    }
    printf("%.5lf",(double)sum/tcase);
}

surung9898 3년 전 1

반례는 다음과 같았습니다.

/*
2
###.#..
#.#....
.#....#
....#.#
###..##

sample answer: 89.6666667
output: 63.66667

possible number: 80, 86, 88, 90, 96, 98

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1089 엘리베이터 문제 어디서 틀렸는지 모르겠습니다

martinok1103 3년 전 0

surung9898 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말