글 읽기 - 반례 부탁드립니다.

ujoon 1년 전 0

해설은 O(n⁵)의 시간 복잡도를 가진 네트워크 뭐시기를 이용하라 하지만 오기가 나서 점수 계산으로 때리는 중입니다. ~~어케든 반례들 돌려막기 하면 되겠다는 마인드로다가 하고 있죠~~ 예제는 잘 돌아가지만 실제 제출시에는 50%에서 틀렸습니다가 나옵니다. 반례 부탁드리겠습니다. (이 방법이라면 시간복잡도가 O(테스트케이스 수 + ?n)정도라 필요없는거 덕지덕지...)

for _ in range(int(input())):
    n=int(input())
    winner=[]
    player_score=[]
    if_player_score=[]
    for i in range(n):
        player_fight=input()
        player_score.append(player_fight.count('1')+player_fight.count('d')*0.5)
        if_player_score.append(player_fight.count('1')+player_fight.count('d')*0.5+player_fight.count('.'))
    max_player_score=max(max(player_score),max(if_player_score))
    for i in range(n):
        if player_score[i]==max_player_score or if_player_score[i]==max_player_score:
            winner.append(i+1)
    print(*winner)

flakepowders 1년 전 1

input

1
5
x11..
0x...
0.x..
...x.
....x

wrong answer

1 4 5

output

1 2 3 4 5

ujoon 1년 전 0

감사합니다!

ujoon 1년 전 0

근데 질문 있습니다. 제가 문제를 잘 이해 못한 것일 수도 있겠지만 혹시 실례가 아니라면 output이 1,2,3,4,5가 나오는 이유를 들을 수 있을까요?

flakepowders 1년 전 1

저 시점에서는 5명 모두 남은 경기를 모두 이긴다면 승리가 가능합니다. 2나 3이 이기려면 1이 남은 2경기에 모두 지면 됩니다.

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

문제

문제

출처

ICPC

반례 부탁드립니다.

ujoon 1년 전 0

flakepowders 1년 전 1

ujoon 1년 전 0

ujoon 1년 전 0

flakepowders 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말