Monday, January 6, 2014

SPOJ GUANGGUN


Problem link: SPOJ Problem Set (classical): 9952. 111…1 Squared

Interesting and fun problem. This is one of those problems that you can sense a pattern from miles away. Just do some bruteforce and print the patterns. You can use pen and paper too, but Python is surely a better option when you have it. All I did is write some bruteforce in my python interpreter, and the pattern is instantly visible, here is the output of f(n)2 for n = 1 to 50:

1
121
12321
1234321
123454321
12345654321
1234567654321
123456787654321
12345678987654321
1234567900987654321
123456790120987654321
12345679012320987654321
1234567901234320987654321
123456790123454320987654321
12345679012345654320987654321
1234567901234567654320987654321
123456790123456787654320987654321
12345679012345678987654320987654321
1234567901234567900987654320987654321
123456790123456790120987654320987654321
12345679012345679012320987654320987654321
1234567901234567901234320987654320987654321
123456790123456790123454320987654320987654321
12345679012345679012345654320987654320987654321
1234567901234567901234567654320987654320987654321
123456790123456790123456787654320987654320987654321
12345679012345679012345678987654320987654320987654321
1234567901234567901234567900987654320987654320987654321
123456790123456790123456790120987654320987654320987654321
12345679012345679012345679012320987654320987654320987654321
1234567901234567901234567901234320987654320987654320987654321
123456790123456790123456790123454320987654320987654320987654321
12345679012345679012345679012345654320987654320987654320987654321
1234567901234567901234567901234567654320987654320987654320987654321
123456790123456790123456790123456787654320987654320987654320987654321
12345679012345679012345679012345678987654320987654320987654320987654321
1234567901234567901234567901234567900987654320987654320987654320987654321
123456790123456790123456790123456790120987654320987654320987654320987654321
12345679012345679012345679012345679012320987654320987654320987654320987654321
1234567901234567901234567901234567901234320987654320987654320987654320987654321
123456790123456790123456790123456790123454320987654320987654320987654320987654321
12345679012345679012345679012345679012345654320987654320987654320987654320987654321
1234567901234567901234567901234567901234567654320987654320987654320987654320987654321
123456790123456790123456790123456790123456787654320987654320987654320987654320987654321
12345679012345679012345679012345679012345678987654320987654320987654320987654320987654321
1234567901234567901234567901234567901234567900987654320987654320987654320987654320987654321
123456790123456790123456790123456790123456790120987654320987654320987654320987654320987654321
12345679012345679012345679012345679012345679012320987654320987654320987654320987654320987654321
1234567901234567901234567901234567901234567901234320987654320987654320987654320987654320987654321
123456790123456790123456790123456790123456790123454320987654320987654320987654320987654320987654321

Beautiful, isn't it?


1 comment:

  1. Hello! This is my 1st comment here so I just wanted to give a quick shout out and tell you I truly enjoy
    reading through your blog posts. Can you recommend any other blogs/websites/forums that go over the same
    topics? Thanks for your time!

    Here is my webpage: our Website

    ReplyDelete