Virtual Participated on May 10, 2020.

Practice & VP available here: Codeforces Gym

• Results
  • Summary
  • Virtual Participation
  • Submit Distribution in Members
• Solutions
  • A: Fried Fish
    • 题意
    • 解法
  • B: Hanoi tower
    • 题意
    • 解法
    • Code
  • C: Desktop
    • 题意
    • 解法
  • D: Weather Station
    • 题意
    • 解法
  • E: Cupcakes
    • 题意
    • 解法
  • F: Vitamins
    • 题意
    • 解法
  • G: Sphenic numbers
    • 题意
    • 解法
  • H: Non-random numbers
    • 题意
    • 解法
  • I: Land Division
    • 题意
    • 解法
  • J: Architect of Your Own Fortune
    • 题意
    • 解法
  • K: Polymorphic code
    • 题意
    • 解法
• Timeline
• Reflections

• Solved 10 out of 11 problems
• Rank 1/34 in official records
• Solved 11 out of 11 afterwards

(√ for solved during VP, ○ for after VP, - for tried but not solved)

• Solved by Pantw

$n$ 张饼，每张饼有两面，一个锅一次最多能煎 $k$ 张饼的单面，问最少几分钟煎完所有饼。

$1\le n, k \le 500$

$\mathrm{Ans}:=\lfloor\cfrac{2n}{k}\rfloor+\left[2n\not\equiv 0\pmod{k}\right]$

$\uparrow$ 然而这样就 WA 了，你需要特判 $n < k$ 的情况，此时答案是 2。

• Formula by Withinlover
• Code by Pantw

给一个解 Hanoi 塔问题的程序，问经过多少步，三根杆上的圆盘数第一次相等。

圆盘总数 $n$，保证 $n\equiv 0\pmod 3$。

$1\le n\le 300$。

$\mathrm{Ans}=\begin{cases}2^{\frac{2n}{3}-1}+2^{\frac{n}{3}-1}-1,& n\equiv 0\pmod 6\\2^{\frac{2n}{3}-1}+2^{\frac{n}{3}}-2,& n\equiv 3\pmod 6\end{cases}$

inn = open("input.txt")
ouu = open("output.txt", "w")
n = int(inn.read())
if n % 6 == 0:
    ans = 2 ** (n * 2 // 3 - 1) + 2 ** (n // 3 - 1) - 1
else:
    ans = 2 ** (n * 2 // 3 - 1) + 2 ** (n // 3) - 2
ouu.write(str(int(ans)))

• Solved by Pantw

$h\times w$ 的方格矩阵上放置 $2\times 2$ 的图标，后放的图标显示在先放的上面，覆盖掉先放的格子，要求每个图标至少有两个是可见的，问最多能放多少图标。要求输出方案。

$1\le h, w\le 500$

直接暴力铺开。

图如：

• Solved by Pantw

给一列方向记录，一共有八种方向：N S W E SE SW NE NW，问有多少种可能的解读方式。

简单 DP 题，不说了。

• Solved by Withinlover

$n$ 个人吃蛋糕，总共有 $K$ 块，用 $a_i$ 表示第i个人一次性最多可以吃下的蛋糕数量。也就是说，第 $i$ 个人最少吃 $1$ 块，最多吃 $a_i$ 块。

$a_i$ 最大的人十分贪婪，每次都会吃满 $a_i$ 块。

从第一个人开始，以循环队列的形式轮流吃蛋糕，第一个人吃完后返回队尾。且最后无蛋糕可吃的人将负责收拾残局。问是否存在一种方案使最贪婪的人收拾残局。

$N \leq 2e5, K \leq 1e8,a_i \leq 1e9$

分别算出，每个人都吃 $1$ 块和吃 $a_i$ 块时的 $Min$ 和 $Max$，只要轮到最贪婪的人时 $Min \leq K\leq Max$ 便有解。

记 $T = \max\{a_i\} + n - 1$，即每一次循环最少吃掉的蛋糕数量，一开始觉得暴力模拟会 $TLE$，想用 $(K - i)/T$ 直接算出需要的循环数。还是有些细节的，写完后发现莫名的 $WA$，改成一趟一趟枚举直接就 $A$ 掉了。

仔细想想这题复杂度上限才 $1e8$，浪费时间了。

• Solved by Withinlover

（有没有人玩过一款叫做平衡球的游戏）

这世上一共有三种球，分别对应纸球，木球，铁球。三者重量不同。

现在给你 $n$ 颗球，编号为 $1,2,\dots,n$ ，同时给出 $m$ 个大小关系。用$>,<,=$连接。要求判断出每个球的种类，对于条件不足无法判断的球，输出 “$?$”。

$n\leq 1000$

思路和这个题很像

用并查集把等于号合并，然后对小于号建图。

如果一个集合同时有入度有出度。则为木球。

木球所到达的集合为铁球

到达木球的集合为纸球

剩下的全部无法判断

（这个题的数据范围挺小的乱搞都能过）

• Solved by Pantw

问一个数 $n$ 是否恰好是三个不同质数的乘积。

$30\le n\le 10467397$

直接暴力分解。水题，不说了。

• Solved by Pantw

指定一个位数 $n$，问有多少 $n$ 位 10 进制数满足本身无前导零，且从左至右第 $i$ 位不是 $i$。

$1\le n\le 100$

容易发现 $n$ 超过 $9$ 时，后面的位都没有限制，直接在后面输出 $0$ 就行了，但是还是可以直接用 python 大力莽。这边由于不熟 py 吃了两发罚时。

• Solved by Gary

给出一个凸$n$边形的$n$个点,选择图形上两点构成的线段使得该线段将原图形分为凸$m$边形和凸$k$变形，求线段长度的最小值，不存在输出$-1$，$n$个点按顺时针输入

$1\le n \le1000$

易发现当$n+2 \le m+k \le n+4 $时有解

当$n+2=m+k$时，应选择点到点的线段，依次遍历$n$个点

对于点$P_i$,记$Q_i=P_{i+k-1\pmod n},S_i=P_{i-k+n+1\pmod n}$

则$\mathrm{ans}=\min\{\lvert\overrightarrow{P_iQ_i}\rvert\,\lvert\overrightarrow{P_iS_i}\rvert\}$

当$n+3=m+k$时，应选择点到边的线段，依次遍历$n$个点

对于点$P_i$,记$Q_i=P_{i+k-1\pmod n},Q^{'}_i=P_{i+k+2\pmod n},S_i=P_{i-k+n+1\pmod n},S^{'}_i=P_{i-k+n+2\pmod n}$

则$\mathrm{ans}=\min\{distance(P_i,\overrightarrow{Q_iQ^{'}_i}),distance (P_i,\overrightarrow{S_iS^{'}_i})\}$

当$n+4=m+k$时，应选择边到边的线段，可转化为两边上4个端点到对应边的距离，同上

• Idea by Pantw & Gary
• Code & Debug by Gary

给出$n，m$两组六位数，某一对数$A_i(\overline{a_1a_2a_3a_4a_5a_6}),B_j(\overline{b_1b_2b_3b_4b_5b_6})$是合法的当且仅当$a_1+a_2+a_3=b_4+b_5+b_6$

或$b_1+b_2+b_3=a_4+a_5+a_6$,求最大合法对数并输出方案

$1\le n,m \le 100$

二分图匹配裸题，建图

$S\xrightarrow{\rm{flow}=INF}S_1\quad S_1\xrightarrow{\rm{flow}=1}A_i\quad A_i\xrightarrow{\rm{flow}=1}B_j\quad B_j\xrightarrow{\rm{flow}=1}T$

跑最大流之后判断$A_i\to B_j$中$\mathrm{flow}=0$的边为选中的数对并输出

• Idea by Pantw & Withinlover
• Solved in Practice by Pantw

指定一系列汇编代码加花规则，给出加花后的代码，要求缩回去，如果有多种缩减方案那么取结果最短的。

一群人证了半天发现好像多解不会导致答案长度变化，因为两个可能冲突的 schema 都是 1 换 5。

然后就直接拿个东西存汇编程序，然后从前往后扫，扫到符合模式的就缩，缩完之后指针倒退 7 个单位。

（这个题最后写了 7.5 KB）

吐槽一下，STL 链表真难用。

• 应该一开始听 W 的去写 list 实现，或者手动实现 list。
• 记得写文件操作