{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", " \n", "Дед Мороз принес детям конфеты. Каждому из присутствующих он может дать не более одной конфеты. На елку пришли разные дети, и аппетиты у них тоже разные. Аппетиты каждого ребенка задан списком `appetite`. Конфеты у деда Мороза тоже разные, их вес задан списком `weight`. После новогоднего утренника ребенок с аппетитом `appetite[i]` становится счастливым, если вес полученной им конфеты `weight[j]` больше или равен его аппетиту, то есть `weight[j]>=appetite[i]`.\n", "\n", "---\n", "\n", "Даны два списка: `appetite` и `weight`. Напишите функцию `max_happy(appetite, weight)`, вычисляющую максимальное количество детей, которых может осчастливить дед Мороз. \\\n", "При разработке не забудьте учесть два крайних случая: дети вообще не пришли (список `appetite` пуст), дед Мороз пришел без конфет (список `weight` пуст).\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "def max_happy(appetite, weight):\n", " pass" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## Раздел тестирования" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "assert max_happy([1,2,3], [1,1]) == 1, \"test1\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пояснение**: хотя у деда Мороза две конфеты, \n", "сделать счастливым он может только одного ребенка с аппетитом 1." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "assert max_happy([1,2], [1,2,3,4]) == 2, \"test2\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пояснение**: сделать детей счастливыми можно разными способами, например, каждому дать конфету, вес которой совпадает с его аппетитом. \\\n", "Но больше двух детей не осчастливить, потому что их всего два." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [], "source": [ "assert max_happy([], [1,2,3,4]) == 0, \"test3\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пояснение**: дети не пришли" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "assert max_happy([1,1,1,1], []) == 0, \"test4\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Пояснение**: Дед Мороз забыл принести конфеты" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "\n", "**Теперь случай больших коллективов детей**\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [], "source": [ "# 11121 ребенок, 73 конфеты\n", "a = [1226,312,534,981,249,968,420,1359,955,641,1285,992,564,434,128,354,583,395,1360,1211,1242,801,90,473,688,850,136,963,518,261,1235,875,1424,71,928,1172,487,1024,1413,415,702,880,678,950,902,308,1527,181,897,37,739,425,1334,914,1549,822,806,771,55,818,426,1065,871,1212,110,269,721,502,826,909,90,1319,69,1458,1010,649,1076,1216,399,513,384,973,1237,941,348,782,888,564,349,371,49,1086,501,590,273,1277,171,675,384,737,607,1324,70,1471,1503,604,85,1424,1139,1438,939,1224,400,322,222,1522,295,339,1135,1265,869,938,456,1282,56,629,1488,1018,1320,1491,1025,668,873,1162,61,149,511,468,330,1197,372,176,1115,519,1477,801,360,1305,66,921,186,1002,1526,834,669,1022,201,209,1107,954,1160,503,128,209,845,598,481,960,470,1391,1398,647,1132,612,1173,758,325,45,505,46,969,918,592,1105,685,465,1185,1369,1297,1000,32,339,663,1538,624,534,1281,1540,561,875,318,989,150,1416,1212,1163,539,984,1437,1403,491,890,1393,221,1376,1496,852,730,1019,511,1051,64,351,751,1457,1481,1360,214,1211,215,1376,957,1092,91,1470,861,1063,46,1288,230,548,1176,636,1495,593,342,269,1480,101,918,870,857,1415,430,1313,1296,124,1404,957,1265,1414,1278,504,763,1171,950,278,1495,850,786,554,951,1432,535,245,1550,861,1214,343,440,1258,690,831,401,534,348,1508,1359,1408,1066,792,178,1002,398,1056,771,55,1274,1497,1066,304,259,644,1404,311,1018,1433,1492,1154,1439,646,406,1541,1253,466,334,546,1325,280,134,766,1529,584,181,1401,1096,1544,867,381,75,226,696,1145,1093,841,188,1343,223,574,655,1399,1269,1196,1318,308,1410,1155,969,443,444,469,1497,1227,487,620,322,124,930,1276,806,389,766,545,304,1472,160,1137,244,768,1112,1347,317,929,1168,427,641,1218,992,1252,1530,968,1215,893,654,688,1249,977,85,1505,615,419,981,117,741,1175,741,968,884,794,894,908,808,1542,1393,456,563,1367,622,556,1114,183,1529,489,361,615,1157,1088,193,237,580,417,677,1377,801,863,77,390,475,1254,452,1175,448,788,344,944,180,110,1463,327,162,525,1306,342,1429,72,78,302,237,1175,716,643,1535,1423,391,36,790,1032,1316,1121,665,1336,472,625,1210,745,955,160,891,994,1086,39,1130,656,566,1013,180,1138,1096,979,898,1347,694,782,377,187,1328,1115,526,1527,328,33,588,237,333,1213,281,766,1450,1019,687,133,1229,414,1433,657,558,1549,606,1006,1541,938,787,400,1255,358,744,1309,1104,1069,792,560,1311,290,1350,426,472,139,644,1295,1547,727,526,854,976,56,1139,509,610,1470,785,775,446,40,581,256,1194,517,184,995,183,791,473,232,176,453,944,1107,984,1506,348,1313,568,348,1279,1309,956,1102,986,1494,144,821,551,130,1027,64,1283,1246,1416,1548,118,1361,1003,265,1119,1175,1417,1003,145,345,1130,593,633,1483,500,865,714,1399,1373,69,383,390,438,1413,955,200,362,28,1120,1142,560,978,407,1335,1098,1353,1477,1203,902,270,289,1197,258,589,1183,91,299,154,846,337,1457,1250,1177,823,311,1218,341,688,1216,1410,837,59,583,980,1160,522,856,1234,209,49,142,731,57,1493,327,1377,643,759,281,274,822,877,166,1333,984,1059,1316,1163,876,665,772,974,30,901,1074,272,1469,669,613,1081,309,1327,1258,1315,190,702,500,217,622,629,361,1490,1321,680,1293,1083,187,416,857,526,63,738,820,891,202,83,1120,614,538,256,766,245,1067,1196,694,449,640,144,120,188,1258,968,73,1095,752,40,878,732,1228,1057,1120,1415,1184,1251,919,1311,1105,520,298,1249,1437,496,1342,1431,241,106,94,451,1008,1080,1432,255,1416,1403,610,1170,1275,112,356,397,956,470,1018,102,1231,1203,380,39,1318,480,1012,1549,843,981,1314,840,1156,723,342,795,848,123,174,1409,1112,567,704,232,593,376,1185,338,838,860,186,1468,1348,281,1140,731,1151,1311,1256,402,1489,999,970,999,380,395,63,265,1213,388,670,925,1066,1016,102,241,487,603,215,197,268,1517,493,252,280,1038,1249,1382,1445,758,875,789,979,419,1304,1326,127,77,1099,837,752,38,1169,143,1149,140,286,1474,744,1428,1012,1378,601,867,574,29,705,602,943,189,559,471,889,1429,1262,617,895,588,1182,313,1323,885,1392,373,1325,501,323,1245,1212,1485,298,1002,638,1425,686,1373,1039,931,640,883,1310,857,882,266,58,1367,1380,351,659,1185,1214,490,1535,37,786,1347,1308,706,364,369,1491,365,1394,1528,622,681,1088,1418,1042,651,900,387,980,670,1168,796,1420,1193,498,1349,986,279,938,621,959,50,1141,624,676,1299,1063,1475,926,792,562,408,855,1309,1049,143,1254,852,1047,1484,1038,346,410,473,592,1189,571,178,705,289,362,938,286,1171,1072,1334,1292,1157,1432,1416,1406,603,1266,1039,378,1249,1003,979,683,388,1290,1224,993,1298,1317,1198,1359,429,669,327,1002,515,400,616,409,1170,1048,263,644,1133,882,742,944,490,1541,249,119,1204,562,674,945,45,561,960,289,1422,782,595,1054,969,638,786,1066,389,931,615,1256,1198,385,1299,421,1115,884,662,1297,53,1385,1478,1400,1422,831,683,538,55,464,804,1265,1201,886,1444,386,1546,128,901,1235,752,870,1466,1199,612,265,300,1466,1299,85,485,1466,764,1288,238,1278,483,1451,149,565,1099,432,499,44,136,288,460,1235,118,443,643,79,520,518,997,1483,1030,68,603,1458,850,588,1456,43,1268,553,90,1140,1237,41,325,1202,1006,505,363,1265,696,616,1053,1082,140,109,260,1255,518,632,1090,570,936,789,1455,210,602,1141,1005,1316,641,499,196,100,793,379,153,1517,474,27,1538,167,968,1251,1185,369,1543,1095,216,1371,1138,909,764,1302,1199,1198,1063,834,1147,704,1126,1075,709,506,113,1276,141,358,96,1199,895,1047,33,944,1522,754,806,1174,249,1533,311,1412,1367,648,921,660,1121,256,1015,269,92,1424,343,56,292,1362,850,943,1019,445,927,552,1084,949,330,1165,1249,367,153,69,695,155,1393,217,1122,158,1424,558,1447,186,1472,509,589,492,782,1076,129,144,536,918,1352,347,1274,1362,231,171,451,759,412,156,644,132,562,1428,848,482,1431,660,1138,284,811,949,1023,1517,409,1202,800,364,262,280,365,1321,454,238,584,1372,35,566,965,1149,1478,685,1394,216,534,853,327,41,1196,466,49,380,503,874,344,375,173,280,1178,628,59,977,772,539,649,528,575,1517,442,143,1274,732,1168,1351,764,702,45,1141,60,140,232,1259,693,1053,908,355,1354,1153,1416,176,972,953,1256,1292,1315,1468,1056,651,380,439,122,842,1137,212,551,807,116,1030,118,1481,1237,980,40,572,1098,903,1492,880,1233,568,1456,243,680,972,558,1026,1399,949,505,1353,1220,1235,441,81,341,169,465,132,946,1401,806,402,277,1097,1183,519,1175,56,364,629,1042,1164,319,1007,1220,341,473,1052,234,807,1396,836,528,96,1076,304,895,1076,745,1109,1460,1473,1513,140,936,175,979,1070,1472,1216,265,1417,129,567,599,720,978,617,739,378,223,550,1481,287,1168,1041,1173,810,388,1403,36,1319,109,427,128,1368,874,653,1208,1288,248,264,736,160,895,1339,845,50,312,69,1514,615,668,491,1160,118,92,112,775,1109,908,109,933,1258,842,801,561,385,832,1345,717,520,851,1142,1233,1359,1295,701,256,1058,617,325,1067,486,1244,178,203,1194,1314,407,1159,1439,1297,1298,451,1540,1122,269,973,29,952,665,1402,686,348,360,1469,408,991,1206,719,963,77,518,941,562,562,62,1397,58,1075,1180,52,772,947,143,1092,131,1150,1124,428,524,122,737,604,551,344,781,711,359,1043,800,1391,875,315,1430,1228,409,935,442,1185,962,146,884,1427,111,1485,1052,1479,86,251,1108,668,788,149,1368,955,1527,912,1404,396,632,502,27,891,1538,1518,1158,1009,925,1198,1171,943,577,652,1348,490,455,510,1051,42,1137,686,581,1167,1312,1147,458,1220,1273,556,839,358,941,1412,74,189,1460,635,1522,1362,832,75,460,1241,1121,1209,732,1421,546,1395,925,1151,545,1529,388,1047,1426,472,355,1503,1051,1468,82,284,1182,1324,1329,682,44,1143,816,866,674,185,1332,1551,1328,249,954,1180,1294,1292,1249,939,921,1058,1066,341,243,1107,91,873,99,892,220,1250,825,279,375,580,370,242,1044,1325,1090,197,1177,1078,130,1084,403,738,1434,112,1111,1429,1483,1174,1141,37,1242,486,332,639,594,417,811,821,1182,1247,1295,610,65,99,235,1427,884,1493,1529,135,570,1322,1110,374,669,357,310,993,568,1476,1487,239,987,843,1158,811,669,1464,1281,981,190,1006,122,153,270,1321,1285,507,726,804,1363,860,491,1303,1320,151,537,963,674,617,949,593,984,63,343,951,1452,100,480,780,876,1175,989,1405,1047,1486,1070,1435,821,359,1061,420,1275,1092,831,546,811,1496,26,1114,386,1192,393,573,947,583,1031,372,241,722,235,919,464,1336,655,225,691,381,987,1171,386,672,264,518,736,514,420,590,507,1316,306,142,317,581,1314,226,68,145,161,490,923,1508,334,1531,440,1319,661,1210,1089,445,283,1319,995,803,1442,991,1005,604,1401,1299,49,1412,1493,1507,351,275,657,157,1191,856,850,1338,1510,186,1197,724,172,567,689,329,760,933,410,447,301,1264,237,1124,109,1081,588,419,811,741,1173,518,871,1480,671,1350,813,1210,195,1163,787,1032,1377,849,944,1130,302,512,604,466,1089,1385,1464,1324,1197,681,210,144,1067,424,909,313,388,526,659,1168,660,1475,1120,1334,1452,625,315,340,425,86,288,1136,1083,1257,1510,1024,225,380,761,136,783,1020,939,251,793,652,78,1403,1383,909,1290,1004,847,100,470,835,1538,1229,423,528,1256,1535,1206,442,395,512,1334,827,1029,747,1445,196,1094,1285,1375,700,243,1241,311,497,500,63,586,351,169,647,907,921,868,233,1499,1483,84,648,83,645,1290,49,641,216,426,319,68,62,34,1071,107,99,157,633,337,1524,1492,965,1134,161,1486,141,1429,1146,1389,260,445,499,738,188,94,1251,1517,1059,1029,995,469,1196,1496,1304,332,89,1152,116,380,1225,54,95,186,1266,1550,360,1057,1480,185,69,1055,526,95,196,1466,1232,1293,716,1097,1115,288,908,1218,1389,640,687,1445,1517,1396,1471,515,1367,1312,1327,311,178,524,320,1542,1393,1415,1444,368,432,266,990,1112,431,1255,189,416,238,422,280,1129,825,641,257,1550,716,724,441,865,838,1246,529,1389,621,1092,567,200,633,1163,436,101,237,177,601,487,1196,1348,1390,1242,576,1364,558,967,1464,58,345,290,98,1473,444,1495,286,1525,1134,982,1407,697,1228,893,632,387,914,1487,1302,1322,784,233,148,1180,1285,179,927,977,62,27,695,916,83,153,599,1432,546,1460,255,738,804,734,840,86,1396,1545,1442,655,1330,1181,304,718,717,591,396,1212,1158,277,644,803,1423,1538,1430,762,1404,599,1255,753,959,657,747,397,871,284,373,1503,1308,690,1429,1201,758,1189,1253,526,1274,919,491,756,1372,331,876,1425,779,1378,1126,896,56,1317,1433,707,744,923,1293,365,361,816,137,885,487,854,1114,1086,1522,104,406,599,1049,1240,781,1021,838,1510,189,508,1443,938,939,1551,1091,353,884,242,305,901,846,1080,1331,70,559,509,1452,809,59,347,123,763,690,76,222,1401,110,277,1074,237,802,1026,554,57,271,561,1113,1346,82,1155,640,177,513,890,316,751,60,1133,431,444,760,893,264,1539,1279,453,872,1121,1506,1220,1429,672,136,1338,1208,1071,800,691,912,95,267,1450,1105,1272,1069,370,394,779,1269,364,1470,971,1118,1128,442,1101,881,736,958,448,1075,1509,1495,223,157,1130,672,1447,1230,944,178,1379,772,882,1082,480,181,422,1216,1428,516,1085,1077,422,1013,1069,1538,1424,483,1223,461,1074,808,948,207,1001,280,318,94,1057,337,316,1361,1466,477,400,960,224,990,1032,174,1330,115,1209,962,249,402,131,291,1212,866,434,1018,1293,723,460,1334,1474,514,366,1417,361,212,981,647,1268,331,579,810,1500,698,1409,1323,995,1462,165,1202,1481,589,203,999,440,863,1189,349,688,738,26,1067,420,1258,1010,1109,346,1127,536,959,1166,1325,256,760,26,316,113,908,490,204,968,248,1467,722,1298,1344,1142,409,1010,838,1086,1035,927,1466,944,73,1416,801,976,189,996,1193,126,376,149,667,225,789,261,342,1358,1456,259,473,1144,989,138,1165,1227,925,407,580,1229,1484,1285,1522,270,442,713,1425,239,1119,807,136,941,374,1465,891,1132,782,1232,1123,1191,407,1003,241,1262,115,286,1244,1256,836,451,335,826,1341,1134,182,858,165,1068,1272,933,1542,29,780,570,588,1044,1244,475,1453,1432,415,1174,1381,1239,1128,131,304,240,519,579,1096,33,286,1414,228,892,158,692,487,603,1373,970,1207,503,1177,815,1260,1544,311,1087,1415,945,955,375,81,1284,880,1197,448,279,902,165,1005,1446,670,115,430,186,130,708,877,454,1177,1181,1003,947,1493,429,46,193,1346,1532,934,1348,31,903,453,1010,1431,506,1461,370,1318,403,303,617,1055,1117,1538,1382,744,1411,1276,1407,957,832,198,1227,1382,183,1536,287,655,834,270,1364,614,1278,1492,413,234,1266,465,264,342,945,565,622,701,26,631,725,979,1409,1165,670,772,823,100,1398,444,1297,914,1480,776,1543,811,428,1409,1108,43,154,418,1452,233,293,716,1349,1031,230,70,79,1390,299,212,1331,1046,1074,138,811,438,1370,418,1103,443,908,1058,376,905,130,708,955,691,1165,937,553,571,105,265,858,840,234,265,1495,39,1386,1543,1132,1181,816,1089,1353,658,1305,1085,796,339,142,788,444,477,777,1041,1475,1004,1276,161,129,1101,1362,947,1233,941,577,529,1428,1003,1301,179,665,118,1369,156,650,1042,1125,1313,789,632,65,364,1036,228,333,281,1230,533,65,268,1194,98,1511,197,695,159,1090,49,535,1359,1057,1416,606,1306,1446,1196,1067,264,1112,1426,998,1205,587,756,879,193,1122,89,935,876,214,567,1302,946,117,405,623,1251,1367,322,529,411,51,695,1081,1465,977,716,1155,419,26,777,121,523,74,1001,512,1396,694,158,975,606,594,1052,274,1398,1446,355,1055,1247,1448,703,432,174,550,1088,792,585,889,789,1058,943,1100,1088,1340,93,887,894,629,1518,307,111,1437,71,726,35,866,435,76,1397,1032,947,1340,373,956,674,1298,929,74,1355,1148,1469,604,506,600,1169,539,776,1130,1162,54,914,1404,425,995,496,813,798,1040,1373,603,1106,446,324,1543,1114,1240,325,101,1319,193,324,1184,705,1123,1105,1510,1194,560,829,110,1342,1507,1109,1003,760,948,1093,258,781,141,1399,1483,927,497,492,623,149,1422,1174,1345,584,703,608,976,985,972,345,1234,1172,1106,626,1392,87,1141,372,1529,1321,1282,1136,44,701,459,943,1460,154,936,824,1463,148,357,740,578,271,1312,26,1280,1438,888,1446,1067,669,974,1297,202,1135,723,605,1378,807,418,239,303,495,62,472,100,712,903,593,1277,374,79,854,578,1454,864,1476,947,1121,324,564,1429,439,495,1125,398,177,1496,721,451,1115,431,1115,488,975,765,1053,661,870,522,1357,1215,497,512,1289,1081,621,1466,1326,1034,1391,989,297,687,431,910,681,789,1326,510,858,534,392,645,1234,544,486,309,310,1253,781,392,668,826,634,623,668,1415,733,539,670,684,536,558,1486,494,225,1352,164,47,597,1402,1239,860,834,1165,162,1297,619,1455,1355,661,1081,859,77,957,464,1442,151,276,419,1472,1368,1165,1255,467,490,1423,1236,1289,1320,1268,1490,1527,996,352,652,394,1130,641,955,966,445,1249,529,320,978,29,1269,1359,273,432,1487,811,742,78,154,589,1292,256,207,1257,541,854,1217,413,1527,1291,205,121,666,226,1081,532,1218,1448,556,1147,876,467,365,1186,299,1205,1291,399,756,1496,254,269,1194,922,403,704,866,163,352,850,331,1092,1105,1037,264,144,498,606,213,502,873,121,605,209,1429,1347,296,1496,379,1457,602,114,1303,910,436,874,351,455,369,1403,765,1430,1518,30,1456,432,169,135,733,705,122,489,1096,481,454,663,192,1366,1171,144,839,807,1047,1522,1006,1357,1496,686,237,1354,762,272,1392,1309,830,405,1427,320,145,1394,966,517,111,480,1317,979,153,723,1498,182,1256,1310,121,977,508,833,1541,277,596,1475,53,1419,192,918,1143,1132,1208,573,786,407,180,509,623,344,799,1072,341,848,1439,1132,1156,832,1448,310,107,191,156,966,1122,1440,402,1041,196,1385,1231,205,822,133,284,892,31,836,119,125,1359,1038,598,1166,731,754,1290,921,1069,891,1042,1465,1433,519,657,736,693,1351,1012,993,355,1061,275,344,915,226,1085,498,1242,1170,543,1324,556,1114,469,752,1482,898,1192,182,727,807,453,265,1245,279,1542,992,829,1178,267,672,748,1124,889,71,149,1453,127,222,91,454,631,459,1005,871,1371,1016,643,559,329,294,798,347,283,509,694,1119,849,264,1246,95,845,945,966,222,297,504,1055,1059,1099,550,1178,907,860,720,1529,656,1124,385,767,1273,836,484,150,1066,1109,924,1544,408,503,585,547,1035,1082,820,654,939,86,1468,144,1270,177,333,523,1429,962,867,51,658,1125,605,1381,1149,1106,59,986,1210,1106,1115,818,433,233,1393,775,1018,1281,711,1229,236,925,1421,1423,1548,589,815,492,290,1290,38,581,1134,462,473,814,1269,974,1152,850,951,460,815,869,773,232,1270,680,211,1475,132,1182,1329,879,253,1328,1361,526,1538,366,705,1341,1537,1227,864,638,85,57,320,513,1383,106,1017,1220,407,110,996,287,1471,1080,1456,416,1447,103,1251,881,1414,821,1442,739,913,982,917,784,906,287,1322,881,492,205,1393,640,866,1405,407,948,1040,781,1013,628,1327,355,781,1278,1019,567,615,446,730,568,1424,146,1550,793,1396,517,1310,658,581,1358,554,1107,885,1195,213,1293,1116,1235,937,213,39,1347,103,133,1465,641,644,428,304,697,928,1226,338,1345,300,545,465,430,1545,807,1455,764,271,754,1288,1042,1251,952,432,1310,1078,1000,130,781,311,805,43,802,438,75,1078,363,1325,593,362,644,218,292,247,299,320,411,782,1105,930,1461,787,1439,1182,657,1463,835,1475,1300,779,854,1152,630,1058,139,915,503,277,381,185,1404,1009,949,676,405,960,726,879,1505,41,590,547,265,362,1271,1526,476,1240,65,313,601,730,900,134,922,51,1251,290,575,768,1376,156,566,541,1041,1127,625,1368,1179,761,423,141,1247,267,1197,459,37,1334,87,1302,1195,1164,883,1149,67,540,552,741,1029,420,382,91,664,1488,1380,280,503,1399,427,1039,783,389,1326,507,216,505,967,360,1274,1126,1440,1131,373,304,1471,1095,1411,433,647,722,1207,971,196,1433,833,975,1528,1284,31,1092,905,1203,1006,620,359,515,220,413,432,1278,1040,1525,30,555,932,1540,586,74,247,602,1376,124,1452,135,672,756,205,962,1353,64,1061,1282,895,1112,594,1503,1241,353,1229,103,831,1088,41,1470,71,1249,1457,915,906,269,784,753,813,219,852,510,506,85,710,283,356,1085,1387,64,367,797,1177,429,246,688,1346,418,828,440,1003,1324,925,333,1303,641,1192,103,1058,1444,1396,1262,914,1260,106,756,305,979,1480,1498,1405,1314,1274,328,1255,625,1014,209,792,360,1244,743,469,405,289,1062,804,1476,995,730,604,1085,465,427,1517,1525,1374,497,664,1503,1459,1024,332,1259,1167,1119,1283,1407,1506,562,1003,1327,1496,56,1459,495,460,829,87,1211,375,590,1140,1140,752,426,628,67,175,154,1224,799,1238,648,1356,1376,1111,633,75,323,33,342,1533,1551,1356,515,1471,51,394,1550,654,164,480,918,849,813,562,1105,731,231,411,622,1097,690,1257,226,1411,887,1071,901,1085,637,205,1447,1274,1539,1535,857,539,864,1338,422,804,1494,1102,255,1137,643,1083,1173,1275,831,27,648,491,1087,1122,1334,600,1449,83,849,29,443,283,173,187,626,175,211,269,1116,866,829,1022,1045,566,962,53,69,1272,1218,910,757,844,58,1111,944,1127,1459,108,47,470,650,103,333,571,375,921,1082,1539,561,1103,1096,1209,1413,233,1127,1202,1375,792,766,966,133,1248,1187,350,470,741,950,774,540,239,805,1404,424,1018,1247,148,1323,1396,43,1404,682,1457,1206,424,60,162,547,186,321,427,1285,1061,1521,740,44,40,867,964,912,805,411,1033,324,654,1032,717,368,989,131,898,1264,1208,1517,1168,1161,919,313,128,309,1278,1165,532,1527,551,171,508,461,1125,269,1395,621,591,159,879,1541,741,1538,832,102,431,796,1421,26,927,1522,849,959,745,656,1466,885,962,672,523,127,1472,617,734,258,843,999,847,368,1386,447,1110,316,1392,717,1063,90,908,695,109,1400,593,674,1536,166,426,1550,857,1286,115,1356,1152,1086,1524,1106,127,340,877,849,281,1114,906,1436,127,1328,730,111,1011,869,269,1157,1390,906,946,780,929,1128,739,711,125,49,519,891,1281,669,1467,1212,700,1084,1016,626,1149,61,486,586,227,834,232,1269,332,855,921,82,1065,220,209,375,542,647,1329,1210,325,1530,1224,1112,713,685,1267,1301,82,1274,995,1100,693,141,1343,1075,1448,642,569,687,1328,136,548,698,86,780,1115,36,789,1498,1500,908,853,141,575,851,292,408,1512,763,789,1492,1052,1083,540,865,453,873,1491,338,279,1009,1356,417,403,1320,1266,1170,492,368,514,1324,488,276,333,348,607,116,245,1080,70,1017,746,535,952,978,1064,911,1283,1337,410,985,1275,561,249,648,518,578,1040,396,1130,585,203,142,305,829,832,512,1447,475,62,1456,323,141,1487,712,244,1439,1456,1378,1055,1534,1274,1396,675,1420,1484,1449,818,359,750,456,454,1239,735,207,1367,166,648,403,556,1474,248,1274,424,1382,1347,751,993,246,758,1279,705,750,997,1049,519,1250,127,765,242,164,634,312,816,846,711,1310,1084,537,287,123,512,733,635,1074,48,784,284,640,1063,162,1469,64,383,751,1445,634,488,546,412,1372,881,64,1230,610,1409,903,1127,693,1543,843,153,465,1519,1180,1296,649,1096,1347,557,747,337,140,1252,225,625,235,1420,149,1064,1206,945,199,278,1466,1364,859,1324,407,1028,342,251,1271,1082,492,1272,453,1039,376,445,859,752,427,631,394,168,498,315,563,818,350,1190,1330,96,767,416,154,281,1440,931,977,1310,706,719,1112,616,1303,1435,412,475,675,209,1122,1094,681,1305,868,1338,916,380,514,684,921,561,613,1536,1365,1178,1509,1229,959,1461,134,737,360,987,671,1402,508,440,1371,129,1456,1383,675,149,1127,905,1397,367,1374,943,86,218,1193,873,1512,531,570,1113,822,959,976,1326,807,884,527,1374,429,200,368,757,960,644,463,792,1345,165,137,470,472,712,1272,1421,865,644,768,744,626,655,1295,278,439,710,878,914,64,1012,257,855,1018,1376,1247,1526,1251,1525,565,945,1487,686,1215,983,703,588,991,1069,891,1008,450,179,1339,1230,813,993,834,651,129,1430,1054,993,1413,985,129,1367,1388,1090,586,1067,1473,515,1315,867,196,872,1213,60,947,882,1345,205,1490,711,999,1420,313,150,1165,1337,740,1381,1305,64,267,630,732,1071,1308,1249,848,1225,242,1317,1355,350,416,230,497,689,684,581,612,362,403,1049,918,1145,237,1170,227,667,1153,70,61,1478,201,1104,790,792,226,922,1243,1507,981,387,1173,1190,879,295,35,54,1479,1503,827,232,168,232,1102,750,1221,635,1312,363,95,141,52,903,256,493,35,859,1405,319,1385,1136,1327,379,770,1245,948,351,1054,1463,636,1118,414,1318,677,1056,1022,395,645,940,257,1086,643,781,1234,731,1225,553,1132,377,1144,1532,1151,548,26,883,537,480,863,125,791,1075,476,302,779,686,975,693,761,1484,905,1174,1049,77,290,642,895,229,1338,383,1190,1092,793,1527,639,1313,62,174,319,574,90,871,836,1022,91,1146,350,1046,882,535,1476,697,565,1379,93,1446,891,1497,177,1549,423,164,1271,808,1176,1083,1506,416,861,196,1323,746,1278,1050,881,615,177,485,879,1360,1032,53,832,639,1487,881,732,441,1046,454,1384,210,572,656,540,697,208,1162,208,185,341,727,1198,730,207,1327,706,1273,1201,1015,1224,569,176,1165,26,901,460,816,692,383,740,871,557,1001,596,98,1068,232,1296,635,38,1187,1495,778,667,191,853,700,1445,1360,1322,574,1323,58,1026,984,511,644,732,66,719,203,1307,1169,1472,449,1494,1456,535,1108,682,386,1044,1486,1248,781,194,697,158,442,1361,726,267,258,1471,416,296,767,482,1432,101,1133,1395,652,183,144,732,224,661,1272,354,1381,99,203,697,576,1241,236,172,1175,1292,226,1285,701,989,146,93,720,94,950,841,397,1255,895,493,1183,223,562,1368,812,116,880,1450,1152,530,468,1428,584,172,1229,381,47,999,341,1336,1030,1059,947,1299,574,102,1202,260,924,1052,254,1185,744,1348,954,1075,741,1155,1139,712,900,1140,742,166,148,1517,1105,1541,440,833,1454,680,1071,1145,1245,211,936,153,63,252,412,1275,1266,1002,1216,137,37,1312,1397,556,1306,255,1336,517,1070,209,957,487,588,619,853,241,1195,231,547,1043,1191,975,788,250,847,817,660,1013,1248,486,92,1084,1205,261,396,1404,1323,63,594,1250,298,309,1389,677,206,869,1528,505,500,807,698,780,632,1181,28,532,1333,872,795,1511,710,792,1375,635,748,560,391,175,586,319,1508,741,928,731,1081,1236,48,416,379,1404,431,41,547,543,272,382,1539,860,161,1548,300,1232,1280,808,806,1329,1286,1295,1342,1276,442,977,261,316,1155,525,703,964,699,286,705,1117,574,1517,187,219,165,1277,619,583,733,137,137,852,399,680,643,1316,639,583,627,1131,225,1166,1059,156,996,69,517,813,531,1209,901,149,431,454,814,182,29,40,1359,865,49,1253,866,885,1493,367,701,1074,451,612,178,1426,1383,330,746,1183,1303,873,921,501,231,1419,567,484,939,1210,1208,246,1527,279,537,698,1284,453,136,798,159,55,393,223,1176,498,900,962,601,309,1213,1476,272,260,1049,1551,775,1255,813,65,1075,613,178,263,575,756,38,553,580,1525,1385,1453,626,894,1468,62,610,575,154,413,1066,502,48,634,65,1442,1221,549,431,702,1042,951,1081,1150,956,75,177,342,514,1000,1481,783,1138,65,69,1093,1239,1280,476,688,691,1418,1106,853,1339,1459,407,413,290,1343,159,88,735,314,214,152,784,955,256,353,127,754,1005,1223,871,168,102,1497,1083,821,1470,499,63,421,59,1488,289,294,528,445,1004,303,306,993,1109,268,1329,239,44,1302,1173,1020,870,805,324,1424,1404,936,1048,649,361,754,294,592,477,537,809,1024,261,1373,1428,833,897,1476,649,1171,1121,83,1076,645,1007,639,434,466,1450,1159,365,1467,284,416,44,1526,835,945,1171,1210,310,1102,270,1112,1248,1090,690,464,278,1271,1188,552,253,237,1446,1166,162,157,661,773,1540,421,57,320,120,386,1090,1135,323,40,1148,216,1028,881,1328,1148,903,534,1011,1533,1105,261,415,685,946,821,1174,1295,389,760,295,905,470,127,1298,676,361,751,1087,1307,354,1455,1067,1233,258,238,593,1521,808,737,1466,490,827,1072,1452,411,1314,902,1142,305,101,1046,155,141,53,868,938,554,731,222,457,381,1447,509,611,974,353,442,486,747,1284,1382,832,622,168,683,629,556,996,923,187,1346,1222,321,732,1093,1475,1474,282,1233,1190,1212,565,287,1514,45,1241,1418,763,64,1482,1078,1451,650,69,1360,402,1500,1135,980,1132,35,774,1298,791,228,988,294,1219,1297,765,588,927,1300,1369,1073,1125,1241,820,587,943,969,1044,1153,82,1136,123,123,243,1249,861,613,304,1335,1344,608,1090,239,593,614,192,393,1523,1475,1461,880,941,1347,409,279,463,620,452,895,840,978,1171,876,345,517,971,1381,80,487,164,361,1058,339,247,1213,1192,1283,819,637,814,1298,350,662,801,362,1220,169,1223,1130,1359,34,229,1304,914,563,995,274,322,156,1136,778,182,761,621,1365,725,263,469,487,1354,1438,798,1022,1174,723,138,232,1488,298,1237,1200,1169,112,35,153,435,131,444,927,399,496,130,1457,938,81,1249,1207,1042,1035,911,1516,832,381,1333,1244,1173,888,66,143,1231,1463,209,433,1454,350,990,580,1166,1207,1206,653,1112,1064,345,1225,1125,1044,657,931,532,1422,281,1507,1384,631,93,280,119,964,566,136,151,483,1158,921,140,633,1324,612,1110,920,779,134,1170,1044,1414,637,576,93,1150,1111,714,1299,664,905,521,186,955,1353,1453,668,614,540,44,1216,108,1440,1426,566,850,611,306,1477,98,1165,188,862,1434,549,339,374,284,1539,640,1508,906,425,994,186,267,370,1450,734,147,1454,401,218,1415,735,27,253,942,1307,1543,241,966,519,1298,1119,230,1014,483,94,1378,1072,1094,183,1474,774,102,464,1395,111,833,428,1032,1289,1428,126,214,530,512,340,475,698,1551,572,778,843,923,409,180,490,997,587,384,391,939,1357,802,649,397,779,1217,1183,373,1352,374,1540,215,52,419,1499,1110,1008,1306,1001,1037,1504,984,414,1169,809,1403,1151,1397,1440,1253,702,622,179,35,354,1176,940,102,841,524,373,1546,177,83,1284,985,653,302,1492,1026,583,1109,1513,275,421,1370,662,582,797,1193,1542,792,1518,208,209,903,692,646,278,1045,1546,939,1133,1316,1365,593,1304,1256,1217,289,651,212,352,1501,1050,1346,1128,1318,1188,1091,441,1329,835,689,894,544,614,730,312,601,685,527,1486,370,873,1504,888,1151,244,1042,1063,1042,622,1289,1082,139,436,508,1017,495,843,140,1118,838,590,1019,1335,1417,538,1471,1144,1499,864,752,1176,401,1339,412,1320,338,1160,687,248,327,1332,1537,881,377,95,674,963,969,46,430,321,57,60,31,440,307,736,1029,279,638,1408,631,65,641,1006,1525,439,606,246,981,1170,895,300,119,914,795,181,691,126,777,1182,1547,388,1328,1543,1102,562,1458,723,928,251,1381,1411,974,1322,1546,58,1092,339,441,415,699,298,191,1175,1235,1095,268,261,501,700,778,874,409,1172,645,1165,809,72,1297,1305,1259,1109,477,634,1312,1338,1137,337,1387,420,347,968,190,1458,1020,880,893,740,295,1143,586,1184,1338,1135,1205,1485,964,1016,1429,151,1445,1406,1514,360,1164,280,1030,417,1364,737,229,1117,711,520,1055,1412,453,1085,1258,71,213,1419,692,1147,713,1260,356,355,579,654,749,133,482,1223,687,1214,1213,824,147,881,743,1506,1538,1079,844,492,1302,103,1389,899,319,446,1023,535,1302,271,1386,1375,933,512,686,1059,383,771,1535,306,981,701,613,811,343,673,1400,1443,1532,827,1252,1430,1278,369,1010,1197,220,610,625,912,273,1472,457,781,734,205,1050,1339,108,981,576,755,556,41,158,1377,311,1077,401,1158,1290,63,590,440,644,1428,850,1462,150,370,1127,852,1448,812,857,199,691,1418,1268,685,1504,677,488,835,334,1253,287,543,570,735,1109,211,1286,1495,783,523,554,346,241,1497,1090,1267,1000,1431,1522,727,1537,1163,685,976,763,402,1526,840,888,444,689,1298,614,1280,958,250,1171,991,1276,1233,606,628,1304,1141,308,536,28,176,828,1376,1423,256,1365,391,1183,835,1420,543,1267,1206,1413,534,963,1436,153,955,559,1472,1058,689,1208,1200,392,1476,985,871,900,822,439,1392,1342,1056,923,1453,879,442,1360,656,1085,804,1493,503,1441,105,47,1453,1350,1059,521,372,1369,927,811,316,857,101,788,1325,350,471,144,879,431,819,1128,939,197,474,1121,78,983,1054,552,748,1206,863,101,1015,283,982,189,1258,863,1384,1312,1503,513,675,1087,659,1473,799,944,1417,492,1230,528,1203,50,314,697,978,852,1201,1356,649,245,1180,1164,1221,155,771,795,847,1410,1190,1269,746,1322,326,1527,1417,1430,681,597,1315,93,867,280,1368,1057,1066,1328,680,691,767,1085,941,837,658,58,431,996,1071,923,1274,180,685,1527,273,576,974,1085,761,526,736,28,1474,1125,84,916,344,747,564,932,622,769,599,1447,739,1132,693,916,1201,1055,510,1355,1153,940,202,1102,1448,1340,1479,1129,1377,186,1006,333,619,1094,873,1147,266,643,1091,1289,1322,974,1396,1400,1221,1103,141,222,559,794,1359,822,1326,576,1473,191,290,276,1505,1455,1542,643,1486,158,243,1513,1062,443,169,1216,1283,656,264,747,737,1392,639,1340,985,988,1335,1402,1137,1442,1329,280,823,1144,1268,167,366,753,991,461,158,164,1282,715,586,769,454,323,1028,1406,140,360,158,55,292,885,1243,1236,202,903,52,134,610,313,124,384,1470,677,662,709,399,1493,1221,689,387,66,1197,716,514,912,932,440,1240,1292,1458,618,725,330,505,1301,621,623,139,700,1100,1503,1254,786,1227,133,1489,548,67,676,249,131,345,868,346,326,828,835,176,163,52,1200,35,1296,739,170,85,184,89,294,1478,1492,335,579,752,397,461,1229,499,1388,921,1289,1228,978,798,517,117,890,806,1166,186,1367,823,1017,276,337,197,1283,942,1513,1288,972,42,696,288,159,556,411,1367,1291,163,165,155,295,134,143,675,380,433,1485,234,1228,652,1410,1132,848,760,965,1028,1377,639,579,90,832,1540,1235,232,1148,868,1386,181,644,437,663,1291,706,620,348,1546,77,595,750,110,608,1120,386,434,174,1461,305,1407,1039,945,960,1214,1417,1015,1229,1445,119,1337,1454,266,28,638,388,397,936,226,142,1485,883,842,541,1095,1536,1314,1053,1005,1335,1155,291,1164,489,308,175,510,1355,1445,1305,1325,143,70,1049,1442,137,259,1256,74,383,396,178,664,89,1100,718,341,39,444,1018,720,350,566,1481,736,1303,1505,1440,843,551,1418,32,685,1339,52,1496,318,553,651,767,1504,1143,371,974,1468,971,1212,111,1194,494,1481,946,1188,961,1511,1305,244,35,802,263,36,51,702,1011,1073,617,502,200,402,1249,251,215,605,117,651,548,109,212,809,230,763,1136,402,470,967,916,1183,157,1387,590,724,264,377,1092,1544,715,288,1411,838,170,1087,717,91,695,85,576,820,340,285,1194,600,311,526,686,897,793,1240,1183,682,534,797,178,1101,499,1331,1382,295,851,818,1224,1297,1248,46,671,889,1528,1149,876,58,240,613,876,1034,88,1371,323,868,599,1445,1243,665,851,1206,152,951,98,1416,1489,737,149,537,128,1129,369,294,1269,34,752,559,651,1350,255,429,1134,625,1495,544,1293,270,635,509,590,806,418,1506,1328,403,225,696,268,1176,1090,164,211,1101,764,193,124,1447,859,80,681,1203,1012,510,875,736,33,878,724,1413,199,969,702,1335,639,1246,1314,1192,1538,294,224,1411,618,1179,1459,687,1221,628,1076,693,98,946,1426,137,901,330,1480,270,490,1259,1426,436,359,1092,615,513,1292,1022,113,687,275,928,238,1280,732,1219,1425,387,69,39,1075,680,77,1382,1305,1335,1299,1199,156,1313,1464,1031,286,316,792,374,1080,439,977,454,1424,1251,663,1259,693,250,231,1441,1375,1245,648,762,148,487,416,821,447,898,1138,103,1416,449,766,721,904,227,330,1045,597,1548,144,259,85,1481,860,1326,762,717,1123,538,1288,678,1228,310,1180,1405,1328,361,760,442,655,1189,297,1543,1301,64,115,498,740,1055,80,114,1068,543,547,839,1371,158,933,1216,953,401,1110,917,441,62,1352,753,319,352,59,81,626,252,1389,568,569,857,86,597,1546,381,1270,177,1502,685,1167,303,1124,808,1311,1100,957,75,1546,252,974,381,363,1027,781,668,1438,249,1188,1454,915,123,479,374,218,222,1057,1298,59,1283,1360,220,1510,1023,597,46,972,536,425,467,526,275,1532,103,190,308,1035,46,635,105,834,290,1344,448,1164,504,886,191,158,312,1271,306,1518,1157,181,294,1245,1085,841,903,811,531,1375,123,1183,1481,66,1240,252,265,568,192,742,490,970,383,1217,1081,1043,639,120,620,1319,1489,1246,606,471,1230,244,807,753,1268,1050,719,316,105,1219,851,727,1075,560,998,560,969,146,1145,1211,390,107,1090,677,1385,756,123,561,1034,1076,203,1486,528,688,1506,400,1015,104,435,650,1458,493,548,461,380,364,190,1100,451,1483,1308,290,324,266,805,1368,398,359,265,947,519,197,326,704,613,1027,474,905,548,1004,599,1335,160,606,1323,716,957,35,864,564,872,844,1206,341,668,198,1532,639,910,590,1217,736,178,544,170,1106,714,1060,1312,1118,617,1506,1544,1314,1494,61,1216,1142,1390,602,746,112,267,1071,366,158,1092,805,1261,275,1509,529,1104,200,1340,796,1094,142,393,486,984,870,353,507,1278,597,52,1326,1369,853,264,1485,814,1220,1115,973,1390,1503,1345,129,874,1152,1202,1083,1256,412,872,1412,1325,397,1421,1208,578,231,222,743,1435,916,1353,796,379,759,621,305,1235,589,1035,704,1481,506,1145,661,1071,1401,1524,1442,871,482,56,857,577,1293,450,178,466,497,1311,621,370,1109,314,741,626,881,51,730,771,1406,1499,59,1238,1230,686,722,979,421,1032,1129,1244,55,1034,1134,188,444,1152,1174,848,986,1345,88,1093,1302,233,1018,54,1329,1092,1286,812,800,689,518,1505,1266,84,1061,1255,178,759,511,1021,419,44,621,63,286,739,1268,466,1234,377,1312,73,980,1257,909,32,553,68,28,1368,1121,450,776,77,918,1409,1229,440,721,1343,469,75,1321,1424,197,61,395,1535,563,1362,1182,823,437,1417,1547,516,1239,857,311,445,153,480,1153,821,121,1112,443,1536,191,495,780,883,1237,339,1484,645,805,1094,694,85,943,731,1322,1323,238,1517,58,1441,1242,641,1384,255,937,486,69,607,322,712,884,1200,553,606,487,1151,1219,1164,1353,1007,889,265,346,1072,686,545,568,1339,55,1047,1257,652,230,579,1065,1226,434,1152,1093,1087,1223,1406,1469,286,286,468,1531,1452,1136,515,471,826,272,966,1320,1201,1098,611,332,1339,1248,673,1367,582,55,854,860,175,1481,394,1042,156,1296,835,1252,1420,248,301,231,1162,1116,260,1414,395,728,670,1154,1469,880,834,1175,841,992,1468,1536,659,1265,961,1214,760,430,663,599,628,886,1298,1276,278,220,66,51,510,326,564,110,915,1459,852,617,1442,679,824,314,1241,686,1116,313,474,376,923,34,304,55,671,796,377,112,687,1063,105,230,1330,960,1404,702,381,1175,1103,212,1429,678,851,790,374,702,1431,923,691,312,1112,1092,217,666,197,1372,981,1306,1024,720,1001,1308,421,1375,632,1209,700,500,1230,315,1230,587,595,770,597,328,829,496,759,261,916,1251,1048,1404,432,1356,707,1434,1012,1534,740,1211,759,1275,611,917,876,930,818,311,121,136,74,392,898,594,782,1080,1325,1404,853,1376,1202,1026,1497,728,411,821,29,1025,220,1138,1304,925,994,1520,1145,1408,171,1095,71,783,681,428,1371,847,839,182,1454,1420,1100,603,1370,609,470,1365,1337,749,1327,662,1038,1200,1212,161,663,582,899,537,847,875,286,824,864,366,957,667,464,1315,720,888,369,1105,735,722,1286,1012,1310,655,1455,1518,684,623,351,444,95,397,685,1092,1151,1012,140,56,1518,93,575,1534,297,297,560,650,1464,691,72,180,569,138,205,486,767,552,1321,976,1504,824,245,1064,319,909,1153,1068,986,446,1501,493,785,238,1523,245,1306,747,794,452,1462,672,956,1411,851,918,319,992,875,1193,1163,132,107,721,333,485,89,846,957,31,864,1360,1422,151,76,738,321,1103,1296,1335,457,682,626,308,1246,248,147,728,1205,863,1548,87,1087,266,594,32,543,283,1050,187,545,1202,882,1459,1307,507,1432,296,968,1159,1445,305,27,760,1442,200,1279,1095,913,970,1306,382,243,85,447,602,1051,858,973,897,131,48,31,167,1357,58,743,1008,230,401,1276,855,151,547,703,925,1234,1006,1377,731,1451,334,1134,1278,468,1016,1369,1261,773,60,347,899,1501,1446,572,855,233,947,1517,1444,623,1244,1298,94,1455,860,1172,1096,771,318,337,1274,112,308,979,1171,666,374,1539,595,602,214,1147,816,1495,524,670,1494,203,966,993,1534,993,1340,849,346,1452,678,1460,1260,398,382,179,1071,910,1214,934,473,221,1525,115,364,1112,485,633,1218,1047,1279,834,421,229,1501,665,1422,757,964,944,804,663,1321,1364,997,1342,838,653,1449,356,134,371,1270,337,480,1264,1266,314,750,1318,569,297,509,990,704,1395,1392,1019,428,479,1226,568,929,568,413,83,309,465,467,1352,1433,1485,144,1295,55,173,145,1548,1144,190,367,659,372,865,1211,395,267,831,1414,1239,66,372,274,1466,799,977,1509,703,1196,1009,882,1407,1458,803,293,143,900,209,517,740,960,1304,382,72,327,698,480,668,1538,176,1413,1479,646,303,652,912,1001,834,938,1230,448,934,572,32,856,944,1424,635,132,404,1325,1209,444,89,415,1070,547,1001,1505,1353,732,31,348,1120,1469,881,1059,41,843,458,1137,131,909,1378,216,1310,76,1282,239,1227,126,1191,29,855,109,898,681,410,740,246,140,1548,1430,433,1137,662,1087,1494,887,1508,1154,1218,1529,1256,1478,567,120,293,688,1000,1451,669,899,353,1185,1300,891,72,706,173,1178,940,1143,1426,995,746,702,1220,184,354,1270,1184,429,439,316,445,999,1188,270,1089,727,1255,770,57,775,940,54,1503,1027,629,1402,440,1262,128,689,573,1362,1190,497,1366,171,1022,580,475,28,638,343,1130,1502,36,30,1367,626,1086,226,1090,599,230,1320,909,1318,1368,281,190,1372,435,1200,1245,1079,1342,391,184,1504,1484,243,429,893,1035,1178,1417,769,617,1213,865,285,299,250,1332,1350,791,901,575,139,1443,226,1355,697,968,1168,297,383,1041,422,160,588,957,270,1381,1002,1062,832,1341,1084,807,1288,632,1265,1085,458,354,1094,610,128,924,107,136,40,82,29,1341,74,1351,889,1344,276,647,286,1363,419,1536,1292,213,1227,1348,1246,1343,249,894,934,1068,1023,84,1108,1363,86,404,827,778,1359,860,450,543,653,1292,1349,175,1222,1377,1037,187,582,522,414,1058,1549,88,1037,793,49,333,912,1203,146,1336,964,1392,446,700,1355,239,1388,1415,1036,267,157,1490,750,1535,1110,788,722,953,836,1155,1228,619,1109,948,1353,1223,749,254,639,195,1459,1257,1424,589,982,1509,668,878,1228,1192,886,790,365,1081,245,413,1194,699,1097,749,1123,283,32,747,1479,62,394,1304,556,1348,436,1410,1206,1201,1307,482,1058,387,1340,962,1272,907,326,666,356,334,1214,1435,529,1273,439,1101,654,1097,1218,280,127,552,1026,618,516,1198,1028,893,938,1544,668,224,764,38,749,629,1173,952,117,258,738,1475,1258,714,392,494,1439,1466,810,621,112,722,500,729,1414,261,766,1421,1245,1281,1197,500,615,286,205,828,48,1117,644,142,797,65,1393,780,548,264,1188,1023,713,714,486,798,887,1336,688,988,357,1481,561,713,1482,765,604,1508,117,1319,65,42,1223,593,1303,1197,168,1358,709,696,305,799,152,620,929,1334,361,1261,175,1477,278,160,1187,301,820,265,821,392,1138,356,716,1145,184,1119,34,1359,273,330,355,1231,479,1366,723,606,822,1103,633,868,179,1344,1132,179,929,488,804,85,833,765,1280,1269,472,1381,515,26,1469,1531,717,322,575,1090,734,963,973,312,216,1170,1086,1460,1247,703,213,939,533,1082,1484,849,159,754,71,1200,1046,96,156,1069,572,1205,928,1201,332,663,950,145,1443,469,864,1424,1307,1502,1453,907,824,233,1282,806,649,925,1219,476,929,1147,420,953,927,145,628,755,1124,1398,808,783,1040,478,815,1203,350,304,393,1370,1409,540,1344,567,277,908,1079,761,1269,522,1465,704,820,788,256,965,902,1024,373,792,183,1225,1357,1058,272,817,1440,48,1332,1065,1134,1070,101,1075,153,900,882,858,1148,1483,268,408,101,1259,483,766,1091,786,1250,594,835,707,1372,565,726,1209,1298,1127,1272,583,600,1052,981,645,656,997,750,1293,1238,1054,258,926,793,67,403,798,867,1495,1513,338,1429,1235,389,1529,188,815,1055,437,424,1156,1100,1281,1485,1067,1510,919,1150,405,389,467,1019,642,1268,51,1050,1282,272,1217,1113,245,1368,46,759,816,819,482,373,602,556,1040,37,541,1277,1498,808,1275,696,569,1228,919,1334,281,1506,1310,833,946,1436,586,1350,1304,830,666,209,1135,1280,837,665,1468,1155,1520,192,1372,892,1016,885,308,1026,1538,955,1409,133,940,248,1137,1294,703,730,1342,1285,632,440,1192,934,164,619,316,313,379,294,553,109,716,316,1140,577,347,759,941,1107,190,643,628,965,1249,962,834,1446,1066,527,1171,459,189,934,1402,438,1027,208,879,1352,1144,792,1141,34,432,1391,497,1319,1041,1360,154,789,1453,1426,1286,843,961,786,792,1000,582,1423,1070,46,978,1535,1154,1061,1466,1505,1481,501,1055,115,1444,1071,710,964,138,298,833,147,365,1287,1529,1163,556,1347,69,788,1025,468,1530,793,149,737,697,901,565,1311,1136,150,1184,836,995,537,122,1401,1092,746,917,1197,1021,180,1391,116,975,305,818,1195,1261,423,815,1119,499,86,1190,925,1058,773,896,757,1417,1143,900,539,1521,796,890,1533,72,1405,617,331,889,1537,170,328,740,533,210,1400,302,1354,105,302,204,194,885,439,439,961,117,1496,949,1047,769,1067,189,1116,309,969,1466,1286,1012,309,250,486,208,388,972,66,1516,63,491,198,980,434,569,1314,1259,593,600,970,1023,363,1530,536,748,1230,290,1143,1353,116,59,1011,511,1515,1442,1196,1239,1040,995,808,1452,144,1476,966,480,72,406,634,1417,1317,1119,850,487,1436,845,1169,184,1360,857,1536,827,354,1004,667,29,768,447,262,308,978,1011,129,922,852,889,1482,848,1027,1329,334,1263,712,51,1128,1251,588,203,1003,897,1144,1538,1296,152,1123,1305,257,525,645,558,949,652,1516,591,720,440,1433,537,936,595,1412,230,200,1001,1512,971,1295,369,573,225,1110,1179,573,802,1150,618,1017,815,330,66,575,241,1057,420,1313,193,1165,1143,1328,639,535,496,729,684,923,1286,514,568,1044,263,698,515,804,753,1074,974,1025,379,100,1155,860,904,1106,642,1227,211,289,432,643,1544,1346,227,588,1053,1367,1156,1282,176,1095,592,1412,357,882,41,109,108,1382,1335,590,640,910,32,811,563,748,75,84,34,206,602,468,1473,773,887,570,887,1353,837,1018,133,1204,1376,765,703,366,1466,930,1016,1074,123,1260,1347,381,924,831,885,427,1140,821,282,546,1540,801,727,154,628,1457,983,908,133,1323,324,1404,613,42,206,236,1171,1534,475,789,1423,391,1337,845,80,1011,662,216,1550,603,873,1209,1268,866,1016,525,1167,659,1334,1315,853,1233,357,226,1445,1518,1291,215,992,1322,653,917,1393,301,1232,1066,491,1116,551,494,501,637,73,651,1535,615,832,428,28,305,925,1280,624,738,1086,865,200,1007,1412,312,831,52,208,295,457,666,1324,393,824,570,1503,846,1417,895,1201,1349,1425,527,1462,349,93,1099,1066,189,1465,1051,87,314,909,464,570,1328,830,1510,1541,1461,300,901,1316,1091,1477,580,932,1011,1401,906,1415,1036,253,1295,845,478,517,404,211,1282,1464,1174,449,1469,122,1535,562,1370,514,1353,438,1197,591,896,1074,585,435,1550,375,589,1396,247,1130,1402,1114,984,1298,1147,1503,493,964,610,967,1151,620,59,935,1348,343,68,891,1512,868,448,289,1351,456,1159,1029,385,113,305,97,1154,896,829,1052,871,1399,853,1399,217,1225,107,1113,78,1506,1508,969,491,1095,1370,1004,164,439,1130,1450,536,767,795,657,1521,53,474,1173,891,124,1080,840,837,1542,234,1169,420,223,360,961,1550,119,501,1239,1536,400,606,1344,1214,632,1354,1464,1177,686,724,41,858,1015,1255,1154,492,1471,432,1091,133,945,1458,1285,93,680,665,763,428,465,99,628,1509,1332,1219,459,91,743,107,718,851,1122,855,524,1493,594,1196,36,1005,1539,416,1077,1241,1334,987,459,1241,1456,195,1551,1290,1358,171,301,1515,468,235,351,502,950,182,196,612,483,1486,1300,1152,448,39,1275,274,483,444,1253,1177,1246,1106,851,742,1144,992,1005,1178,1406,308,1219,307,682,463,1176,475,611,266,1334,84,739,1139,901,1494,1037,381,1142,430,1480,949,64,650,158,824,1448,1363,238,1360,131,252,1179,1098,1389,737,785,985,743,924,397,878,885,1074,438,410,1267,952,1060,591,327,561,914,1027,367,100,1328,118,1308,54,153,1237,484,332,1244,349,883,158,191,1204,1236,629,201,1348,1044,614,335,952,1423,1354,1427,104,1026,128,967,224,808,127,199,1496,1311,640,689,1316,563,1129,313,749,483,578,1117,1278,757,439,761,848,938,623,1242,906,504,1365,658,770,1004,1295,230,1449,1378,914,143,719,1054,237,125,1206,749,949,1309,811,761,1206,272,1214,1476,1198,60,1453,631,113,37,1006,989,27,128,184,135,793,378,1455,26,1057,1296,391,713,202,860,487,411,1504,1474,1280,802,485,1354,508,841,1204,133,40,1137,1389,431,307,307,683,259,1379,246,899,728,669,243,979,1450,1209,531,786,755,106,1443,741,1057,844,884,140,658,1526,727,948,1158,978,550,973,1288,946,663,445,1514,1310,59,837,228,211,874,667,1285,1210,1296,341,417,922,1041,213,1459,30,710,1248,327,885,1496,1350,1543,975,774,1404,101,248,987,170,236,47,849,841,1042,1368,543,238,1517,171,482,445,803,207,109,598,1460,685,1369,488,973,1188,318,399,1514,414,1258,1241,898,1516,389,366,677,989,1228,327,1148,600,1034,441,1096,853,1150,115,1128,85,86,671,645,435,905,978,603,690,1507,497,1139,954,121,685,1306,526,780,647,562,199,444,1134,606,1156,1387,1141,1516,332,177,126,1464,1349,623,66,1050,1222,1513,1498,834,1430,151,1393,1381,1169,250,1298,187,368,1016,798,106,1211,277,1092,183,350,1277,1482,562,873,1290,957,127,589,392,139,1070,47,588,1062,1227,1300,734,792,1504,515,1209,343,1438,1277,184,733,1263,480,936,1168,1422,940,1385,422,398,45,671,319,192,929,184,331,174,879,323,1136,995,446,1162,1144,1189,726,1098,737,1013,77,603,61,750,381,1027,886,1519,1174,510,582,1444,1285,760,606,850,821,666,797,1212,1115,938,1476,1431,1392,733,1107,29,291,353,605,701,559,469,74,1468,1527,867,60,1163,474,338,184,553,498,283,323,880,227,1319,1346,1019,1242,1176,808,847,1377,1342,1315,1443,450,1445,805,602,239,1111,290,1109,1183,1168,433,1527,689,972,600,1444,1431,452,591,1461,419,154,392,289,442,524,1145,110,1532,1550,510,1135,749,465,588,782,347,460,635,289,1494,1534,880,206,461,1532,1551,412,178,1549,74,1099,1333,667,563,384,27,921,1449,302,963,315,1257,240,654,1523,36,1071,1062,1050,945,466,394,1425,894,622,378,51,1301,1295,277,1535,1389,532,397,75,1186,1445,812,1547,798,1350,1425,623,27,511,961,210,148,1415,63,337,60,1208,40,903,1114,653,1398,1240,807,435,275,910,874,1245,1188,357,298,863,929,1238,370,700,257,1429,1170,672,218,960,647,1446,108,1246,179,929,393,820,316,1421,911,1255,190,736,865,1493,967,423,1228,435,562,113,200,1551,1120,576,252,1005,1461,973,837,1332,158,909,849,152,768,123,981,40,376,1357,533,404,438,517,587,388,272,1525,1276,96,1035,1157,545,876,504,1328,66,320,166,841,308,1040,731,1076,186,681,378,306,189,1017,1300,783,179,601,584,1182,96,80,850,1061,624,546,433,1551,363,1362,201,1517,1166,645,1103,497,1254,687,1307,542,1459,1244,124,717,1252,1282,599,938,874,364,232,1082,942,1451,737,414,688,786,217,741,939,912,88,296,521,83,375,1282,969,849,613,585,499,867,929,1032,144,891,488,724,642,1013,949,1200,650,213,303,959,1450,1398,1231,175,289,1514,1440,1093,106,109,549,1117,1127,586,941,296,1207,742,832,1093,887,594,1257,1199,81,1257,1226,730,152,720,256,56,1263,1459,1079,913,933,199,1272,30,624,1088,641,1153,844,601,928,1442,386,1409,1497,258,516,248,57,964,522,1216,863,571,52,1490,634,228,1474,1310,440,1282,143,1274,578,694,1079,485,994,1281,1037,1321,39,242,1294,729,562,679,445,194,805,1068,1352,999,1512,91,957,378,37,789,351,394,724,187,1352,1362,1408,1436,1509,60,343,119,832,761,879,64,668,617,144,633,48,990,173,817,1492,419,1428,1422,1267,221,719,1101,1505,1225,848,815,235,454,722,994,987,1225,680,1103,733,949,1260,1526,737,1343,116,1104,519,1326,620,1090,506,236,1162,448,93,938,632,896,1115,355,205,783,490,633,35,380,68,406,1497,552,1104,251,1245,1235,1301,1274,995,800,1043,227,215,304,331,713,892,780,1235,100,749,868,895,959,339,883,97,906,1344,1498,791,167,364,773,159,1527,1546,1036,328,1006,837,218,636,500,928,819,1414,1037,1422,489,419,1361,300,1204,39,925,801,851,1003,504,66,609,1502,470,192,961,844,69,331,1355,1109,730,827,830,683,1239,1539,779,624,198,106,262,1336,1519,721,1206,31,410,513,156,314,1431,1242,1394,909,1358,905,1262,1137,832,103,1502,850,829,1390,600,58,1488,1482,133,339,925,596,1437,137,283,389,858,37,520,203,833,1290,1436,1127,1101,1336,1163,1464,319,1085,609,964,553,114,662,1416,940,1136,192,754,1116,1218,1332,248,1351,602,321,955,359,1101,337,1418,1193,626,965,1272,783,906,813,915,578,193,1368,974,410,639,125,1493,421,635,689,424,1392,1057,1438,473,85,768,395,1328,428,1323,1309,865,147,1323,598,1513,1437,1331,1247,180,884,1272,668,623,1090,1172,296,956,525,965,1381,116,1000,615,1148,1369,129,1362,1435,638,265,864,542,945,997,399,524,1186,40,669,757,752,351,722,687,29,1028,1466,44,872,583,447,1078,797,212,533,1256,1380,969,937,1208,82,1546,1203,486,177,424,874,1261,220,1291,730,934,1268,524,399,870,1350,504,1270,1105,302,421,789,1032,1500,1000,1136,1481,1064,869,503,370,906,1041,1533,326,1169,1498,334,751,764,1081,1527,528,1026,1453,73,1150,1071,1393,748,80,1448,807,1509,1091,956,1154,328,1042,45,195,1469,810,796,1514,392,1047,538,1093,613,451,910,99,275,1003,1509,722,398,508,246,1167,1119,574,1097,1462,1046,939,28,887,68,820,879,904,1514,150,495,809,427,234,78,153,233,1434,1220,813,517,1076,527,670,437,264,1126,1345,27,1384,79,657,173,422,735,675,266,595,1516,347,1040,885,1516,1548,213,587,776,819,961,1261,1427,60,86,321,1435,123,624,1409,1289,765,920,774,1313,1280,611,518,224,251,420,237,1194,800,982,1009,775,737,755,677,694,686,1136,422,886,72,1356,862,1316,39,337,1042,473,647,278,688,71,1108,527,639,534,700,638,600,858,1276,72,1313,1238,682,1361,717,366,207,1259,1518,528,99,1459,938,968,669,1521,324,424,1414,1539,970,37,123,669,1283,862,285,1087,983,158,1324,1014,500,373,1520,902,726,613,703,536,202,1494,461,1004,906,1375,909,362,1163,535,666,671,175,1058,1403,734,459,1550,1141,579,1421,1260,261,1013,1503,69,276,376,276,54,1338,1289,371,1245,743,82,1544,1239,1349,1453,95,1216,1538,108,330,922,913,448,630,578,555,1123,1147,202,145,362,503,1149,1213,530,429,1435,1296,279,1451,1078,946,998,311,1406,709,1311,1310,965,1547,643,989,1424,1512,27,370,1009,976,834,727,956,276,960,1373,304,635,561,127,360,416,1413,691,812,1132,735,114,302,1506,451,422,1046,707,1401,613,946,1354,191,377,413,1538,834,1004,439,518,128,1044,105,1247,847,664,380,458,149,954,152]\n", "w = [29,310,236,441,200,267,115,59,277,42,361,112,483,104,338,69,438,55,318,470,20,490,455,119,259,51,492,50,160,414,38,289,429,446,350,412,12,515,367,397,122,35,522,355,448,266,333,500,211,226,203,366,240,324,111,280,520,321,211,360,437,292,512,161,85,139,12,211,236,213,377,85,494]\n", "assert max_happy(a, w)==70, \"test5\"" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [], "source": [ "# сто тысяч детей, две тысячи конфет\n", "import random\n", "random.seed(1234565432)\n", "children = 100_000\n", "sweets = 2_000\n", "\n", "a = [random.randint(50,2000) for _ in range(children)]\n", "w = [random.randint(10,500) for _ in range(sweets)]\n", "\n", "assert max_happy(a, w)==1847, \"test6\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Последний тест - на время**. Два миллиона детей, двадцать тысяч конфет" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Счастливыми стали 16074 детей. Затрачено 0.327 секунд\n" ] } ], "source": [ "from time import time\n", "random.seed(12345698765)\n", "children = 2*10**6\n", "sweets = 20_000\n", "\n", "a = [random.randint(1000, 20_000) for _ in range(children)]\n", "w = [random.randint(10, 5000) for _ in range(sweets)]\n", "t = time()\n", "happy = max_happy(a,w)\n", "t = time() - t\n", "print(f'Счастливыми стали {happy} детей. Затрачено {t:.3f} секунд')\n", "assert happy==16074, \"Что-то пошло не так\"" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "# Эту ячейку выполнять не обязательно! \n", "# Проверка времени будет выполнена на том компьютере, \n", "# где хороший алгоритм работает примерно 0.5 секунды\n", "assert t<1, \"Слишком долго считалось!\"" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }