QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#54566 | #1361. Ant Typing | not_so_organic# | AC ✓ | 450ms | 68468kb | Java11 | 1.7kb | 2022-10-09 18:18:21 | 2022-10-09 18:18:22 |
Judging History
answer
import java.io.*;
import java.util.*;
public class ant_finn {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] seq = br.readLine().toCharArray();
int n = seq.length;
int[][] counts = new int[9][9];
for (int i=1; i<seq.length; i++) {
int d1 = seq[i-1]-'1';
int d2 = seq[i]-'1';
counts[d1][d2]++;
}
int[] perm = new int[9];
for (int i=0; i<9; i++) {
perm[i] = i;
}
int best = 987654321;
while (perm!=null) {
int[] index = new int[9];
for (int i=0; i<perm.length; i++) {
index[perm[i]] = i;
}
int sum = index[seq[0]-'1'];
for (int i=0; i<9; i++) {
for (int j=0; j<9; j++) {
int dist = index[i]-index[j];
if (dist<0)
dist*=-1;
sum += counts[i][j]*dist;
}
}
sum += seq.length;
if (sum<best)
best = sum;
perm = nextPermutation(perm);
}
System.out.println(best);
}
static int[] nextPermutation(int[] c) {
int first = getFirst(c);
if (first == -1)
return null;
int toSwap = c.length - 1;
while (c[first] >= c[toSwap])
--toSwap;
swap(c, first++, toSwap);
toSwap = c.length - 1;
while (first < toSwap)
swap(c, first++, toSwap--);
return c;
}
static int getFirst(int[] c) {
for (int i = c.length - 2; i >= 0; --i)
if (c[i] < c[i + 1])
return i;
return -1;
}
static void swap(int[] c, int i, int j) {
int tmp = c[i];
c[i] = c[j];
c[j] = tmp;
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 314ms
memory: 65264kb
input:
6
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 357ms
memory: 64492kb
input:
352836512461179399826927828445163785261417666171453483576899676763764928341261962358737253818463814858565221466575498899898835568743316628247174676952381449147193191788177911797527361649543158616436321694172452689147288835568666918784929695569394655833978219612584637258492511247969998253315177569943...
output:
392933
result:
ok single line: '392933'
Test #3:
score: 0
Accepted
time: 383ms
memory: 64516kb
input:
968884598119167786222882717561136271258178322114499631431168437152319338284128325566492371843153634373998119972663175955316621871196955773794711869424245474973253727335485699826672425921549421474494147229652553728521332495721653457163161741649486568718788497235884884271122261183582319332269114971817...
output:
394664
result:
ok single line: '394664'
Test #4:
score: 0
Accepted
time: 431ms
memory: 68468kb
input:
683412251689845461817923147259774964383159658449891915133215549956251828864364313696312963272819495298632848747431585341886467284794396545668622674767116477954324211934265166678211817468916142924319716576862979237997215273147359445833376466319214969265971711816157481253512934953386353547377361396196...
output:
393919
result:
ok single line: '393919'
Test #5:
score: 0
Accepted
time: 397ms
memory: 68372kb
input:
793413248661841899956962996149582153286568745845426726626741997574977847728465587437749642293284475574432875453315117193156379221656595692327291876139928696877762933239918113828226436292619542275425269336822184239426865136177559755975137675165562357892872597995857677171316858612137827928654836578312...
output:
393800
result:
ok single line: '393800'
Test #6:
score: 0
Accepted
time: 403ms
memory: 64764kb
input:
417945123165992614765338944444296975768196599265132553568932179127253855711163863765928951248227823968765833275116543283633468248662742363347291168368263991438531662944563875763722861928627934312432227281273297129383518712815967362374683269769633684932228244154481357479667523356385974327797382399565...
output:
393463
result:
ok single line: '393463'
Test #7:
score: 0
Accepted
time: 450ms
memory: 66480kb
input:
761516338356551975157774489286685265387439119927746187735157324467763246485133173342627781962263755596343666343884382465193163361936949619496665752933335714897716429375772618157582373867283283241418469738176736798731116515132727471419652997699517743927634878619359762879346214965527473515198792719195...
output:
393734
result:
ok single line: '393734'
Test #8:
score: 0
Accepted
time: 328ms
memory: 66512kb
input:
452646533999964766974591119414915157862638483746513612496323887667364175241679367348981649871647174262463497116677212838644661788747989751984334147364683635749881659943383248733477481144973282945443365529669337986546236169645654786951236661879848964251181798394453699395876173261855611628215186596864...
output:
393449
result:
ok single line: '393449'
Test #9:
score: 0
Accepted
time: 335ms
memory: 64956kb
input:
892933166787684876233472692156924877315491587224215657794711176246792498827395714358785444393137862131622236664777297685973478453481742735955935812548619939949816263513262474652489599115938517554462282656168899394675812293721799857276432796467622182215326836428112463683881984867759968618983979294471...
output:
393543
result:
ok single line: '393543'
Test #10:
score: 0
Accepted
time: 400ms
memory: 64156kb
input:
443494391473867598146699249145491138796297424237949566864711424981515755661718517795236754493356987316553369681157821636124825155655178124138485945376482389189885549849534358284722459348434263344632142928463753398997552947717347367229653393645997599977962716972387584965662667771286366458526719422475...
output:
393892
result:
ok single line: '393892'
Test #11:
score: 0
Accepted
time: 299ms
memory: 62692kb
input:
731751822859611165598229768362525618797797786414166541796193792191817827787177438958755714113769658417884754281628475364174221136483412233629911963258152989777957187848636623359446872443865864688396641842338556377493828515381262475482145412849119644181582598812122977861578955553151553678661841713618...
output:
395302
result:
ok single line: '395302'
Test #12:
score: 0
Accepted
time: 368ms
memory: 64312kb
input:
934538585471192519625275252367341866598775944166724559493147921744372875426231194623428159714745149887834583134911937786184781872397328363525511548593914512334184721543963296931746111262678356446331416657852779338592196754945219987351255255113871941424453534388598429896133627862518823496499552773293...
output:
394207
result:
ok single line: '394207'
Test #13:
score: 0
Accepted
time: 351ms
memory: 64320kb
input:
555458514559312987914285792461913388993893412631869484867557593593525819593167492862232364752163342551675643529457597173941389569895113199149129217845486619926653726231667241256957632199264546637842377666942866821631564188222544636553744594511762271883887995884588548164211188283798612313524714389853...
output:
393360
result:
ok single line: '393360'
Test #14:
score: 0
Accepted
time: 381ms
memory: 65392kb
input:
443311794878596951273565853645197445255454363672495881798126447715765388831543847213671343257665541858544398361698142261622689885464777244736891361542468382554323887898376413472285718763828126796623771187213266973727697493572839135445921379295646449329819692475718229886945353998585854198272694653781...
output:
393589
result:
ok single line: '393589'
Test #15:
score: 0
Accepted
time: 372ms
memory: 64568kb
input:
6666666666111212131313141414141515151515161616161616171717171717171818181818181818191919191919191919
output:
283
result:
ok single line: '283'
Test #16:
score: 0
Accepted
time: 307ms
memory: 63548kb
input:
111212131313141414141515151515161616161616171717171717171818181818181818191919191919191919
output:
273
result:
ok single line: '273'