UTS Open '21 P1 - COVID Party

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Sava and his N - 1 friends are organizing a party in celebration of his first 15-point solve on DMOJ. The N people can each be represented as a point in a 2-D plane. Due to health concerns, they must party abiding the new Manhattan social distance rule. The rule states that the Manhattan distance between any 2 people must be no less than 2. For reference, the Manhattan distance between 2 points (x_1, y_1), (x_2, y_2) is |x_1 - x_2| + |y_1 - y_2|. Since the venue Sava is renting only provides square-shaped rooms in integer S \times S dimensions, he is curious as to what the minimum possible S is such that it is possible for the N people attending the party to arrange themselves in the room abiding the Manhattan social distance rule. Please write a program to help him out.


For this problem, you MUST pass the sample cases in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

2 \le N \le 10^9

Subtask 1 [20%]

2 \le N \le 10^5

Subtask 2 [80%]

No further constraints.

Input Specification

The first and only line contains an integer N, the number of people attending the party.

Output Specification

Output one line containing the minimum possible integer S such that N people can fit in a square-shaped S \times S room abiding the Manhattan social distance rule.

Sample Input 1


Sample Output 1


Explanation for Sample 1

The following diagram depicts a possible arrangement of the 3 people in a 2 \times 2 room abiding the Manhattan social distance rule. Note that it is possible for a person to position themselves directly on the borders of the room.

It can be proven that 3 people cannot fit in a 1 \times 1 room abiding the Manhattan social distance rule, so S = 2 is our final answer.

Sample Input 2


Sample Output 2



  • 0
    shubho  commented on Feb. 14, 2021, 2:31 a.m.


    • 1
      Ehsian  commented on Feb. 14, 2021, 7:26 p.m.

      There is a pattern. Try drawing out a couple layers on paper, then look for the pattern from there.