CF592B.The Monster and the Squirrel

普及-

通过率:0%

时间限制:1.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Ari the monster always wakes up very early with the first ray of the sun and the first thing she does is feeding her squirrel.

Ari draws a regular convex polygon on the floor and numbers it's vertices 1, 2, ..., n in clockwise order. Then starting from the vertex 1 she draws a ray in the direction of each other vertex. The ray stops when it reaches a vertex or intersects with another ray drawn before. Ari repeats this process for vertex 2, 3, ..., n (in this particular order). And then she puts a walnut in each region inside the polygon.

Ada the squirrel wants to collect all the walnuts, but she is not allowed to step on the lines drawn by Ari. That means Ada have to perform a small jump if she wants to go from one region to another. Ada can jump from one region P to another region Q if and only if P and Q share a side or a corner.

Assuming that Ada starts from outside of the picture, what is the minimum number of jumps she has to perform in order to collect all the walnuts?

阿里这个怪物总是在第一缕阳光照进来的清晨早早醒来,而她做的第一件事就是喂她的松鼠。

阿里在地板上画了一个正凸多边形,并按顺时针方向将其顶点依次编号为 1, 2, …, n1,\,2,\,\dots,\,n。然后,她从顶点 11 开始,向其余每个顶点各画一条射线;该射线在抵达某个顶点或与之前已画出的某条射线相交时即停止。接着,她依序对顶点 2, 3, …, n2,\,3,\,\dots,\,n 重复这一过程(严格按此顺序)。最后,她在多边形内部的每一个区域中都放上一颗核桃。

松鼠阿达想要收集全部核桃,但她不允许踩到阿里所画的任何线条上。这意味着:若阿达想从一个区域进入另一个区域,就必须进行一次小跳跃。当且仅当两个区域 PP 与 QQ 共享一条边或一个顶点(角)时,阿达才可从区域 PP 跳跃至区域 QQ。

假设阿达从图示范围之外开始行动,那么她为收集全部核桃所需执行的最少跳跃次数是多少?

输入格式

The first and only line of the input contains a single integer n (3 ≤ n ≤ 54321) - the number of vertices of the regular polygon drawn by Ari.

输入仅有一行,包含一个整数 nn(3 ≤ n ≤ 543213 \leq n \leq 54321),表示阿里所画正多边形的顶点数。

输出格式

Print the minimum number of jumps Ada should make to collect all the walnuts. Note, that she doesn't need to leave the polygon after.

输出Ada收集所有核桃所需的最少跳跃次数。注意,她无需在收集完所有核桃后离开多边形。

输入输出样例

  • 输入#1

    5

    输出#1

    9
  • 输入#2

    3

    输出#2

    1

说明/提示

One of the possible solutions for the first sample is shown on the picture above.

第一个样例的一种可能解法如上图所示。

输入解题思路,AI测评打分。不知道怎么写?

首页