예전에 저의 멘탈을 파괴햇던 문제 하나 질문 더 할게여 ㅠ

  • yeonzzg
    yeonzzg

    문제링크:
    http://acm.timus.ru/problem.aspx?space=1&num=1914

    해석:
    n개의 반지가 두줄로 나열되어있습니다. 윗 줄의 i번째를 한바퀴 돌리면 아랫줄의 1~n까지가 어떤 비율로 따라 돌아가는지 입력으로 주어집니다. 윗 줄의 반지중 최소 하나를 정수바퀴가 아니게 돌리면서 아랫줄의 모든 반지는 정수바퀴가 돌도록 하는 방법이 있는지 없는지 조사하세요. (n<=100)

    k=1~100까지 1/k바퀴 돌리는걸 1~n번마다 한번만 돌려놓고 그 이후는 선형방정식을 세워서 가우스 소거로 풀어볼려했는데.. 12번 데이터를 절대 못넘어가더군요.. 가우스 소거를 좀 특이하게 나머지 가지고 돌려봤는데 전혀 해결이 안됐습니다..

    yes no 찍는게 왠지 2sat같기도 한데 논리식으로 세워보자니 전혀 떠오르는거 하나 없네요.. 도와주세요!


    11년 전
9개의 댓글이 있습니다.
  • Being
    Being

    1/100이 아니라 1부터 100까지의 최소공배수 단위로 돌려야겠네요. 무지 크겠죠? 윗줄의 각 반지에 대해서 한 바퀴 이상씩 돌리는 건 의미가 없으니 [0,1) 바퀴씩 돌려서 nontrivial solution이 존재하냐는 문제일텐데요. 최소공배수 K로 뻥튀기해서 mod K인 정수 합동방정식 시스템을 만들면, N개의 합동식과 N개의 변수로 구성된 시스템이 되는데 이 시스템이 넌트리비얼 솔루션을 가지는지 알려면 싱귤러인지 아닌지만 알면 될 것 같습니다. 단지 저 최소공배수 K가 무지 커서 어떨지 모르겠네요.


    11년 전 link
  • yeonzzg
    yeonzzg

    그러고보니 최소공배수로 돌려야 모든 경우가 다 커버되겠네요. 근데 대략만 계산해보면 최소공배수가 100^100정도가 되버려서..ㅠ double로 mod K 선형방정식을 돌려봤자 오차가 너무 크게 날거같네요 ㅠ 빅인트를 써야하나.. 그리고 nontrivial인지 체크하는데 싱귤러인지의 여부가 무슨 의미인지 모르겠어요. 선대 들은지 너무 오래되서 ㅠㅠ nontrivial인지 체크하려면 가우스 소거 후에 남은 수식의 개수랑 변수의 개수를 비교해보면 되는것 아니었나요?


    11년 전 link
  • Being
    Being

    네 스퀘어 매트릭스니 싱귤러이면 소거해서 빈 행이 남아 있겠죠. 다 동치입니다.


    11년 전 link
  • Being
    Being

    생각해보니 K가 소수가 아니라서, 나눗셈은 못 하겠네요. --;;;; 나눗셈 없이 디터미넌트를 구하는 방법이 있기는 한데 이게 의도일진 모르겠네요.


    11년 전 link
  • yeonzzg
    yeonzzg

    음.. 결국 시간복잡도 때문에 LU decomposition 해서 det을 구해야될꺼같은데 LU decomposition 과정은 전혀 기억도 안나고 짜본적도 없네요..... ㅠㅠ


    11년 전 link
  • yeonzzg
    yeonzzg

    아 그보단 디컴포지션 과정에도 나눗셈이 있네요.. 나눗셈 없이 det을 어케 구하나요? ㅠㅠ


    11년 전 link
  • Being
    Being

    찾아보시면 방법이 있기는 한데, 한편으로는 그냥 실수로 두고 계산해도 되지 않을까 싶습니다. 디터미넌트는 어느 정도 랜덤한 값이라 우연히 0에 가깝게 되기는 쉽지 않을 것 같은데요 흠...


    11년 전 link
  • yeonzzg
    yeonzzg

    실수로 계산해봤는데 오번데이터에서 틀리네요 ㅠ 코딩이 잘못된건가 ㅠ


    11년 전 link
  • Being
    Being

    ㅠㅠ


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.