Vous êtes Tom Sawyer et vous devez peindre une clôture de 102400 m de long. Heureusement, vos amis ont décidé de vous aider en échange de diverses choses. Chaque ami peindra L mètres, à partir de S avec la couleur C . S , L sont un nombre entier de mètres et 1 ≤ C ≤ 97. En vous ennuyant, vous décidez de savoir combien de mètres de chaque couleur vous avez.
Contribution
L'entrée est lue à partir de l'entrée standard. Chaque ligne contient trois nombres S , L , C comme décrit ci-dessus.
Ouput
La sortie est écrite sur la sortie standard. Pour chaque couleur qui apparaît sur la clôture finale, imprimez le numéro de couleur et le nombre de fois qu'il apparaît. Commandez par couleurs.
Exemples
Entrée 0
..............
0 3 1 111...........
2 4 2 112222........
1 2 3 133222........
0 4 1 111122........
7 3 5 111122.555....
Sortie 0
1 4
2 2
5 3
Entrée 1
0 100 1
50 150 2
Sortie 1
1 50
2 150
Entrée 2
500 1000 1
0 2000 2
Sortie 2
2 2000
Plus d'exemples
Voici un petit générateur:
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
/* From http://en.wikipedia.org/wiki/Random_number_generation */
unsigned m_w;
unsigned m_z;
unsigned get_random()
{
m_z = 36969 * (m_z & 65535) + (m_z >> 16);
m_w = 18000 * (m_w & 65535) + (m_w >> 16);
return (m_z << 16) + m_w; /* 32-bit result */
}
int main(int argc, char **argv)
{
int i;
assert(argc == 2);
m_w = 0xbabecafe;
m_z = atoi(argv[1]);
i = 10;
while (i--);
get_random();
i = atoi(argv[1]);
while (i--) {
int s = (int) ((get_random() << 8) % 102397);
int l = (int) ((get_random() << 8) % (102397 - s));
int c = (int) ((get_random() << 8) % 97 + 1);
printf("%d %d %d\n", s, l, c);
}
return 0;
}
Exemples d'exécution:
$ ./gen 1 | ./paint
6 535
$ ./gen 10 | ./paint
28 82343
36 3476
41 1802
49 4102
82 1656
$ ./gen 100 | ./paint
2 2379
22 17357
24 4097
25 1051
34 55429
42 9028
45 9716
66 1495
71 196
85 640
97 706
$ ./gen 1000 | ./paint
16 719
26 29
28 24
33 1616
55 371
65 35
69 644
74 16
84 10891
86 36896
87 50832
89 19
$ ./gen 10000 | ./paint
3 800
6 5712
14 3022
17 16
26 1
29 18770
31 65372
37 387
44 40
49 37
50 93
55 11
68 278
70 19
71 64
72 170
77 119
78 6509
89 960
97 15
$ ./gen 100000 | ./paint
2 6
8 26
12 272
24 38576
26 1
34 1553
35 8
36 19505
43 2
45 11
46 2
47 9
49 27339
50 139
53 3109
69 11744
92 89
$ ./gen 1000000 | ./paint
1 1
3 4854
6 523
13 1
16 11
18 416
22 7
24 3920
25 96
31 10249
32 241
37 1135
45 10
57 758
62 2348
65 11
66 7422
78 6
85 13361
87 3833
88 187
91 46
93 7524
96 45436
Votre programme doit s'exécuter dans un délai raisonnable. Ma solution s'exécute en quelques secondes sur le dernier exemple.
Le code le plus court gagne.
Incluez le temps d'exécution et votre sortie pour le dernier test.
EDIT : Ce problème n'est pas destiné à être forcé par une brute, donc une solution triviale n'est pas acceptable.
Réponses:
Python,
221239caractèresConserve
F
une liste non triée de triplets (début de parcours, fin de parcours, couleur) représentant l'état actuel de la clôture. Étant donné que la peinture aléatoire dans le générateur repeint de larges bandes assez fréquemment, cette liste n'est jamais trop longue (généralement entre 15 et 40).Fonctionne en 37 secondes sur l'exemple 1M.
la source
G+=[(a,min(b,s),d)]*(a<s)
etc. pour obtenir la boucle for sur une lignefor C in sorted(f[2] for f in F):print C,sum(b-a for a,b,c in F if c==C)
enregistre quelques caractères sur vos quatre dernières lignes et évite d'avoir à connaître le nombre magique 98.sorted(set(...))
ce soit ce qui n'est plus une amélioration.Haskell, 251
261269294caractèresQuelque chose ne va pas tout à fait bien car cela prend beaucoup trop de temps et de pile ... Mais cela produit les bonnes réponses:
replicate
etgroup
est tout aussi efficace pour compter la peinture et prend moins de code que la fonction personnalisées
max
appelerf
la source
Perl - 148 octets
Il semble que Perl soit le meilleur pour jouer avec. facile à coder plus court et plus rapide. ;)
code:
temps:
la source
la source
JavaScript, 183 caractères, 1,3 seconde
Malheureusement, j'ai dû couper la partie stdin / out de l'exigence, que JavaScript ne prend pas en charge. Au lieu de cela, j'obtiens l'entrée d'un téléchargement de fichier à la
<input>
place (que je ne compte pas dans mon nombre de caractères, bien que je devrais probablement le faire).Voici la version non golfée. C'est une fonction qui prend la chaîne d'entrée complète ... tous les 14 Mo! C'est celui qui prend 1,3 seconde; la version golfée prend environ deux fois plus de temps - mais elle bat toujours les autres solutions! Fait intéressant, il est deux fois plus rapide dans Firefox que dans Chrome. Démo en direct ici .
Et voici la version golfée.
la source