Under construction

Still being built. Things may change

Classroom Assignment

Time limit1sMemory limit1024 MB

Summary
Given N classrooms, pair them into floor(N/2) classes of two rooms each to find the maximum number of chocolate pies Jiwoong can receive.
Level

Medium6 of 10

Topics
Dynamic programming, Bit manipulation
Solved
No attempts yet

Problem

Daegu Science High School is repairing its reading hall, so self-study is held in regular classrooms instead. The teachers worried that students would make noise, so they decided to give each class two classrooms. The rooms differ in size, so the teachers rotate the room assignments every day to share them fairly. The school has NN classrooms and ⌊N2⌋\lfloor \frac{N}{2} \rfloor classes. Each class is split into students with odd numbers and students with even numbers, and the two groups study in different classrooms.

Input

The first line contains an integer NN.

Output

Print the maximum number of chocolate pies Jiwoong can receive.

Constraints

  • 2≤N≤302 \le N \le 30

Hints

  • The maximum number of chocolate pies Jiwoong can receive does not exceed 2602^{60}.
  • If NN is odd, one classroom is left empty.
  • ⌊x⌋\lfloor x \rfloor is the greatest integer less than or equal to xx.

Examples1

  1. Example 1

    Input
    6
    
    Expected output
    15