Cliquez ici pour les problèmes-> http://nabetani.sakura.ne.jp/hena/ord15subpalin/
Comparez les deux caractères, un caractère à la fois, à partir de la combinaison des premier et dernier caractères. Si les n1er et n2nd caractères sont identiques, augmentez la longueur (ans) de 2. Recherchez le même caractère entre n1 + 1 et n2-1. (Boucle dans la boucle for de la fonction de boucle) Si le dernier nième et n + 1 ne sont pas identiques, ajoutez 1 à la longueur. Au début, il était tard sans taille avec Julia, alors je l'ai essayé avec Nim et Ruby, Après tout, si la somme de la longueur actuelle (ans) et du nombre de caractères restants est supérieure à la longueur maximale (ventilateurs) jusqu'à présent Seuls (fans <j-i + ans + 1) effectuent une simple recherche de branche et poursuivent la recherche. Si je mets une pause après la boucle dans la boucle for, c'est devenu beaucoup plus rapide. Julia
#Julia v 0.6-1.4
inp="0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3"
function main()
local fans
function loop(str,ans)
if str !=""
for i in 1:length(str)-1
for j in length(str):-1:i+1
if str[j]==str[i] && fans<j-i+ans+1
loop(str[i+1:j-1],ans+2)
break
end
end
end
ans +=1
end
if fans<ans
fans=ans
end
end
str0=split(inp,"\n")
for s0 in str0
s1=split(s0," ")
fans=0
ans=0
loop(strip(s1[2]),ans)
if fans==parse(Int,s1[3])
sel="pass"
else
sel="fail"
end
print(sel," ",fans,"\n")
end
end
@time main()
Nim Parfois, ce n'est pas beaucoup plus rapide que Julia, mais dans ce problème (code), c'est beaucoup plus rapide.
#Nim v 0.194
import os,strutils,sequtils,times
import math
const inp="""0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3"""
proc main()=
var fans=0
proc loop(str:string,ans:int)=
var ans1=ans
if str != "":
for i in 0..len(str)-2:
for j in countdown(len(str)-1,i+1):
if str[j]==str[i] and fans<j-i+ans1+1:
loop(str[i+1..j-1],ans1+2)
break
ans1=ans1+1
if fans<ans1:
fans=ans1
for s0 in inp.splitLines :
var s1=s0.split(" ")
fans=0
loop(s1[1].strip,0)
var sel=""
if fans==s1[2].strip.parseInt:
sel="pass"
else:
sel="fail"
echo(sel," ",fans)
var t = cpuTime()
main()
echo cpuTime()-t
Ruby J'ai l'impression qu'il y avait plus d'utilisateurs de Ruby parmi les participants à "Comment écrire". Je lis la première édition de "Ruby du langage de script orienté objet" J'ai eu l'impression que Delphi est plus pratique pour les programmes GUI et qu'il est plus lent à résoudre les énigmes. Je l'ai utilisé au lieu de awk de temps en temps. Cependant, en raison d'un autre problème, c'était considérablement plus rapide que Julia lorsque je l'ai écrit en référence au code d'autres personnes, donc J'ai aussi essayé cette fois. Ce problème n'était pas très tôt avant la taille, mais après la taille, c'est un bon match avec Julia. Du point de vue des utilisateurs de rubis, cela peut être démodé et redondant, mais je publierai celui élagué.
#ruby v 2.5.5
require 'benchmark'
$inp="0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3"
def main()
def loop(str,ans)
if str !=""
for i in 0..str.length-2
(str.length-1).downto(i+1) {
|j|
if str[j]==str[i] && $fans<j-i+ans+1
loop(str[i+1..j-1],ans+2)
break
end
}
end
ans +=1#*string(str[1])
end
if $fans<ans
$fans=ans
end
end
$inp.lines do |s0|
s1=s0.split(" ")
$fans=0
ans=0
loop(s1[1].strip,ans)
if $fans==s1[2].to_i
sel="pass"
else
sel="fail"
end
print(sel," ",$fans,"\n")
end
end
time = Benchmark.realtime do
main()
end
p time
Une autre solution (Prolog) Il s'agit d'une méthode pour trouver la plus longue combinaison du même caractère dans la chaîne de caractères opposée à la chaîne de caractères d'origine. C'est une récurrence commémorative. Si les n1 et n2 des deux chaînes sont identiques, augmentez la longueur R de 1 et comparez les n1 + 1 et n2 + 1. S'ils sont différents, en comparant les n1 + 1 et n2nd, et en comparant les n1st et n2 + 1th Ajoutez le plus long et R. Si vous l'écrivez comme du code f (n1, n2) = si n1 == n2: f (n1 + 1, n2 + 1) + 1 # résoudre / 4 4ème section sinon: max (f (n1 + 1, n2), f (n1, n2 + 1)) # résoudre / 4 5ème section Pour la partie de conversion de mémo, utilisez functor pour créer un mémo du tableau bidimensionnel (F). Dans la troisième section de résoudre / 4, si elle est écrite dans le mémo (nonvar (R1)), utilisez cette valeur. data / 4 est utilisé pour écrire et lire des mémos.
%SWI-Prolog v 7.4.2,7.6.4
%start.
%:-initialization(start). %ideone
twoar(_,0,_). % two dimensional array
twoar(F,X,Y):-arg(X,F,V),functor(V,y,Y),X1 is X-1,twoar(F,X1,Y).
data(F,X,Y,V):-arg(X,F,V1),arg(Y,V1,V).
solve([],_,_,0).
solve(_,[],_,0).
solve(L1,L2,F,R):-
length(L1,N1),length(L2,N2),data(F,N1,N2,R1),nonvar(R1),!,R=R1.
solve([H1|T1],[H2|T2],F,R):-
H1==H2,!,length([H1|T1],N1),length([H2|T2],N2),
solve(T1,T2,F,R1),R is R1+1,data(F,N1,N2,R).
solve([H1|T1],[H2|T2],F,R):-
length([H1|T1],N1),length([H2|T2],N2),
solve([H1|T1],T2,F,R1),solve(T1,[H2|T2],F,R2),R is max(R1,R2),data(F,N1,N2,R).
start:-str(S),split_string(S,"\s,\n","\s",L),pre(L),!.
disp(R,Q):-
number_string(R,R1),(R1==Q->Str="pass ";Str=" fail "),
write(" "),write(Str),writeln(R).
pre([]).
pre([_,B,C,_|T]):-
atom_chars(B,L),reverse(L,L1),length(L,M),M1 is M+5,functor(F,x,M1),twoar(F,M1,M1),
solve(L,L1,F,R),disp(R,C),pre(T).
str("0 I_believe_you_can_solve 9 evo_n_ove
1 a 1 a
2 aa 2 aa
3 aaa 3 aaa
4 ab 1 b
5 aabb 2 bb
6 ABBA 4 ABBA
7 Abba 2 bb
8 1234567890 1 0
9 1234567890987654321 19 1234567890987654321
10 abcdcba 7 abcdcba
11 0a1b2c3d4c5b6a7 7 abc4cba
12 abcdcba0123210 7 0123210
13 abcdcba_123210 7 abcdcba
14 _bcdcba0123210 7 0123210
15 abcddcba0123210 8 abcddcba
16 abcdcba01233210 8 01233210
17 a0bc1dc2ba3210a 9 a0123210a
18 a0bc1ddc2ba3210 8 0bcddcb0
19 3a0bc1ddc2ba3210 10 3abcddcba3
20 11oooo1111o1oo1o111ooooooooooo 20 oooo111o1oo1o111oooo
21 11o1111o1111oo11ooo11111ooo1oo 20 o1o1111oo11oo1111o1o
22 111111oo11o111ooo1o1ooo11ooo1o 21 1ooo11ooo1o1ooo11ooo1
23 11o1o1o11oo11o11oo111o1o1o11oo 27 11o1o1o11oo11o11oo11o1o1o11
24 oo111o1o11o1oo1ooo11o1o11o1o1o 27 oo111o1o11ooo1ooo11o1o111oo
25 1o1oo11111o1o1oo1o1o1111oo1o1o 28 1o1oo1111o1o1oo1o1o1111oo1o1
26 QQooooQooooQQyQoyQQQyyyyQQoyoy 15 ooQQyyQQQyyQQoo
27 oQoooQooooQyoyQoyoyyyQQyQQQQoQ 16 QoQQyQyyyyQyQQoQ
28 yyyyyooyQyyyoyyQyyooyQoQoQQoQy 17 yooQyoyyQyyoyQooy
29 yyQoyQoyyQyQQoyooooyyQQyQyooQy 24 yQooyQyQQyooooyQQyQyooQy
30 oQQooQoQyQQoyoQQoQyQyQyQoQoooo 24 oooQoQyQQyoQQoyQQyQoQooo
31 oQQyQQyyQyQQoooyQQyyyQQQyyQQoy 25 oQQyQQyyyQQoooQQyyyQQyQQo
32 WAk9iHI4jVDlStyudwTNqE138kwan2 3 wkw
33 c43fIu1Mlz0K9hEVOgGcUdbeB5ksa7 3 cGc
34 CAbYcW5VqHjzFdIkH_61PM0TsyRuie 3 HkH
35 jInQnUvSayrJTsQWujovbbqW0STvoj 10 jvTWbbWTvj
36 iZDrvpUKgtj3FrZsZ4CLjrEgUdZzQG 11 ZUgrZsZrgUZ
37 ROgYUOu6er_DA7nB6UGquO1GUHC62R 11 RUOu6B6uOUR
38 Oh_be_a_fine_girl_kiss_me 9 e_i_l_i_e
39 8086_6502_6809_Z80 11 8086_2_6808
40 xcode_visualstudio_eclipse 11 ce_iutui_ec
41 word_excel_powerpoint_outlook 9 ol_opo_lo
42 abcdefghijklmnopqrstuvwxyz0123 1 3").