Like Tree1Likes
  • 1 Post By kmdv

Problem with task

This is a discussion on Problem with task within the C++ Programming forums, part of the General Programming Boards category; Hi, I have a problem with my task. I have 2-dimensional board and in the middle are 3 numbers (1,1,1) ...

  1. #1
    Registered User
    Join Date
    Jan 2013
    Posts
    3

    Problem with task

    Hi, I have a problem with my task. I have 2-dimensional board and in the middle are 3 numbers (1,1,1) - in vertical rotation. They make one segment. The „next step” will be one distinction of that segment. It is growing in the way that to each end, added are the next numbers (one greater than the previously added) with changing rotation (vertical- horizontal -vertical etc.)
    On that 2-dimensional board I put point (x,y) in some place, which in case of meeting with growing segments will stop their growth. My job is to put for giving points (x,y) if growing segments
    will ever meet with the points (if yes after how many steps ),if not then I have to write never.

    I think I need to look for solution in moving diagonal. For main diagonal (0x0, 1x1, 2x2 etc.) Results are next power of number 2. Every next power of the number 2 they make ,,almost squares" with dimensions (2^)- 1 x 2^. At the end of that squares ( in middle of the bigger square) (1x2,3x4,7x8 etc.)....(each smaller is a half of the bigger one )) I am able to turn in any another diagonal and in her middle I am able to turn in another one (just how many times I need), but unfortunately there are a certain shifts (resulting probably from that the ,,almost squares" are not the real squares (3x4 instead of 4x4)). I m going to show it in the examples below for better understanding. I am adding also a link to the picture of the board (32x32) and few examples correct and invalid.
    Board (-1- will never meet, 0x0 in the bottom left corner): img27.imageshack.us/img27/3600/planszad.png

    Example 1. (Correct)
    1). Preliminary result: 8 (4x4)
    2). Preliminary result: 12 (6x2)
    3). Preliminary result: 10 (5x3) (half dimensional of quadrangle 4x4 6x2)
    4). End result: 12 (4x2)

    Example 2 (correct)
    x =2 y=10
    1) preliminary result: 16 (8x8)
    2) preliminary result: 24 (4x12)
    4) end result: 28 (2x10)

    Example 3 (invalid)
    X=9. Y=3 (the result is number even and is placed UNDER dimensional)
    1) preliminary result: 16 (8x8)
    2) preliminary result: 24 (12x4)
    Preliminary result: 28 (10x2)
    4) end result: 30 (9x3)

    Explanation: in the end result the result should be reduced by 2 not increased but I don't know what I am doing wrong. Please help me with this task, I need to finish it till the end of the week.

    P.S. Coordinates x and y they fit in interval (-100000;100000) but growing segments are ,,quarters" symmetric so in case of negative coordinates we can make them into positive (x=|x|, y=|y|). I put a link to oryginal content of the task: img51.imageshack.us/img51/462/tresc.png
    Last edited by Salem; 01-10-2013 at 09:07 AM. Reason: Fixed image URLs

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,755
    Announcements - C++ Programming
    So when you say "have a problem", does this mean you've got as far as writing any code at all?

    If you have code, you should post it.
    Announcements - General Programming Boards
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Jan 2013
    Posts
    3
    Writing code is not a problem and that is why I don’t ask for it. The problem is how to resolve this task. All of my ideas turned out to be incorrect / inaccurate.

    Ps. Created board has a lot of reflection symmetric, for example :
    If x>=y then t[x,y]=t[y,x+1]+1

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    I'm afraid I don't understand what that task is from your description.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    Your post of the original content says to draw line segments on a grid to simulate the development of one of the pathogens. This seems simple and straightforward. You could write a program that accepts input for a given age then draws the shape of the colony. Since the colony can only grow in one way the shape will always be the same at any given age.

    You then proceed to describe a program that has nearly nothing in common with the "original" description. From the best I can gather you are giving it a set of coordinayes and seeing if line segments ever meet in that coordinate?

    Still seems very unclear. What if the given coordinates are at 0,0 then it is the center (midpoint) of a singular line segment therefor not really a meeting of line segments. Would this then qualify as false? If the point 0, 1 was given does this qualify as true since the next line segment will draw rotated with this at its midpoint or are we only talking about points such as -1, 0 where two parallel line segments meet at an endpoint?

    Try to be more concise in a description of the objective before telling us the logic behind what didn't work. I think you would have gotten an answer by now if it had been clear.

  6. #6
    Registered User
    Join Date
    Jan 2013
    Posts
    3
    Here is the full wording of the task: http://img713.imageshack.us/img713/8484/fullj.png
    This image shows what the results should be returned by my program (bottom left - x=0,y=0, top right - x=32,y=32): http://img27.imageshack.us/img27/3600/planszad.png
    Someone has some idea on this task?

  7. #7
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Seems pretty strait forward. Build the table in planszad.png, big enough to enclose all input bacteriostats, and then some. Then look up the coordinate of each bacteriostat on the table, and that'll give you the result for each trial.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  8. #8
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    Build the table in planszad.png, big enough to enclose all input bacteriostats, and then some
    His description said -1,000,000 <= x <= 1,000,000.

    So that would be storing 1,000,000,000,000 sets of coordinates in a map. Seems excessive.

    It definitely seems like there is a simplier pattern here. Its full of symmetry and rotation.

    First thing I notice is on the Y axis is it counts upward in 2s (with the exception of coordinate (0, 1)) and only the powers of 2 are in white, all other numbers are -1.

    The X axis is counting upward in 2s but in odd numbers, and only the ((powers of 2)-1) are in white, all other numbers are -1.
    So all valid coordinates could be represented as the number set
    Where N is any whole number and the equation represents as
    X Coordinate = AGE

    (2^N) - 1 = (2^(N+1))-1
    If you just save the picture put it a image editing program.
    (change coordinate (16, 25) to white as it is improperly colored and change coordinate (2, 12) to that tanish grey color as it is also colored wrong)

    Then look at the picture itself and you can see that smaller segments can be copied, pasted and then rotated to the right or the left by 90 in order to create the exact same pattern based on if you translate upward or towards the right.

    Translating up seems to be a rotation to the left by 90 degrees while translating right seems to be a rotation to the right by 90 degrees.

    It seems that other than the X and Y axis being a different pattern the rest of it is just a rotation of the pattern performed by (1, 1), (15, 16).

    The things that concern me about the assumption is.
    1. The picture's colors were wrong so logically the picture's numbers could be wrong.
    2. The Pattern's reptition seems to change by powers of 2 so (32, 32) could represent a new point in the sequence with a few new "special cases" that are only relected into its larger counterparts rather than smaller.

    I am guessing there is a fractal algorithym at work here, but I never managed to finish that book so I'm at a loss for spotting it yet. I do enjoy this puzzle though so I will probably keep thinking about it until a solution is presented.

    Though it looks like the modulus of 16 is going to be significant.
    Last edited by Lesshardtofind; 01-13-2013 at 03:59 AM.

  9. #9
    Registered User
    Join Date
    Aug 2010
    Location
    Poland
    Posts
    682
    Quote Originally Posted by algo00 View Post
    I put a link to oryginal content of the task: img51.imageshack.us/img51/462/tresc.png
    o_O

    Original content?
    I think this is the original one: High School Programming League 2012/13 - Problem HS12BAPE

    This is not the way to win a contest.
    Salem likes this.
    I never put signature, but I decided to make an exception.

  10. #10
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    You guys are ninjas on finding this stuff.

    I am slightly dissapointed I won't find the solution to this. The best I could tell it is a differential equation. I started learning trajectories and fractal complex plane graphing to see if I could solve this from that information and while I have found equations to represent each axis value individually I haven't found one to represent the entire problem.

    I always love a good problem. Kinda scary to think a highschooler somewhere has already solved this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help from the task
    By MAJA83 in forum C Programming
    Replies: 1
    Last Post: 06-06-2012, 12:35 PM
  2. Need help to do the big task
    By Steve Cao in forum Linux Programming
    Replies: 1
    Last Post: 07-16-2010, 03:01 PM
  3. Replies: 2
    Last Post: 12-31-2007, 11:40 AM
  4. Task/Process Problem
    By slx47 in forum C++ Programming
    Replies: 1
    Last Post: 05-11-2002, 06:37 AM
  5. task bar
    By Unregistered in forum C Programming
    Replies: 2
    Last Post: 03-21-2002, 05:53 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21