http://nabetani.sakura.ne.jp/hena/ord20meetime/
http://qiita.com/Nabetani/items/5791f8ae1bb5d069a49b
Je pense que cela a pris environ une heure et demie, temps de correction compris, parce que j'étais accro à une mauvaise lecture du problème (mauvaise gestion de MM. I et J). Même si je ne pouvais pas me concentrer sur sa création en voyageant en train, je pense que je ne pourrais pas y arriver à temps même si je l'ai fait localement.
time2min = lambda t: int(t)/100*60 + int(t)%100
reserve = lambda r: bin(1<<24*60 | r)[3+10*60:3+18*60].find("1"*60) + 10*60
def solve(data):
A = B = I = J = Z = R = (1<<24*60)-1
for d in data.split(","):
start, end = map(time2min, d[1:].split("-"))
exec(d[0]+" &= "+str(~R>>start | R>>end))
r = min([r for r in map(reserve, (A&B&I&~Z, A&B&J&~Z)) if r >= 10*60] or [-1])
return "-" if r < 0 else "%d%02d-%d%02d"%(r/60, r%60, r/60+1, r%60)
def test(data, correct):
answer = solve(data)
print "xo"[answer == correct], data, correct, answer
0, test( "A1050-1130,B1400-1415,I1000-1400,I1600-1800,J1100-1745,Z1400-1421,Z1425-1800", "1425-1525" );
1, test( "A1000-1200,B1300-1800,Z1000-1215,Z1230-1800", "-" );
2, test( "Z0800-2200", "1000-1100" );
3, test( "A1000-1700,Z0800-2200", "1700-1800" );
4, test( "A1000-1701,Z0800-2200", "-" );
5, test( "A1000-1130,B1230-1800,Z0800-2200", "1130-1230" );
6, test( "A1000-1129,B1230-1800,Z0800-2200", "1129-1229" );
7, test( "A1000-1131,B1230-1800,Z0800-2200", "-" );
8, test( "A1000-1130,B1229-1800,Z0800-2200", "-" );
9, test( "A1000-1130,B1231-1800,Z0800-2200", "1130-1230" );
10, test( "A1000-1130,B1230-1800,Z0800-1130,Z1131-2200", "-" );
11, test( "A1000-1130,B1231-1800,Z0800-1130,Z1131-2200", "1131-1231" );
12, test( "Z0800-0801", "-" );
13, test( "Z0800-1031,Z1129-1220,Z1315-1400,Z1459-1600", "1459-1559" );
14, test( "Z0800-2200,I1000-1600,J1030-1730", "1600-1700" );
15, test( "Z0800-2200,I1000-1600,J1130-1730", "1000-1100" );
16, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1025", "1025-1125" );
17, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645", "1645-1745" );
18, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645,I1735-2200", "-" );
19, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645,J1735-2200", "1645-1745" );
20, test( "Z1030-2200,I1000-1600,J1130-1730", "1030-1130" );
21, test( "Z1035-1500,I1000-1600,J1130-1730,Z1644-2200", "1644-1744" );
22, test( "I2344-2350,A2016-2253,Z1246-1952", "1246-1346" );
23, test( "Z2155-2157,B1822-2032,Z1404-2000,Z2042-2147,Z2149-2154", "1404-1504" );
24, test( "Z2231-2250,Z2128-2219,B2219-2227,B2229-2230,Z0713-2121,A0825-1035,B1834-2001", "1035-1135" );
25, test( "J0807-1247,I0911-1414,B1004-1553,Z0626-1732,Z1830-1905,A1946-1954,A0623-1921", "-" );
26, test( "J1539-1733,J0633-1514,Z1831-1939,J1956-1959,I0817-1007,I1052-1524,Z1235-1756,Z0656-1144", "1524-1624" );
27, test( "Z2319-2350,B0833-2028,I2044-2222,A1410-2201,Z2044-2228,Z0830-2023,Z2242-2306,I2355-2359", "-" );
28, test( "B2001-2118,Z0712-1634,I1941-2102,B1436-1917", "1000-1100" );
29, test( "A0755-1417,B2303-2335,Z0854-2150,Z2348-2356,Z2156-2340,I1024-1307,Z2357-2359", "1417-1517" );
30, test( "A1958-1959,B0822-1155,I1518-1622,Z1406-1947,A1800-1822,A0904-1422,J1730-1924,Z1954-1958,A1946-1956", "1422-1522" );
31, test( "B1610-1910,I2121-2139,A0619-1412,I2147-2153,Z0602-2111,I0841-2031,A1657-1905,A1956-2047,J0959-1032,Z2131-2147", "1412-1512" );
32, test( "Z0623-1900,A0703-1129,I1815-1910,J1956-1957,I0844-1518,Z1902-1935,B1312-1342,J1817-1955", "1129-1229" );
33, test( "J1246-1328,B1323-1449,I1039-1746,Z1218-2111", "1449-1549" );
34, test( "A1958-1959,I1943-1944,I0731-1722,Z0845-1846,J1044-1513,Z1910-1923,B1216-1249", "1513-1613" );
35, test( "A1855-2047,Z0946-1849,Z2056-2059,I1855-1910,B1946-2058,I1956-2025,Z1905-2054,J0644-1800,I0720-1618", "1618-1718" );
36, test( "J1525-1950,Z0905-1933,A1648-1716,I2051-2054,I2015-2044,I0804-1958,B0934-1100,Z1953-2037", "1100-1200" );
37, test( "Z1914-1956,J0823-1610,Z0641-1841,J1800-1835,A0831-1346,I1926-1941,I1030-1558,I1738-1803", "1558-1658" );
38, test( "Z0625-1758,J1033-1351,B1816-2236,I0838-1615,J2247-2255", "1351-1451" );
39, test( "J0603-1233,A1059-1213,I1326-2103,Z0710-1459", "1213-1313" );
40, test( "B1302-1351,J1410-2038,A0755-1342,J0637-0658,Z2148-2159,Z1050-2131,A1543-1844,I1615-1810", "1351-1451" );
41, test( "Z0746-2100,A2122-2156,I1022-1144,J0947-1441,A1333-1949", "1144-1244" );
42, test( "J0718-1243,Z1443-1818,B2055-2057,A0714-1238,Z1045-1344,A1643-1717,B1832-2039,J1623-1931", "1238-1338" );
43, test( "Z1921-1933,A1208-1418,I0827-1940,Z0757-1917,J0653-1554,B1859-1909", "1554-1654" );
reserve = lambda r: bin(1<<24*60 | r)[3+10*60:3+18*60].find("1"*60) + 10*60
Il s'agit d'une définition de fonction de réserve qui recherche le programme de 10h00 à 18h00 pendant 60 minutes de temps libre continu et renvoie l'heure de début. L'horaire de chaque personne est constitué de données bitmap d'une minute, et les données bitmap r qui produisent logiquement l'horaire de chaque personne sont transmises. Utilisez la fonction bin pour convertir les données bitmap de planification en une chaîne binaire, qui est une chaîne d'une minute de "1" si la planification est gratuite et "0" si elle est planifiée. La raison pour laquelle 1 << 24 * 60 est logiquement additionné est que si le programme est programmé à partir de 0 heure, le 0 de début sera supprimé par la fonction bin et il ne sera pas de 24 * 60 caractères pendant 24 heures, donc c'est définitivement 24 * Pour obtenir 60 caractères, 1 << 24 * 60 est additionné logiquement et converti en une chaîne binaire de 24 * 60 + 1 caractères. Puisque la chaîne de caractères binaires est constituée de données bitmap de 0:00 à 23:59, la partie de l'heure de réunion de 10:00 à 18:00 est coupée avec [3 + 10 * 60: 3 + 18 * 60]. Ce qui est 3+, c'est que "0b" est ajouté au début du résultat de la conversion par la fonction bin, et 1 << 24 * 60 ajoute un "1" supplémentaire, pour un total de 3 caractères. Utilisez find ("1" * 60) pour rechercher la pièce qui a un programme gratuit pendant 60 minutes consécutives. S'il n'est pas trouvé, ce sera -1. Puisqu'il est trouvé à partir de la chaîne de caractères binaires coupée après 10h00, 0 est renvoyé s'il est trouvé pendant 60 minutes à partir de 10h00 et + 10 * 60 est renvoyé pour renvoyer les données d'heure à 10h00. .. Si aucun temps libre n'est trouvé, -1 + 10 * 60 renvoie 9:59.
A = B = I = J = Z = R = (1<<24*60)-1
(1 << 24 * 60) -1 crée des données bitmap dans lesquelles 24 * 60 1 bits sont organisés. Un bit représente un rendez-vous d'une minute. Les horaires de M. A, M. B, M. I, M. J et M. Z sont initialisés avec des données bitmap dans lesquelles 24 * 60 1s indiquant qu'ils sont libres pendant 24 heures sont alignés. R est utilisé dans le calcul pour rendre la partie horaire planifiée de chaque personne 0.
exec(d[0]+" &= "+str(~R>>start | R>>end))
Si les données d'entrée sont "A1050-1130", calculez A & = (~ R >> (10 * 60 + 50) | R >> (11 * 60 + 30)). Chaque bit dans la plage de 10:50 à 11:30 des données bitmap de programme de M. A sera 0, ce qui représente planifié.
r = min([r for r in map(reserve, (A&B&I&~Z, A&B&J&~Z)) if r >= 10*60] or [-1])
Dans A & B & I & ~ Z, le temps libre de Mr. A, Mr. B et Mr. I et le temps programmé (bit inversion) de Mr. Z sont logiquement multipliés. Cela vous donnera des données bitmap de planification pratiques pour 4 personnes. Étant donné que M. I ou M. J devraient être présents du début à la fin, nous demandons également les données bitmap du calendrier de A & B & J & ~ Z. Trouvez l'heure de début antérieure avec min (map (reserve, (A & B & I & ~ Z, A & B & J & ~ Z))) équivalent à min ([reserve (A & B & I & ~ Z), reserve (A & B & J & ~ Z)]). Cependant, si aucun temps libre n'est trouvé, la fonction de réserve renverra les données à 9:59 et 9:59 sera sélectionnée, donc si r> = 10 * 60 à 10 heures en utilisant la notation d'inclusion. Seules les données suivantes sont extraites. S'il n'y a pas de temps libre dans les deux cas, ce sera une liste vide [], et min ([]) entraînera une erreur, donc s'il s'agit d'une liste vide, min ([-1]) sera calculé ou [-1]. Je vais.
Recommended Posts