鱼C论坛

 找回密码
 立即注册
查看: 185|回复: 22

[已解决]【C++板块提升计划】梦想护卫舰 第13期 细胞分裂

[复制链接]
发表于 4 天前 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 sfqxx 于 2023-1-26 17:57 编辑

上一关:https://fishc.com.cn/thread-223768-1-1.html

你们打开了神庙大门,成功救出了小甲鱼
然后你们告别了他,继续前进,结果遇到了“hanks博士”
题目描述:
Hanks 博士是 BT(Bio-Tech,生物技术)领域的知名专家。现在,他正在为一个细胞实验做准备工作:培养细胞样本。

Hanks 博士手里现在有 N 种细胞,编号从 1~N,一个第 i 种细胞经过 1 秒钟可以分裂为 S
i 个同种细胞(Si为正整数)。现在他需要选取某种细胞的一个放进培养皿,让其自由分裂,进行培养。一段时间以后,再把培养皿中的所有细胞平均分入 M 个试管,形成 M 份样本,用于实验。Hanks 博士的试管数 M很大,普通的计算机的基本数据类型无法存储这样大的 M 值,但万幸的是,MM 总可以表示为 m1的m2 次方, 其中 m1 ,m 2均为基本数据类型可以存储的正整数。

注意,整个实验过程中不允许分割单个细胞,比如某个时刻若培养皿中有 4 个细胞,Hanks 博士可以把它们分入 2 个试管,每试管内 2 个,然后开始实验。但如果培养皿中有 5 个细胞,博士就无法将它们均分入 2 个试管。此时,博士就只能等待一段时间,让细胞们继续分裂,使得其个数可以均分,或是干脆改换另一种细胞培养。

为了能让实验尽早开始,Hanks 博士在选定一种细胞开始培养后,总是在得到的细胞“刚好可以平均分入 M 个试管”时停止细胞培养并开始实验。现在博士希望知道,选择哪种细胞培养,可以使得实验的开始时间最早。


输入格式:
第一行,有一个正整数 NN,代表细胞种数。
第二行,有两个正整数 m1,m 2,以一个空格隔开,即表示试管的总数 M = m1的m2次方。
第三行有 N 个正整数,第 i 个数S i表示第 i 种细胞经过 1 秒钟可以分裂成同种细胞的个数。
输出格式:
一个整数,表示从开始培养细胞到实验能够开始所经过的最少时间(单位为秒)。
如果无论 Hanks 博士选择哪种细胞都不能满足要求,则输出整数 -1

输入与输出样例:
输入(1)
  1. 1
  2. 2 1
  3. 3
复制代码

输出(1)
  1. -1
复制代码

输入(2)
  1. 2
  2. 24 1
  3. 30 12
复制代码

输出(2)
  1. 2
复制代码

说明/提示
【输入输出样例 1 说明】

经过 1 秒钟,细胞分裂成 3 个,经过 2 秒钟,细胞分裂成 9个,……,可以看出无论怎么分裂,细胞的个数都是奇数,因此永远不能分入 22 个试管。

【输入输出样例 2 说明】

第 1 种细胞最早在 3 秒后才能均分入 24 个试管,而第2 种最早在 2 秒后就可以均分(每试管 144 / 24^1 = =6 个)。故实验最早可以在 2 秒后开始。
数据范围:
对于 50% 的数据,有m 1的m 2次方 ≤30000。

对于所有的数据,有 1≤N≤10000,1≤m 1 ≤30000,1≤m2≤10000,1≤S i≤2×10 的9次方
提示:可以作用分解鸡数,啊不,分解质因数的方法解决。
注:本题非原创,见这里
答案
游客,如果您要查看本帖隐藏内容请回复
[/hide]
最佳战士:hziyan
奖励:3贡献 5 荣誉最佳答案
使用语言:python3(回答时请标注)
下一关:【C++板块提升计划】梦想护卫舰 第14期 取余
https://fishc.com.cn/thread-223804-1-1.html



顺便打个广告:戳他
此链接设置了鱼币福利,欢迎参加!
(你们积极参与我就有机会申请精华
最佳答案
3 天前
sfqxx 发表于 2023-1-26 17:12
我拿您的代码去试试,如果通过即可领奖励

。。那你还是用这个吧,我刚有个特殊判定没加上
  1. kinds = input()
  2. m1,m2 = input().split()
  3. splits = input().split()
  4. m1 = int(m1)
  5. m2 = int(m2)
  6. time = set()
  7. pri_m = set()
  8. pri_tm = set()

  9. for factor in range(2,m1+1):
  10.     if m1 % factor ==0:
  11.         ifadd = True
  12.         for f in pri_m:
  13.             if factor % f == 0:
  14.                 ifadd = False
  15.                 break
  16.         if ifadd:
  17.             tm = 0
  18.             while m1 % factor == 0:
  19.                 m1 /= factor
  20.                 tm += 1
  21.             pri_tm.add(tm)
  22.             pri_m.add(factor)  

  23. maxtm = max(pri_tm)*m2 if pri_tm else 0
  24. for sp in splits:
  25.     sp = int(sp)
  26.     if len([sp for m in pri_m if sp % m == 0]) == len(pri_m):
  27.         pri_ts = set()
  28.         
  29.         for t in pri_m:
  30.             ts = 0
  31.             while sp % t == 0:
  32.                 sp /= t
  33.                 ts += 1
  34.                
  35.             pri_ts.add(ts)
  36.             
  37.         maxts= max(pri_ts) if pri_ts else 1

  38.         if maxtm % maxts == 0:
  39.             time.add(maxtm // maxts)
  40.         else:
  41.             for t in range(2,maxtm+1):
  42.                 if maxts *t > maxtm:
  43.                     time.add(t)
  44.                     break
  45.     else:
  46.         time.add(-1)
  47.             
  48. time.discard(-1)
  49. if time:
  50.     print(min(time))
  51. else:
  52.     print(-1)
复制代码

评分

参与人数 2荣誉 +7 鱼币 +7 贡献 +3 收起 理由
zhangjinxuan + 5 + 5 鱼C有你更精彩^_^
liuhongrun2022 + 2 + 2 + 3

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
抱歉了,我数学不好。 这题太难
先不论这题如何解决,单是计算试管有几个都成问题,试问如何算出 30000^10000 是多少呢?另外分裂 S 可以最多是 2×10 的9次方(这只是第一个时间单位),第二个时间单位再分裂的话根本没有办法算了吧?接近无限 infinity
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 4 天前 | 显示全部楼层
傻眼貓咪 发表于 2023-1-25 17:27
抱歉了,我数学不好。 这题太难
先不论这题如何解决,单是计算试管有几个都成问题,试问如何算 ...

您点击原创链接看看,我复制来可能会有细微差别
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
sfqxx 发表于 2023-1-25 17:28
您点击原创链接看看,我复制来可能会有细微差别

看了,哈哈哈,我还是不会,数据太大了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
我提供个思路:(不知道正不正确)
分解质因数
24=2^3*3;
12= 2^2*3 ;12^2 =2^4*3^2可以包含24((2^3*3)*2*3)
30= 2*3*5;30^3=2^3*3^3*5^3可以包含24((2^3*3)*3^2*5^3)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 4 天前 | 显示全部楼层
jhq999 发表于 2023-1-25 17:41
我提供个思路:(不知道正不正确)
分解质因数
24=2^3*3;

对的,我忘记说了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 4 天前 | 显示全部楼层
傻眼貓咪 发表于 2023-1-25 17:33
看了,哈哈哈,我还是不会,数据太大了

去参加一下我的鱼币活动呗,顺便测测运气
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
密码已经被破译了,小甲鱼都被救出来了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
傻眼貓咪 发表于 2023-1-25 17:27
抱歉了,我数学不好。 这题太难
先不论这题如何解决,单是计算试管有几个都成问题,试问如何算 ...

分 解 只 因 数
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
额,标题改一下,最后的密码破译改成细胞分裂
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层

  1. #这里提供一下C++的答案
  2. #include <bits/stdc++.h>
  3. using namespace std;

  4. int n, m1, m2;
复制代码

第二行,C++ 的注释是    // 开头的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 4 天前 From FishC Mobile | 显示全部楼层
zhangjinxuan 发表于 2023-1-25 20:14
额,标题改一下,最后的密码破译改成细胞分裂

啊呀,尴尬极了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 4 天前 | 显示全部楼层
数学要学好哇~(我**干嘛要选数学题
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
 楼主| 发表于 4 天前 From FishC Mobile | 显示全部楼层
zhangjinxuan 发表于 2023-1-25 22:20
数学要学好哇~(我**干嘛要选数学题

跟数学没关系吧
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 3 天前 | 显示全部楼层
sfqxx 发表于 2023-1-25 22:39
跟数学没关系吧

肯定有啊,分解质因数难道不是数学吗?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 3 天前 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 3 天前 | 显示全部楼层
我盯了一下午,用Python写出来,顺便在洛谷看看他们怎么写的,结果全是用C写的


  1. kinds = input()
  2. m1,m2 = input().split()
  3. m1 = int(m1)
  4. m2 = int(m2)
  5. splits = input().split()
  6. time = set()
  7. pri_m = set()
  8. pri_tm = set()

  9. for factor in range(2,m1+1):
  10.     if m1 % factor ==0:
  11.         ifadd = True
  12.         for f in pri_m:
  13.             if factor % f == 0:
  14.                 ifadd = False
  15.                 break
  16.         if ifadd:
  17.             tm = 0
  18.             while m1 % factor == 0:
  19.                 print(f"m1:     {m1}/{factor}={m1/factor},{tm}+1")
  20.                 m1 /= factor
  21.                 tm += 1
  22.             pri_tm.add(tm)
  23.             pri_m.add(factor)  

  24. maxtm = max(pri_tm)*m2
  25. print(pri_m,pri_tm,maxtm)
  26. for sp in splits:
  27.     print(f"___{sp}____")
  28.     sp = int(sp)
  29.     if len([sp for m in pri_m if sp % m == 0]) == len(pri_m):
  30.         print(sp)
  31.         pri_ts = set()
  32.         
  33.         for t in pri_m:
  34.             ts = 0
  35.             while sp % t == 0:
  36.                 print(f"splits:{sp}/{t}={sp/t},{ts}+1")
  37.                 sp /= t
  38.                 ts += 1
  39.                
  40.             pri_ts.add(ts)
  41.             
  42.         maxts= max(pri_ts)   
  43.         print(pri_ts,pri_tm)

  44.         if maxtm % maxts == 0:
  45.             time.add(maxtm // maxts)
  46.         else:
  47.             for t in range(2,maxtm+1):
  48.                 if maxts *t > maxtm:
  49.                     time.add(t)
  50.                     break
  51.         print(time)
  52.     else:
  53.         time.add(-1)
  54.             
  55. time.discard(-1)
  56. if time:
  57.     print(min(time))
  58. else:
  59.     print(-1)
  60.             
  61.             
复制代码

改了好多遍了,也不想写注释,就这样吧
写下来最大的感想就是起名字好难啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 3 天前 | 显示全部楼层
等会,我刚交的是观赏版
  1. kinds = input()
  2. m1,m2 = input().split()
  3. m1 = int(m1)
  4. m2 = int(m2)
  5. splits = input().split()
  6. time = set()
  7. pri_m = set()
  8. pri_tm = set()

  9. for factor in range(2,m1+1):
  10.     if m1 % factor ==0:
  11.         ifadd = True
  12.         for f in pri_m:
  13.             if factor % f == 0:
  14.                 ifadd = False
  15.                 break
  16.         if ifadd:
  17.             tm = 0
  18.             while m1 % factor == 0:
  19.                 m1 /= factor
  20.                 tm += 1
  21.             pri_tm.add(tm)
  22.             pri_m.add(factor)  

  23. maxtm = max(pri_tm)*m2
  24. for sp in splits:
  25.     sp = int(sp)
  26.     if len([sp for m in pri_m if sp % m == 0]) == len(pri_m):
  27.         pri_ts = set()
  28.         
  29.         for t in pri_m:
  30.             ts = 0
  31.             while sp % t == 0:
  32.                 sp /= t
  33.                 ts += 1
  34.                
  35.             pri_ts.add(ts)
  36.             
  37.         maxts= max(pri_ts)   

  38.         if maxtm % maxts == 0:
  39.             time.add(maxtm // maxts)
  40.         else:
  41.             for t in range(2,maxtm+1):
  42.                 if maxts *t > maxtm:
  43.                     time.add(t)
  44.                     break
  45.     else:
  46.         time.add(-1)
  47.             
  48. time.discard(-1)
  49. if time:
  50.     print(min(time))
  51. else:
  52.     print(-1)
  53.             
  54.             
复制代码

(不要问观赏版是什么,问就改bug顺便问问你们是怎么改bug的)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 3 天前 | 显示全部楼层
。。要不要我再加一下特判
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1

GMT+8, 2023-1-29 18:04

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表