这是我想解决的问题:
有一个N(
N1≤≤4)福克森守着一个宝贵的宝藏,你喜欢亲自动手.问题是,Foxen肯定不会允许 - 至少,不是在他们醒着的时候.幸运的是,通过仔细观察,你已经看到每个狐狸都有一个规律的睡眠周期.特别是,
i狐狸保持清醒Ai(1≤≤23Ai)小时,然后睡眠Si(Si1≤≤23)小时,无限期地重复这种模式(Ai + Si2≤≤24).在你的宝藏尝试开始时,i福克斯正好Oi(0≤Oi<Ai + Si)小时进入它的周期.如上所述存在
T(1≤≤20T)场景.对于每一个,你想确定所有的狐狸会在多长时间内同时睡着,让你抓住他们的宝藏,或者如果这根本不会发生.输入
Run Code Online (Sandbox Code Playgroud)Line 1: 1 integer, T For each scenario: Line 1: 1 integer, N Next N lines: 3 integers, Ai, Si, and Oi, for i = 1..N产量
Run Code Online (Sandbox Code Playgroud)For each scenario: Line 1: 1 integer, the minimum number of hours after the start to wait until all of the Foxen are asleep during the same hour. If this will never happen, output the string "Foxen are too powerful" (without quotes) instead.样本输入
Run Code Online (Sandbox Code Playgroud)2 2 2 1 2 2 2 1 3 1 1 0 1 1 0 1 1 1样本输出
Run Code Online (Sandbox Code Playgroud)6 Foxen are too powerful
当我输入给定的示例案例并获得预期的输出时,我的解决方案按预期工作.但是当我将代码提交给在线判断时,它会给出修剪错误.现在没有错误的细节,这使得很难找到问题所在.
这是我迄今为止所做的解决方案:
# ai is awake hours
# si is sleep hours.
# ai + si <= 24.
# False == sleep. True == awake.
datasets = int(raw_input());
foxen = [];
number_of_foxen = 0;
foxes = [];
class fox:
def __init__(self, a, s, i):
self.awake = a;
self.sleep = s;
self.current = i;
awake = 0;
sleep = 0;
current = 0;
def next(self):
if ( self.sleep + self.awake-1 > self.current ) :
self.current = self.current+1;
else:
self.current = 0;
return self.current;
def check(self):
if(self.current>=self.awake):
return False;
return True;
def printdata(self):
print "awake="+str(self.awake)+" sleep="+str(self.sleep)+" current="+str(self.current);
#return "awake="+str(self.awake)+" sleep="+str(self.sleep)+" current="+str(self.current);
for i in range(0, datasets):
number_of_foxen = int(raw_input());
for j in range(0, number_of_foxen):
foxen.append(raw_input());
x = foxen[j].split();
a = fox(int(x[0]), int(x[1]), int(x[2]));
foxes.append(a);
solution = False;
for j in range(0, 48):
#print "hour number = " + str(j);
#for k in range(0, len(foxes)):
#print "fox number="+ str(k)+" "+ foxes[k].printdata()+str(foxes[k].check());
count = 0 ;
for k in range(0, len(foxes)):
if(foxes[k].check()==False):
count+=1;
#print "count = "+str(count);
#print len(foxes);
if( (int(count) == int(len(foxes))) and (solution == False) ):
#print "this runs now *************";
solution = True;
number = j;
for k in range(0, len(foxes)):
foxes[k].next();
if(solution==True):
print number;
else:
print "Foxen are too powerful";
#print "Foxen are too powerful";
foxen = [];
number_of_foxen = 0;
foxes = [];
小智 5
Jorge的评论是正确的,除了任意48小时的截止外,你的算法似乎没有任何问题.
然而:
1)您的print语句不使用Python 3+的正确语法.例如,您的最终print语句print "Foxen are too powerful";必须更改为在Python 3中工作,请尝试print ('Foxen are too powerful')使用.
2)我也看到一些奇怪的C/MatLab语法,行以分号结束,双括号围绕if语句中的条件.这可能不是问题,但根据你提交答案的系统的挑剔程度,你可能想要清理一下.
3)绝对增加搜索的截止时间.我推荐一个相当大的值,大约10,000小时,只是为了确保它不会是一个因素.
我冒昧地做了以上所有更改,所以我现在发布结果代码:
# ai is awake hours
# si is sleep hours.
# ai + si <= 24.
# False == sleep. True == awake.
datasets = int(raw_input())
foxen = []
number_of_foxen = 0
foxes = []
class fox:
def __init__(self, a, s, i):
self.awake = a
self.sleep = s
self.current = i
awake = 0
sleep = 0
current = 0
def next(self):
if ( self.sleep + self.awake-1 > self.current ):
self.current = self.current+1
else:
self.current = 0
return self.current
def check(self):
if(self.current>=self.awake):
return False
return True
def printdata(self):
print ("awake="+str(self.awake)+" sleep="+str(self.sleep)+" current="+str(self.current))
#return ("awake="+str(self.awake)+" sleep="+str(self.sleep)+" current="+str(self.current))
for i in range(0, datasets):
number_of_foxen = int(raw_input())
for j in range(0, number_of_foxen):
foxen.append(raw_input())
x = foxen[j].split()
a = fox(int(x[0]), int(x[1]), int(x[2]))
foxes.append(a)
solution = False
for j in range(0, 10000):
#print ("hour number = " + str(j))
#for k in range(0, len(foxes)):
#print ("fox number="+ str(k)+" "+ foxes[k].printdata()+str(foxes[k].check()))
count = 0
for k in range(0, len(foxes)):
if(foxes[k].check()==False):
count+=1
#print ("count = "+str(count))
#print (len(foxes))
if (int(count) == int(len(foxes)) and (solution == False)):
#print ("this runs now *************")
solution = True
number = j
for k in range(0, len(foxes)):
foxes[k].next()
if(solution == True):
print (number)
else:
print ("Foxen are too powerful")
#print ("Foxen are too powerful")
foxen = []
number_of_foxen = 0
foxes = []
享受和祝你好运!
您的代码最大的问题是它无法读取.实际上,它似乎是用Python的优点概念编写的.这是我的建议:
#!/usr/bin/env python3
"""
The Foxen's Treasure puzzle from http://wcipeg.com/problem/acmtryouts1b
"""
from sys import stdin
from itertools import cycle
from euclid import lcm
debug = True # set to False before submission to mechanical judge
class Fox:
"""A Fox cointains its defining integers and other derived
bindings such as its cycle and schedule."""
def __init__(self, trio):
(self.awake_count, self.sleep_count, self.skip_count) = trio
self.cycle = 'a' * self.awake_count + 's' * self.sleep_count
self.schedule = cycle(self.cycle)
if debug: print('<Fox: {}> cycle {}'.format(trio, self.cycle))
# handle skips by discarding the first elements
for _ in range(self.skip_count):
next(self.schedule)
def find_all_sleeping(foxes):
"""Return an hour number if all foxes are sleeping at that hour."""
# only examine the LCM of all fox periods. If not there it will never be.
lcm_period = 1
for fox in foxes:
lcm_period = lcm(lcm_period, len(fox.cycle))
for hour in range(lcm_period):
states = [next(fox.schedule) for fox in foxes]
if debug: print('{:2d} {}'.format(hour, ' '.join(states)))
if 'a' not in states:
return hour
return None
def read_trials(fp):
"""Reads the entire input at once. Returns a list of trials.
Each trial is a list of Fox."""
trials = list()
trial_count = int(fp.readline())
for trial in range(trial_count):
if debug: print('--Read trial {}'.format(trial))
foxes = list()
fox_count = int(fp.readline())
for _ in range(fox_count):
fox = Fox([int(x) for x in fp.readline().split()])
foxes.append(fox)
trials.append(foxes)
return trials
for trial, foxes in enumerate(read_trials(stdin)):
if debug: print('--Run trial {}'.format(trial))
hour = find_all_sleeping(foxes)
if hour is None:
print('Foxen are too powerful')
else:
print(hour)
我怀疑第一个问题是它看起来比OP长得多; 这是事实,但是如果你拿出显示事情发生方式的调试代码,以及解释它为什么会这样做的文档字符串,它实际上比OP短几行.
如果没有重要的研究,OP的主循环太长而无法理解,并且一大堆不良变量名称使得更难.相反,这里有一些地方只给一个值一个名称,以使代码更明确地表明输入行的含义.你会发现很多
for _ in range(trial)
显示未使用循环值.在处理固定格式输入时,这是一种常见的习惯用法.
Fox表示将内部工作保持在问题空间中.正如练习页面所述,将事物视为序列之间的并发更有意义:
--Read trial 0
<Fox: [2, 1, 2]> cycle aas
<Fox: [2, 2, 1]> cycle aass
skip_count这里没有显示偏移量,但在试运行中它们很清楚.
数据文件的输入全部保留在内部,read_trials()而不是通过代码分散.这将混乱局限于一个地方而不是通过代码分发.我们从拼图说明中了解到数据文件不够大,无法关注.read_trials(fp)还有一个类文件对象,允许它从实际文件,StringIO缓冲区或标准输入中读取.
一旦Fox计划生成器初始化,itertools.cycle将为序列中的下一个字母提供无休止的供应; 它为你做环绕.
值得注意的是,主要数据结构trials是一个普通的旧列表,因为它不需要更多的东西.
我有点厌倦了糟糕的代码被更糟糕的代码回答.当然,这可以被认为不仅仅是电子法官的需求,只有输出很重要.相反,我仍然感到困惑,比如(solution == False),一个长42行的主循环,在文件的顶部和底部之间分开,变量喜欢i和j没有传达意图,内存负担False == awake(或者我混淆了吗？ ),死代码,无操作代码,`范围(0,n)和一大堆幻数.
当然,您可以像代码一样编码并不重要,但如果您正在教自己编写代码,那么练好练习是很好的.是的,你可能再也不会看这段代码了,但如果你现在不学习它,那么什么时候？
如果您认为导入作弊lcm()是没有理由再次写入,所以我引用了一个自制程序包,其相关行是:
def gcd(a, b):
"""Return the Greatest Common Divisor of a and b."""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""Return the Least Common Multiple of a and b."""
return abs(a * b) // gcd(a, b)