oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

memory Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

memory.html

JOI-chan was selected to represent Japan in the upcoming IOI. In order to improve his information processing skills, manager K of the Japanese Informatics Olympic Committee has presented him with a task as follows:

Manager K will write down a string S that he will not reveal to JOI-chan. S consists only of the characters '<', '>', '[' and ']'. Manager K will still tell JOI-chan the length of the string.

JOI-chan's task is to determine if the string S is good. Whether or not a string is good is defined by the following rules:

  • It is an empty string. In other words, it is a string of length zero.
  • If x is a good string, then <x> is also a good string.
  • If x is a good string, then [x] is also a good string.
  • If x and y are good strings, then xy is also a good string.

For example, "<>[]" and "[<>]<>" are good strings, but "><" and "[<]>" are not.

JOI-chan will can make a phone call to Manager K once a day at noon. JOI-chan can give Manager K an integer I, to which Manager K will respond by telling JOI-chan the Ith character of S.

However, JOI-chan is not allowed to make any notes about this problem or otherwise note any information about it down. The only exception to this is the length of the string, which JOI-chan will always have access to. Apart from that, JOI-chan is only allowed to rely on his own memory. Every day, JOI-chan sleeps at 10 pm and wakes up at 6 am, during which he can only remember 22 bits of information. In other words, before he sleeps, JOI-chan can memorize any integer from 0 to 222 - 1 and recall it in the morning.

Relying only on his memory and his smarts, JOI-chan must determine if Manager K's string is good through the daily phone calls within 15 000 days.

Implementation

You are to write one program to implement JOI-chan's strategy for determing if Manager K's string is good. The program should include Memory_lib.h as a header. Within the program, you must implement the following function.

  • int Memory(int N, int M)

    A call to this function represents JOI-chan's actions for a day.

    • Parameter N is the length of the string S.
    • Parameter M is the integer JOI-chan memorized from the previous day. On the very first day, M = 0.
      • During the execution of this function, you are allowed to call Get at most once.
      • This function must return an integer. If the integer is within 0 to 222 - 1 inclusive, then that integer is the integer JOI-chan will memorize for tomorrow. Otherwise, it must be -1 or -2. If it is -1, S must be a good string. If it is -2, S must be a bad string. If the integer you return does not satisfy the above description, your program will receive a "Wrong Answer (1)" verdict.
    • The function's return value and calling behavior to Get should depend only on N and M. In the actual grading process, this function will be called 222 × 4 times. For more details, read the grading process.

Your program is allowed to call this function.

  • char Get(int I)

    • Within every call to Memory you are allowed to call this function at most once. If this function is called more than once within one call of Memory, your program will receive a "Wrong Answer (2)" verdict.
    • Parameter I must be within the bounds 1 ≤ I ≤ N. If this function is called with a parameter I that does not satisfy those bounds, then your program will receive a "Wrong Answer (3)" verdict.
    • This function will return the Ith character of S.

Grading Process

The program is graded against a selection of test cases each of which consist of multiple test strings S with the same length N. For each test string, the grading process terminates immediately whenever a "Wrong Answer" verdict is determined.

  • Given the length of the strings N, the grader will investigate the behavior of your program for all possible inputs. In other words, for each M satisfying 0 ≤ M ≤ 222 - 1, the following process will be used:

    • For each character c in '<', '>', '[' and ']', Memory will be called with parameters N and M. If Get is called during the execution of Memory, c will be returned. The grader will store the return value of Memory(N, M) as m(M, c).
    • In the four calls to Memory performed above, any calls to Get must be exactly the same. In other words, if a call to Get is made during any of the calls to Memory for this particular M, then all of the three other calls to Memory should call Get with the same parameter I. If no call was made to Get during one of the calls to Memory for this particular M, then all of the three other calls to Memory should also not produce any calls to Get. If this condition is not satisfied, your program will receive a "Wrong Answer (4)" verdict.
    • If a call to Get was made, the grader will store the parameter to Get as i(M). If no call was made, i(M) = 1.
  • For each of the strings S in the test case, the grader will simulate the process described in the problem as follows:

    1. M is initially 0.

    2. Repeat forever:

      1. Set c to the i(M)th character of S.
      2. Set M to m(M, c).
      3. If M is -1 or -2, break.
      4. If this is the 15 000th iteration, your program will receive a "Wrong Answer (5)" verdict.
    3. If any of the conditions below are satisfied, your program will receive a "Wrong Answer (6)" verdict.

      1. S is a good string but M = -2.
      2. S is not a good string but M = -1.
    4. Your program will receive a "Correct" verdict.

    Important Note

    The runtime of your program will be the runtime of the grading process as described above. Namely, note that Memory will be called 222 × 4 times.

    The simple grader provided runs your program according to a simulation of the problem above, whereas the strict grader provided runs your program according to the grading process described above. Due to the difference in grading method, the simple grader is not able to determine a "Wrong Answer (4)" verdict.

    Constraints

    All test cases satisfy the following constraints.

    • 1 ≤ N ≤ 100.
    • S consists of only characters '<', '>', '[' and ']'.

    Subtasks

    Subtask 1 (10 points):

    • N ≤ 8 is satisfied.

    Subtask 2 (10 points):

    • N ≤ 14 is satisfied.

    Subtask 3 (5 points):

    • N ≤ 24 is satisfied.

    Subtask 4 (5 points):

    • N ≤ 30 is satisfied.

    Subtask 5 (10 points):

    • S contains only characters '<' and '>'.

    Subtask 6 (60 points):

    No further constraints.

    Sample Input

    4 1
    <>[]
    

    Explanation

    According to the behavior of the simple grader, here is an example of the sequence of calls made.

    Call to MemoryReturn valueCall to GetReturn value
    Memory(4, 0)
    Get(1)
    <
    2015
    Memory(4, 2015)
    Get(3)
    [
    3
    Memory(4, 3)
    Get(2)
    >
    23
    Memory(4, 23)
    Get(4)
    ]
    4194303
    Memory(4, 4194303)
    Get(3)
    [
    -1

    Tags

    JOI 2014/2015

    Subtasks and Limits

    Subtask Score #TC Time Memory Scoring
    11032s256MBMinimum
    21012s256MBMinimum
    3512s256MBMinimum
    4512s256MBMinimum
    51012s256MBMinimum
    66022s256MBMinimum
    7012s256MBMinimum

    Attachments

    Attachment Filesize Last Updated
    grader-simple.cpp1.5KB22 Mar 2015, 21:22:54
    Memory_lib.h82B22 Mar 2015, 23:57:10
    grader-strict.cpp2.44KB22 Mar 2015, 17:43:48
    sample-in-01.txt9B22 Mar 2015, 17:43:48
    sample-out-01.txt3B22 Mar 2015, 17:43:26
    Memory.cpp76B22 Mar 2015, 23:57:12

    Judge Compile Command

    g++-8 ans.cpp grader.cpp -o memory -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

    Accepted Submissions

    subIDUserTimeMax Time

    Past Submissions

    subIDUserTimeScore
    mrJudge 09.05.20
    Copyright © 2020 mrJudge. All rights reserved.