Skip to content

Richardyu114/ZTEchallenge-2020-Fourier

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

9 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

背景描述

在某片遥远的大陆上,居住着两个世代友好的部落,分别是部落A和部落B。他们一起耕耘劳作,互相帮助,亲如一家。久而久之,部落里的每个人都在对方部落里找到了志趣相投,互相欣赏的好朋友。有的人性格热情开朗,好朋友很多;有的人性格沉稳内敛,好朋友相对少一些。 每到秋天丰收的季节,这两个部落的人民都会聚集在一起举行盛大的“丰收祭”,来祈祷下一年的风调雨顺。今年的丰收祭马上又要举行了。为了进一步增进两个部落的友谊,也为了明年能有一个好收成,这两个部落的祭司们商量后决定:在今年的丰收祭前举办一场特别的“击鼓传花”游戏。只不过游戏中并非有人真的击鼓,并且所传递的“花”也不是真的花,而是等待在丰收祭上献上的祭品。 游戏规则如下:

  1. 两个部落的所有人都可以事先准备自己的祭品,且每个人的祭品样式都不同,每一个祭品都分别盛放在一个相对应的木托盘里;准备此祭品的人熟悉自己的祭品;
  2. 每个人可以准备的祭品数量不限;祭品的最小不可分割单位是1份;
  3. 游戏开始后,在整个游戏过程中,每个人都能且只能将祭品(包括木托盘)传递给自己在对方部落里的好朋友们,每个好友可以接收的祭品数量不限;
  4. 收到祭品的人必须在盛放此祭品的木托盘上刻上自己的名字(代表留下自己美好的祝愿),随后按按照上一条规则,继续传递;
  5. 如果祭品回到最初准备此祭品的人手中,此人也在木托盘上刻上自己的名字之后,终止传递;
  6. 木托盘上不允许出现重复的人名,如果无法满足此条件,则不再继续传递该祭品;
  7. 当所有的祭品都不再传递后,游戏结束;

游戏开展得非常顺利。游戏结束后,祭司们将收集同时满足如下三个条件的祭品用于接下来的丰收祭活动:

  1. 此祭品回到了最初准备它的人手中;
  2. 盛放此祭品的木托盘上至少有4个名字,至多有14个名字;
  3. 如果有多个木托盘上的名字完全一样(不区分名字的排列顺序),则从其中随机选择一个木托盘所对应的祭品。

问题

已知这两个部落里的所有人都不重名,并且部落A的人和部落B的人之间的好朋友关系以附件的csv数据表格文件给出,其中行索引代表部落A中的人,列索引代表部落B中的人,表格中的数字“1”代表他们两人是好朋友,“0”代表他们两人不是好朋友。请问:如果以木托盘上的名字的数量对用于丰收祭的祭品分类,每一类分别最多有多少个祭品?

具体:

木托盘上有4个名字的祭品最多有()个;

木托盘上有6个名字的祭品最多有()个;

木托盘上有8个名字的祭品最多有()个;

木托盘上有10个名字的祭品最多有()个;

木托盘上有12个名字的祭品最多有()个;

木托盘上有14个名字的祭品最多有()个;

代码要求

c++ / java / python / matlab 皆可,只准单线程,在CPU不超过3GHz,内存不多于8G的家用电脑上运行时间不超过10分钟得出答案

TODO

由于数据存在人为精心设定的规律,所以时间可以压缩至1分钟,但是如果针对一种普遍性搜环问题,数据是随机不确定的,该如何进行优化,尤其是查重。