예비소집 MM 어떻게 푸셨나요 'ㅅ'?

  • Taeyoon_Lee
    Taeyoon_Lee

    예비소집 MM 어떻게들 푸셨나요??

    오후 2시에 끝인 줄 알았는데, 지금 보니 이미 끝나고 채점 중... -_-;;

    저의 접근 방법을 소개하겠습니다... 아마도 9000점 이상은 다 저랑 비슷하실 것 같네요...

    1. 보라돌이, 뚜비, 나나가 주는 점수가 평균적으로 많이 올라가는 숫자를 찾아 봅니다. (나중에 곱해지는 상수는 일단 무시하고요.)
    2. 찾아보니 49000000...나 250000000... 같은 수가 나오네요. Example을 돌려 봅니다.
    3. 테스트 결과를 보니, 보라돌이 점수가 거의 항상 뚜비와 나나 점수보다 낮아요. 그러니까 최대한 제곱수의 개수를 늘려야 한다는 결론이 나오네요.
    4. 제곱수의 개수를 최대한 늘리도록 백트래킹을 돌립니다. 대략 30자리 이내 수들만 돌려보았습니다.
    5. 143451562500000000000 같은 수가 나옵니다. 제출해보니, 점수가 꽤 좋습니다. (1434515625 뒤에 0만 붙여서 제출해도 9500점 이상일 듯)
    6. 그런데 테스트 결과를 보면, 여전히 보라돌이 점수가 뚜비와 나나보다 낮아요. 그러니까 한정된 길이 n 내에 제곱수를 더 끼워 넣어야 kriii군을 따라잡을 수 있다는 거죠!
    7. 왜 그럴까 곰곰이 따져 봤는데... 1434515625에는 무려 7개의 제곱수가 suffix로 붙어 있어요. 25, 625, 5625 ... 그리고 이 숫자에 00이 붙으면 제곱수의 개수가 7개씩 늘어나요. 2500, 62500, 562500 ... 전부 새로운 제곱수가 되죠. 그래서 이 숫자에 0만 계속 붙이면 제곱수의 개수도 늘어나고, 제곱수들의 길이도 늘어나고, 새로운 제곱수도 늘어납니다. 그래서 전반적으로 점수가 좋아져요.
    8. ㅇㅋ 그럼 이제 suffix로 제곱수가 많이 붙어 있는 숫자를 더 찾아봅시다!
    9. 금방 또 나왔습니다. 230861434515625! 무려 8개의 제곱수가 suffix로 붙어 있어요. 여기에 00을 붙이면, 새로운 제곱수가 8개씩 늘어나요!
    10. 9개의 제곱수가 suffix인 숫자를 찾아봅시다!!!
    11. 그리고 대회가 끝났습니다. 9개 짜리는 못 찾았어요. :'(

    이런 스탭을 밟았습니다.

    ipkn님과 blmarket님과 kriii군도 아마 결론적으론 비슷한 방식이 아닐까 싶은데, 어떻게 푸셨는지 궁금하네요! 그리고 9개의 제곱수가 suffix인 수.... 혹시 찾으셨나요?!

    P.S. 1434515625는 진짜 마법의 숫자인 듯. 이거에 0붙인 답을 넘기가 웬만해선 힘들고, 심지어 230861434515625에도 1434515625가 숨어(?)있다능...


    12년 전
11개의 댓글이 있습니다.
  • kriii
    kriii

    글보고 세어봤더니

    607204292297119140625
    suffix가 10개네요 ㅋㅋ


    12년 전 link
  • kriii
    kriii

    9 개인건
    64682795166015625
    58332816103515625
    401540045166015625
    48909435635166015625
    가 있습니다


    12년 전 link
  • 음매~@
    음매~@

    보라돌이가 항상 점수가 낮은 것 까지는 확인해서 제곱수를 최대한 늘리는 방향으로 짜야되겠다고 생각은 했는데, 시간을 확보를 못해서 시도를 못해본 게 아쉽네요. 이번 라운드1은 더욱 분발해야겠네요!


    12년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    10개 짜리도 찾았다니 ㅎㄷ...


    12년 전 link
  • Neon
    Neon

    처음에는 0붙이기는 전혀 고려하지 않고 문제를 풀었습니다. 도저히 issquare 함수를 짤 엄두가 안나서 걍 10자리 내외의 모든 square number들을 나열한 다음 그것들을 이리저기 기워붙이기를 시도해본건데 점수가 2천점 정도로 나와서 망... 그러다가 곰곰히 생각해보니 x가 square number면 x*100도 square number네! 00만 붙이면 쭉쭉 늘어나네! 그럼 625같이 한자리에서 끝나는 square number 여러개를 찾으면 되겠네! 하고 그동안 만들어놨던 square number generator에서 갖고 놀아서 1434515625를 만들고... 그것보다 더 큰 값은 잘 안나오길래 안나오나보다. 하고 말았져. 저는 그쪽보다 n이 비교적 작은 상황에서는 1434515625 갖고 만들면 안될 것 같길래 더 적은 자릿수의 값들 가지고 만들어서 비교해보는 걸 만들어봤다가 점수가 덜나와서 멘붕하고 그냥 저거랑 네자리 숫자 갖고 만드는 거 둘 중에 하나로만 돌리게 했어요. 그래도 혹시 몰라서 n=10일때는 최초에 만들었던 라스 베가스도 돌리게 했다능. 점수는 별로네여.

    전체적으로 00 multiplier를 찾냐 못찾냐의 문제가 된 것 같아 조금 아쉬움.


    12년 전 link
  • kriii
    kriii

    지금보니 저건 suffix 10개짜리가 아니네요 ㅋㅋㅋㅋㅋ
    ㅋㅋㅋ
    저도 8개 까지가 최고인것 같습니다...
    0으로 시작할때는 제곱수로 안치는걸 잊었네요


    12년 전 link
  • astein
    astein

    새벽 1시(종료 1시간 전)까지 허우적거리다가 아무 생각없이 342250000...000을 제출했더니 뜬금없이 6000점대의 점수를 받아서 트릭을 눈치채고 76125625를 찾아서 제출... suffix 5개짜리네요..... 사실 더 많은걸 찾긴 했는데 예전에 찾았던 데이터를 날려먹어서... 그래도 5등한걸로 만족합니다 [...]


    12년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    ㅋㅋㅋ 저도 bigint Issquare 어떡할까 하다가 3번 스탭부턴 Java로 발랐ㅔ요 ㅋㅋㅋ


    12년 전 link
  • astein
    astein

    Bigint 클래스는 원래 있던거에서 바이너리서치 사용해서 찾는걸로 바꿔서 하긴 함... 근데 효율은 별로일듯 하고... 앞자리부터 고정시켜나가는 식으로 찾으면 되긴 해영... 귀찮아서 그렇지 ㅠㅠ


    12년 전 link
  • 일루
    일루

    34444361465256103515625
    934444361465256103515625


    12년 전 link
  • ipkn
    ipkn

    y^2이 하나의 제곱수일때 (x+y)^2이 뒷자리가 y^2인 x를 찾는 걸 반복하면 되는 문제
    -> y^2이 k자리일때 10^k|x^2 + 2xy를 만족해야함
    -> x^2 + 2xy == 0 (mod 10^k) 인 x를 구하기
    이거 변형하면 x^2=b (mod c)가 되긴하는데 그거 풀줄은 모르고 울프람 알파 넣었어요 (..)


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