Skip to content

11531: 【原1531】电路手动分析

题目

题目描述

author: 彭宇翔,greatwall1995 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1531

Description

在设计电路的过程中,常常要手动分析电路。

我们故事的主人公 —— 奸笑熊是一个参加了 NOI2015 结果遗憾退役的 OIer。

马上就要回班搞高考了,奸笑熊不免有点伤感。于是奸笑熊开始玩电路散散心。

奸笑熊的电路有 n×m 个节点,排成 n 行 m 列。任意两个相邻节点之间连着一条导线。如果两个节点 (x1,y1),(x2,y2) 满足 ∣x1−x2∣+∣y1−y2∣=1 则称这两个节点相邻。

奸笑熊定义一个电路的复杂程度为最大的非负整数 s 满足可以选出 s 个节点使得任意两个被选中的节点间都有一根导线相连。

奸笑熊手里还有 r 根导线,可以连在 r 对节点之间。奸笑熊希望新加上不超过 r 根导线后,电路的复杂程度最大。

请你帮奸笑熊手动分析他的电路,告诉他复杂程度最大是多少。

Input Format

共一行,包含三个整数\(n, m, r\).

Output Format

共一行,包含一个整数表示答案。

Sample Input 1

2 2 0

Sample Output 1

2

Sample Input 2

2 3 3

Sample Output 2

4

Limits

对于30%的数据,\(1≤n, m≤4, r≤13\)

对于另外40%的数据,\(n=1, m≤10^18\)

对于100%的数据,\(n, m≤10^9, r≤10^18\).

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!