E. Count Distinct Sets

Codeforces

IDCF10058E

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Alice writes a permutation P1, P2, P3, ... PN of [1, 2, 3, ...N]. A permutation that follows the condition: Pi > Pi / 2 for all i = 2 to N, is assumed to be an ‘amusing’ permutation. Note that / denotes integer division. Alice wrote down all ‘amusing’ permutations on a sheet of paper. For each number from i = 1 to N, she defines a set Si. A number j belongs to Si if number i was at j’th position in at-least one of the ‘amusing’ permutations. You have to find how many distinct Si exist for i = 1 to N. First line contains T, the number of test cases. Each test case consists of N in single line. For each test case, print the required answer in one line. *Constraints* Example 1. Only ‘amusing’ permutations is [1, 2]. [2, 1] is not an ‘amusing’ permutation because P2 < P2 / 2. S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2}. Therefore 2 distinct sets are possible ie. {1} and {2}. Example 2. All ‘amusing’ permutations are: [1, 2, 3] and [1, 3, 2]. S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2, 3} and S3 is also defined as {2, 3}. So a total of 2 distinct sets {1} and {2, 3} are possible. ## Input First line contains T, the number of test cases. Each test case consists of N in single line. ## Output For each test case, print the required answer in one line.*Constraints* 1 ≤ T ≤ 104 1 ≤ N ≤ 1018 [samples] ## Note Example 1. Only ‘amusing’ permutations is [1, 2]. [2, 1] is not an ‘amusing’ permutation because P2 < P2 / 2.S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2}.Therefore 2 distinct sets are possible ie. {1} and {2}.Example 2. All ‘amusing’ permutations are: [1, 2, 3] and [1, 3, 2].S1 is defined as {1} since 1 only occurs at first position in all ‘amusing’ permutations. Similarly S2 is defined as {2, 3} and S3 is also defined as {2, 3}.So a total of 2 distinct sets {1} and {2, 3} are possible.

**Definitions** Let $ N \in \mathbb{Z}^+ $. A permutation $ P = (P_1, P_2, \dots, P_N) $ of $ \{1, 2, \dots, N\} $ is *amusing* if $ P_i > P_{\lfloor i/2 \rfloor} $ for all $ i = 2, 3, \dots, N $. For each $ i \in \{1, \dots, N\} $, define the set $ S_i \subseteq \{1, \dots, N\} $ as: $$ S_i = \{ j \in \{1, \dots, N\} \mid \exists \text{ an amusing permutation } P \text{ such that } P_j = i \} $$ **Constraints** - $ 1 \le T \le \text{some bound} $ (not specified, but irrelevant for formalism) - For each test case: $ 1 \le N \le \text{some bound} $ (not specified) **Objective** Compute the number of *distinct* sets $ S_i $ for $ i = 1 $ to $ N $.

API Response (JSON)

{
  "problem": {
    "name": "E. Count Distinct Sets",
    "description": {
      "content": "Alice writes a permutation P1, P2, P3, ... PN of [1, 2, 3, ...N]. A permutation that follows the condition: Pi > Pi / 2 for all i  =  2 to N, is assumed to be an ‘amusing’ permutation. Note that  /  ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10058E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alice writes a permutation P1, P2, P3, ... PN of [1, 2, 3, ...N]. A permutation that follows the condition:\n\nPi > Pi / 2 for all i  =  2 to N, is assumed to be an ‘amusing’ permutation. Note that  /  ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z}^+ $. A permutation $ P = (P_1, P_2, \\dots, P_N) $ of $ \\{1, 2, \\dots, N\\} $ is *amusing* if $ P_i > P_{\\lfloor i/2 \\rfloor} $ for all $ i = 2, 3, \\dots, N $.  ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments