QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#559910#6395. Equation DiscoveringchimeraTL 19ms11076kbPython31.8kb2024-09-12 10:27:282024-09-12 10:27:30

Judging History

你现在查看的是最新测评结果

  • [2024-09-12 10:27:30]
  • 评测
  • 测评结果:TL
  • 用时:19ms
  • 内存:11076kb
  • [2024-09-12 10:27:28]
  • 提交

answer

import math
import functools

N = int(input())
Xys = [tuple(map(eval,input().split())) for _ in range(N)]


def sin(vs):
    return [math.sin(v) for v in vs]
def cos(vs):
    return [math.cos(v) for v in vs]
def add(vs1, vs2):
    return [v1+v2 for v1,v2 in zip(vs1,vs2)]
def mul(vs1, vs2):
    return [v1*v2 for v1,v2 in zip(vs1,vs2)]
def div(vs1, vs2):
    if not len(vs2) or min(vs2) < .01:
        return []
    return [v1/v2 for v1,v2 in zip(vs1,vs2)]
def sub(vs1, vs2):
    return [v1-v2 for v1,v2 in zip(vs1,vs2)]

@functools.lru_cache(maxsize=None)
def evl(e):
    if e == 'x':
        return [a[0] for a in Xys]
    
    operand = e[0]
    args = tuple(map(evl, e[1:]))
    return eval(operand)(*args)
    


def chk(e):
    reslt = evl(e)
    if len(reslt) and max([abs(r-y)/max(1,abs(y)) for r,y in zip(reslt, [v[1] for v in Xys])]) <= 1e-3:
        return True
    
def pprint(e):
    #print(e)
    if e == 'x':
        return e
    if e[0] in ('sin','cos'):
        return f'{e[0]}({pprint(e[1])})'
    mpd = {'add':'+','sub':'-','mul':'*','div':'/'}
    return f'({pprint(e[1])}{mpd[e[0]]}{pprint(e[2])})'


exprs = [['x']]
for i in range(1,10):
    e2 = [('sin', v) for v in exprs[-1]] + [('cos', v) for v in exprs[-1]]

    for nl in range(0, (i-2)+1):
        nr = i - 2 - nl
        for op in ('add','mul','div','sub'):
            if (op == 'add' or op == 'mul') and nl < nr:
                continue
            for v1 in exprs[nl]:
                for v2 in exprs[nr]:
                    e2.append((op, v1, v2))
    exprs.append(e2)

    for e in e2:
        #assert e.count('sin') + e.count('cos') + 2*sum(e.count(x) for x in ('add','mul','div','sub')) == i

        if chk(e):
            print(pprint(e))
            quit()
            pass
print(len(exprs[-1]))

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 8ms
memory: 10916kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

(x*x)

result:

ok great!!

Test #2:

score: 0
Accepted
time: 19ms
memory: 11076kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

(sin(x)/(x*x))

result:

ok great!!

Test #3:

score: 0
Accepted
time: 11ms
memory: 11076kb

input:

5
77.685777 233.057331
-66.445083 -199.335249
79.966717 239.900151
84.982130 254.946390
-31.528900 -94.586700

output:

((x+x)+x)

result:

ok great!!

Test #4:

score: -100
Time Limit Exceeded

input:

5
25.032427 -0.100652
38.727324 1.658518
27.684334 -0.669555
64.282391 8.275303
52.640700 -0.962660

output:


result: