MaliciousPath
SRM 652 · 2015-01-29 · by lg5293
SRM 652 · 2015-01-29 · by lg5293 · Graph Theory
Problem Statement
Problem Statement
Alice and Bob are playing a game on a graph.
The graph has
Alice is currently at at node 0. She wishes to travel to node N-1. Bob initially has K tokens. At each node along Alice's path, she will first announce which outgoing edge she intends to traverse. If Bob wishes and if he still has a token, he may spend one token and choose a different outgoing edge from Alice's current node. Alice will then be forced to travel along the edge chosen by Bob and incur the cost of this edge. If Bob does not use a token, Alice travels along the edge she announced, incurring the cost of the edge. Alice knows how many tokens Bob has remaining at all times. The game ends when Alice reaches node N-1, or she traverses an edge 1,000,000,000 times without reaching the node N-1.
Alice wishes to minimize her travel time. Bob will use his tokens in such a way that Alice cannot reach node N-1 if it is possible. Otherwise, he will use them to maximize the total cost that Alice incurs before reaching node N-1, and Alice will always choose an option to minimize the total cost. If it is not possible for Alice to make it to node N-1, return -1. Otherwise, compute and return the minimum time that Alice can guarantee to reach the node N-1.
Constraints
- N will be between 2 and 1,000, inclusive.
- from,to,cost will each contain between 1 and 2,500 elements, inclusive.
- from,to,cost will contain the same number of elements.
- Each element of from,to will be between 0 and N-1, inclusive.
- Each element of cost will be between 0 and 1,000,000, inclusive.
- Each integer between 0 and N-1, inclusive, will appear at least once in the array from.
- K will be between 0 and 1,000, inclusive.
Examples
0)
3
1000
{0,1,1,2}
{1,0,2,2}
{3,2,1,1}
Returns: 5004
When Alice is at node 0, she will attempt to travel to node 1 using the first edge. Bob will do nothing. When Alice is at node 1, she will attempt to travel to node 2 using the third edge. If Bob has a token, Bob will make her go back to node 0 instead using the second edge. Thus, Alice has to travel the cycle 0->1->0 1000 times before she can successfully make it to node 2. This will yield a total cost of 5004.
1)
4
1
{0,0,1,1,1,2,2,3}
{1,3,0,2,3,2,1,3}
{0,100,103,0,0,34,102,33}
Returns: 100
In this case, Alice's optimal strategy is to attempt to go to node 3 directly from node 0. Bob's optimal response will be not use a token, allowing Alice to reach node 3.
2)
10
5
{0,0,1,1,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,9,9}
{1,1,2,2,3,3,4,4,5,5,4,6,6,7,7,8,8,9,9,9,9}
{2,10,10,1,2,10,10,1,2,10,100,10,2,1,10,10,2,1,10,10,1}
Returns: 514
3)
50
200
{0,13,8,17,3,8,4,21,11,20,2,18,21,2,4,9,17,0,14,10,15,18,1,22,10,14,
19,24,5,5,12,7,7,16,19,13,20,15,23,6,23,9,3,6,16,11,22,24,12,1,25,25,
26,26,27,27,28,28,29,29,30,30,31,31,32,32,33,33,34,34,35,35,36,36,37,
37,38,38,39,39,40,40,41,41,42,42,43,43,44,44,45,45,46,46,47,47,48,48,
49,49,37,9,14,0,33,20,46,26,12,11,2,7,34,19,37,5,2,17,41,16,34,13,18,
35,6,14,16,25,9,10,5,10,7,36,45,3,6,22,32,28,45,40,16,36,28,16,34,1,
9,19,18,6,15,29,12,5,44,33,49,14,40,1,30,21,37,49,1,44,42,6,38,1,31,
40,37,34,35,6,43,29,41,48,17,4,38,26,4,46,43,6,27,30,0,16,40,33,0,42,
41,10,33,47,11,37,49,25,36,20,47,12,28,17,11,17,26,26,37,34,27,17,8,
2,13,43,36,28,1,23,29,40,18,22,0,7,30,23,3,39,5,23,28,38,44,19,43,15,
16,43,5,27,24,25,7,16,38,33,33,1,9,25,47,0,31,30,29,4,36,49,26,6,39,
40,28,39,48,26,2,15,41,42,32,0,35,34,28,30,40,3,33,16,15,41,45,12,33,
35,16,47,34,23}
{41,42,17,0,2,7,28,32,31,33,6,42,11,13,7,40,47,21,4,6,19,15,4,18,30,25,
2,10,30,34,1,47,35,23,3,0,9,25,42,21,4,6,47,32,5,40,5,0,8,49,16,29,8,
11,42,33,35,26,27,43,35,6,14,13,44,25,13,42,2,26,17,3,40,31,18,12,24,
37,0,37,15,44,35,40,10,1,35,47,36,33,2,39,23,28,32,0,6,21,33,41,0,19,
16,29,35,16,44,6,18,17,2,46,41,11,27,5,44,1,48,15,43,8,41,33,16,11,45,
47,19,41,14,41,8,24,13,3,44,41,42,30,31,44,21,14,43,48,0,6,25,38,36,14,
36,22,43,15,20,19,37,25,17,44,17,46,8,25,33,19,42,40,42,24,15,31,34,8,
41,25,20,29,2,5,43,28,33,40,31,27,6,21,9,35,8,8,26,13,11,31,4,4,30,34,
35,1,15,11,10,24,15,24,23,16,24,32,9,1,6,17,48,6,35,19,12,5,21,23,25,9,
17,47,19,23,22,35,19,5,1,10,9,41,11,45,0,23,0,11,39,0,17,2,18,4,17,24,0,
10,19,4,36,22,42,18,13,48,27,11,19,28,31,39,32,48,2,26,38,43,38,49,34,
37,11,9,11,14,12,9,37,0,22,14,15,0,8,23,7,43,5,8,16,47}
{494,848305,3326,6008,223,2,6,673,152335,25,713909,42842,122,9941,361853,
35,20157,1098,41,83693,365851,43843,622,591230,7722,2489,7,861622,21272,
169,1153,3,7,3,577031,24522,5,241,757900,11036,8892,199,7,2,1,453031,115,
13,125,67,35,91,33427,14,106,203749,5,1804,4543,23,1,281,441212,18,3,
11629,233,388188,10,701,76170,763,875,11606,44972,6449,37409,83516,5912,
6,705899,26759,253,580531,14215,21916,884775,30,678,5940,17,480830,8,
61,218613,683352,4,557589,2619,3658,221515,15825,163577,25,9,1,4,13,2,88,
147,110163,18118,2,15429,211872,24,1,188382,12500,2348,190,4279,40,8428,
56325,933152,231523,9454,21,4855,96168,1722,329515,77,1,3,3518,10926,
12172,4,71,181976,1318,9,5086,905,108490,80164,2,10236,197,1880,17420,
614650,372457,13918,36,17,167,6,254127,512,15,341436,1,186,96,7,3,42,4,
3,4,492598,18523,172302,1,421535,390382,2952,6228,871,505372,131266,5,
743902,11,34,657,4717,3196,259,192504,229,6786,28,44364,21123,8,166781,
885021,2,828,497,376,24707,52,1,1659,19402,27261,82,473,443,1089,586,20,
7,239277,27132,4681,761,10644,17798,1,820306,13330,19,293167,2,4,89279,
14,1,9,18023,1165,495221,32304,538,178613,1,4764,32767,114,103,1,302,428,
92,927352,22270,2646,3599,6,16362,3,4,280286,338,652,2,347022,23,323084,
3338,46,58,1263,93,46992,19112,1,19499,33,807600,20296,16803,911294,3151,
1,793,1,1,504,62209,1397,52726,3650,54,3630,358480,178,394,28,137436,52764,
1209,1599}
Returns: 121213509
4)
20
1000
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,18}
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,0,0}
{1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,
1000000}
Returns: 19019000000
6)
833
1000
{608,543,495,257,789,263,744,447,151,423,396,431,498,676,379,378,526,105,576,249,449,192,90,217,731,140,123,19,598,237,162,649,822,389,76,96,271,366,33,570,60,342,318,774,555,725,171,720,787,339,307,287,399,494,679,786,580,732,64,131,289,351,800,635,273,203,553,519,528,619,400,749,764,747,621,799,822,335,752,494,312,105,425,573,820,624,46,208,141,829,805,180,631,563,544,699,183,637,185,802,536,110,42,229,410,603,29,42,793,741,131,626,129,759,547,646,694,582,786,266,247,811,569,578,656,308,252,485,136,138,134,8,328,309,561,439,236,581,784,761,779,629,486,209,285,167,550,578,485,540,349,639,205,81,594,496,410,430,668,495,174,362,387,801,127,221,87,602,52,683,49,336,318,296,270,40,344,141,599,371,649,591,220,184,648,606,501,560,348,620,405,92,177,187,102,500,151,290,144,346,632,794,98,472,267,57,384,223,24,24,438,118,788,271,708,456,777,303,773,101,444,483,452,16,32,149,86,406,325,797,459,440,176,122,392,224,656,524,179,450,615,400,831,430,562,797,184,759,495,248,353,179,448,730,217,488,558,109,590,467,71,357,617,182,640,454,471,189,457,444,604,316,282,407,282,747,645,37,596,374,653,445,50,314,211,150,625,54,172,205,244,643,248,657,700,608,75,521,405,484,372,458,379,652,37,639,739,169,304,683,96,115,706,633,692,715,158,123,47,643,596,655,520,479,465,536,796,84,54,697,433,108,413,702,390,386,794,364,611,372,420,193,763,492,468,332,530,317,259,616,438,125,171,181,204,577,110,261,103,135,211,103,780,377,57,733,778,375,94,270,483,546,529,469,818,520,370,745,676,434,806,513,748,14,458,757,288,535,714,742,568,616,727,106,775,461,51,173,210,20,415,474,733,710,23,468,765,627,263,499,594,632,678,239,212,337,133,88,241,434,428,274,372,343,629,27,368,130,763,572,732,100,124,586,677,787,362,827,671,380,704,334,352,454,403,538,643,215,505,241,612,657,570,329,135,51,65,163,272,47,817,773,687,347,239,140,315,473,555,409,21,695,784,51,350,713,269,118,439,229,348,56,70,369,191,499,556,675,821,745,554,186,754,544,78,504,556,376,383,551,142,533,172,277,613,518,331,455,560,427,526,583,326,516,220,66,693,414,636,529,337,135,531,338,503,442,753,684,600,746,44,457,360,238,321,283,449,126,365,521,596,231,531,272,760,508,735,272,83,717,735,591,617,220,148,7,308,73,82,749,456,222,227,207,81,741,409,767,275,257,139,225,428,398,768,553,450,35,791,260,250,88,264,155,59,497,486,45,403,307,125,206,44,142,487,219,3,552,63,467,25,97,112,638,791,605,169,290,213,11,296,371,781,421,506,64,734,300,601,746,724,13,16,19,359,113,263,426,114,750,405,268,164,146,723,71,187,603,688,825,684,677,244,34,315,32,218,827,167,579,270,340,566,400,180,161,475,762,798,505,6,726,62,469,431,189,594,514,433,586,376,131,743,15,417,442,150,70,408,312,196,696,446,300,681,375,382,592,762,74,479,126,490,327,404,790,719,517,1,691,380,436,90,488,557,804,828,385,344,671,513,718,8,140,720,485,68,582,513,378,733,361,685,497,137,493,77,807,462,748,726,625,255,532,526,669,92,370,282,748,95,712,203,283,7,668,5,3,306,5,780,49,607,507,104,208,345,693,85,156,286,470,423,197,124,175,219,236,129,437,737,307,242,186,587,25,119,480,419,341,532,299,340,132,120,42,166,268,394,351,774,421,196,216,737,636,492,635,552,540,59,349,577,83,80,734,539,138,254,662,134,664,238,810,129,613,316,41,682,569,6,115,60,202,457,213,418,399,509,176,470,295,654,89,562,227,451,92,661,426,493,228,254,721,482,119,454,53,587,326,30,112,673,335,550,562,196,560,246,388,731,716,166,664,38,742,9,292,152,609,481,367,417,799,500,279,816,789,398,717,776,252,323,88,161,79,221,404,566,297,93,361,464,22,322,702,310,651,755,825,20,630,420,542,94,159,829,610,121,657,284,727,726,636,452,534,439,740,511,816,618,281,125,53,512,393,222,488,419,808,568,655,603,74,704,558,663,792,538,21,581,402,619,19,506,177,157,813,202,14,797,525,16,651,96,705,702,719,215,676,764,464,714,774,641,626,672,790,1,7,524,699,106,684,383,642,779,432,325,264,618,743,342,391,292,79,391,525,632,266,522,677,233,575,529,26,337,810,99,818,305,478,667,548,601,434,699,777,142,365,524,783,609,686,424,788,228,481,145,481,706,36,753,425,407,689,62,427,195,798,215,627,394,709,674,358,818,407,280,527,810,63,111,438,628,588,353,322,756,565,516,704,31,541,708,116,72,110,207,520,188,69,480,510,658,612,538,518,769,89,383,703,522,163,13,6,277,334,194,301,377,420,368,144,328,725,503,353,563,234,525,77,289,313,0,611,210,259,659,743,85,606,98,444,589,787,512,725,4,29,418,225,199,75,831,453,762,812,193,462,250,580,771,316,233,113,689,17,412,305,670,658,441,422,519,201,595,162,714,584,739,173,572,464,468,515,262,397,332,504,58,648,615,4,478,436,168,21,76,722,593,235,679,294,474,133,97,696,515,340,61,759,74,533,792,765,82,479,35,297,114,397,309,490,357,584,240,489,437,623,393,156,67,455,675,289,226,143,623,585,641,629,489,170,324,364,543,5,184,396,660,388,579,570,343,146,153,417,766,711,326,210,25,401,12,267,807,390,565,242,382,736,645,232,491,12,790,590,221,447,512,73,796,828,198,549,251,147,625,484,154,688,697,534,761,545,342,471,86,204,166,261,377,515,303,811,165,745,581,429,778,93,749,165,59,395,265,192,323,311,291,549,421,545,130,785,365,557,681,168,803,817,681,275,237,564,769,267,635,730,782,411,45,807,567,443,35,291,212,689,516,473,801,672,374,448,109,640,634,687,349,612,118,336,499,174,133,286,321,90,605,805,312,771,10,523,338,716,617,197,70,571,163,325,592,523,186,111,78,772,149,750,586,330,134,165,188,209,253,323,624,33,401,711,619,484,412,48,701,707,779,327,501,126,551,718,777,573,723,111,736,213,254,256,752,528,206,622,698,30,103,528,815,713,754,650,761,120,608,40,720,724,207,69,194,542,724,319,763,710,415,757,72,707,460,756,240,105,18,575,157,576,182,237,507,217,710,728,178,799,610,662,251,475,703,0,772,595,776,253,363,256,809,806,76,673,287,224,712,435,811,830,102,271,406,821,252,415,381,38,574,531,55,122,31,274,514,202,385,411,661,646,469,597,831,489,422,760,306,752,448,812,819,273,530,49,408,475,41,576,230,334,634,154,511,224,330,155,536,71,595,827,333,502,544,530,164,229,453,413,148,306,466,360,577,794,243,589,299,302,708,753,352,809,582,231,266,108,381,432,599,366,327,231,32,707,339,738,52,500,28,359,102,214,331,822,75,832,554,650,354,226,100,30,347,205,550,791,172,465,2,778,654,571,830,95,348,824,403,136,295,195,647,510,628,416,123,369,410,208,190,812,322,729,277,470,363,235,251,374,155,285,79,12,152,452,346,159,463,177,757,695,249,37,247,398,615,427,387,373,193,688,631,386,450,185,120,128,227,356,508,738,447,191,328,389,425,443,692,230,343,443,647,214,620,815,145,170,293,226,245,358,294,211,680,104,477,786,754,587,647,756,62,366,539,392,305,367,445,324,721,592,716,72,301,10,276,785,281,768,39,800,109,387,751,599,751,293,384,672,644,832,246,732,298,178,176,198,564,734,43,832,669,91,618,823,766,701,496,691,770,167,10,739,578,314,820,496,370,424,804,669,58,78,640,769,501,755,80,663,552,697,781,63,248,437,773,139,414,57,563,187,298,650,655,64,48,175,394,150,736,693,483,262,601,73,760,509,738,148,691,1,412,781,703,546,355,634,137,527,685,583,766,132,36,295,243,802,793,649,728,333,549,673,302,722,785,611,664,539,431,222,182,651,100,329,633,567,653,804,242,333,713,741,652,463,541,803,559,682,690,783,346,178,446,160,630,219,692,232,665,572,695,121,670,796,709,386,585,249,429,801,621,477,668,441,597,758,269,132,214,358,614,722,157,402,556,808,591,354,712,216,698,276,345,518,50,656,200,233,278,308,320,494,11,559,199,124,637,690,117,809,510,194,423,453,382,660,441,362,368,285,661,653,355,548,29,336,351,53,569,660,593,830,47,315,814,770,598,161,17,390,665,175,359,311,772,776,758,455,620,144,819,234,250,579,600,667,304,559,705,192,584,40,517,137,682,262,440,533,3,574,84,39,264,81,20,604,671,561,631,158,675,138,69,87,498,551,737,476,824,564,614,28,107,728,553,83,46,216,68,299,352,280,717,476,580,153,829,767,281,160,740,800,701,26,614,686,43,313,607,680,153,442,191,750,94,474,246,678,545,445,373,288,329,504,523,350,91,130,116,638,771,244,456,472,825,406,284,61,605,313,107,335,23,813,735,344,705,156,616,740,356,258,98,195,261,347,151,278,502,497,547,815,521,641,430,253,93,22,235,461,711,296,435,665,247,269,67,361,461,341,238,666,276,56,561,817,666,639,659,658,44,416,112,696,589,0,527,598,240,324,571,171,232,742,465,55,234,537,180,116,449,555,101,97,66,34,542,31,540,816,659,755,355,491,414,39,541,14,460,709,2,223,298,283,593,543,823,149,209,428,694,204,34,519,396,575,82,201,662,67,546,490,86,357,397,297,508,273,404,683,588,505,609,314,206,731,287,158,200,478,670,84,24,183,522,451,767,17,422,65,399,813,435,654,54,11,218,136,471,621,354,783,694,401,602,775,197,159,259,622,770,685,814,715,50,104,780,367,385,446,228,680,473,189,115,517,48,590,91,154,310,821,379,127,392,107,808,506,806,429,690,700,345,164,746,384,300,814,744,301,27,723,568,68,291,121,320,274,66,477,802,537,395,637,633,507,223,8,607,99,80,360,630,218,679,174,200,700,686,375,463,663,255,597,341,117,279,302,363,117,678,45,260,492,480,280,95,85,585,416,169,828,638,319,268,146,168,245,395,409,388,319,493,364,642,667,588,22,198,376,432,534,795,718,18,310,826,320,644,294,413,317,486,284,826,183,181,321,426,547,245,666,265,122,236,436,52,627,339,28,61,87,648,292,610,373,108,824,260,338,152,181,583,411,4,56,687,644,782,304,381,792,764,826,729,258,674,65,147,185,535,143,290,715,99,795,239,309,573,642,257,487,9,55,509,459,784,265,89,482,419,143,393,139,317,600,288,503,330,458,459,460,782,418,511,33,332,789,128,798,548,602,706,389,491,303,498,230,9,26,36,199,820,476,203,626,293,101,472,451,719,768,558,652,356,557,391,60,730,371,77,747,243,482,805,145,628,311,41,201,15,170,674,128,565,535,318,758,467,574,788,775,256,23,350,286,698,212,380,173,532,462,141,113,378,502,624,765,58,487,160,606,255,566,554,823,275,190,466,147,803,2,645,27,241,466,106,279,43,729,13,622,537,793,514,114,646,190,258,331,119,46,278,623,613,179,402,38,819,744,727,15,433,225,604,424,127,795,162,751,408,369,188,721,440,18,567}
{530,694,157,430,86,476,376,481,615,500,676,169,506,49,61,319,507,271,480,563,472,56,247,690,817,574,630,31,70,292,15,580,369,11,114,592,117,772,549,266,108,114,686,365,411,357,352,498,815,258,98,47,196,87,559,599,323,1,115,586,816,735,401,713,148,684,809,484,375,155,618,488,309,647,683,790,521,125,417,484,197,368,217,176,741,51,528,193,156,199,220,504,570,612,203,301,762,777,96,152,585,721,112,24,261,556,514,594,120,221,160,468,652,563,803,321,458,576,255,134,606,686,226,29,212,310,746,195,756,292,3,677,214,817,352,771,588,652,164,797,2,32,303,107,13,799,62,478,581,144,159,145,226,197,240,701,23,99,748,385,548,115,130,721,710,203,385,703,243,565,624,273,521,445,178,463,687,812,480,191,655,217,53,609,573,173,281,588,421,578,404,89,673,463,775,519,88,45,73,175,786,751,290,677,361,200,204,198,744,568,436,106,274,325,338,473,525,100,554,815,216,743,712,698,501,93,668,586,245,62,179,162,304,585,4,521,395,720,322,729,527,453,176,635,498,327,754,419,821,771,411,454,766,340,173,119,162,158,821,598,302,773,410,588,128,690,410,44,557,670,51,576,560,400,474,585,563,35,522,161,748,281,250,722,13,3,197,500,734,619,607,253,161,298,508,162,535,555,6,263,698,545,154,192,304,130,122,94,340,43,145,192,527,484,595,665,96,649,361,78,372,714,551,365,458,28,99,675,210,470,486,525,818,269,235,299,606,267,233,533,735,740,810,635,118,165,181,763,58,740,483,17,170,720,510,516,57,162,419,749,285,234,669,257,495,624,43,166,158,660,272,83,245,5,733,459,148,146,804,368,239,300,394,223,575,144,495,699,546,454,376,259,570,461,757,396,352,128,519,153,71,185,600,703,405,321,678,692,133,560,218,760,362,537,415,54,364,52,226,97,255,83,522,685,526,805,755,682,555,172,12,6,79,556,633,67,605,797,101,256,750,308,624,605,780,253,514,411,65,405,49,497,150,11,532,804,231,625,709,97,564,61,829,59,254,647,785,392,51,314,236,506,575,514,764,34,818,649,620,626,149,232,501,534,187,477,794,386,511,85,0,223,642,808,466,174,261,49,341,187,669,705,763,257,448,222,52,518,348,470,456,440,462,90,295,174,365,747,38,314,423,186,654,30,783,822,774,670,592,622,731,284,646,27,402,447,713,242,620,168,121,444,428,323,794,632,763,638,93,587,341,145,680,378,606,550,410,521,741,720,194,16,359,771,776,127,652,437,157,523,678,464,737,86,186,2,539,68,658,400,542,615,725,384,143,514,33,412,669,698,252,638,135,239,701,27,700,318,417,371,656,543,594,558,727,372,676,193,7,222,19,379,512,332,343,362,236,763,263,383,707,356,604,479,730,718,364,802,485,329,21,778,430,294,438,764,688,693,293,805,639,611,628,435,298,773,126,761,107,771,726,583,482,776,445,708,125,467,680,575,265,206,488,459,94,135,364,521,658,466,608,230,795,206,119,173,134,693,327,686,442,612,799,642,821,136,471,691,443,576,339,504,185,120,422,185,602,640,734,461,316,272,367,276,280,396,584,216,525,787,754,415,247,460,213,509,753,588,822,53,523,418,724,730,17,457,276,457,106,672,660,312,599,642,389,493,821,273,589,492,15,31,44,553,343,492,179,155,309,524,493,396,57,456,103,782,391,190,146,452,710,571,54,650,102,738,238,51,353,389,170,821,637,251,120,161,461,33,234,20,785,389,61,800,733,6,121,510,574,620,726,149,255,96,176,219,732,199,211,129,346,751,90,582,447,588,729,366,537,335,700,682,825,786,725,468,344,649,523,782,136,628,166,366,180,193,249,328,287,340,621,239,824,644,6,39,442,214,439,818,807,826,724,450,0,445,52,723,528,501,614,533,801,42,804,100,707,477,509,61,105,250,476,69,82,165,281,67,360,612,141,635,502,807,55,210,396,266,789,643,761,6,334,706,77,16,817,21,338,650,74,378,583,426,73,585,794,559,451,634,610,599,351,754,327,639,401,593,106,315,557,631,277,238,397,33,207,289,385,408,327,749,755,319,446,655,307,686,326,780,579,719,40,243,783,95,307,188,643,695,195,664,465,365,480,665,81,462,312,227,550,663,307,182,120,407,413,546,763,624,403,440,333,270,137,5,200,490,798,685,322,739,558,387,139,224,377,820,782,679,182,311,485,41,745,827,512,741,682,150,533,494,651,620,722,0,333,165,199,782,151,29,539,162,159,47,442,257,295,339,124,750,154,670,69,72,117,550,591,809,572,18,63,525,259,371,624,802,617,147,810,695,732,334,480,705,208,616,379,572,686,766,759,486,23,51,192,124,458,518,441,482,184,569,733,158,291,801,127,191,330,414,408,106,424,513,618,552,201,491,765,87,705,211,503,523,832,410,259,739,168,180,690,652,184,136,704,56,696,76,696,488,51,610,26,79,373,810,803,532,482,303,385,591,283,80,799,388,363,702,639,674,822,369,304,609,592,82,827,320,823,630,127,256,171,415,258,92,425,356,216,474,498,307,373,104,584,702,184,655,168,559,659,760,41,426,302,788,800,548,579,620,706,828,549,331,26,627,342,225,312,408,357,641,589,267,649,513,462,464,77,103,38,407,198,340,494,194,631,708,350,72,670,91,388,719,126,441,680,563,646,701,0,552,197,585,701,146,696,816,475,507,586,640,671,361,316,586,379,0,277,773,351,723,523,317,154,296,198,567,515,387,212,14,1,220,284,48,667,193,337,53,354,381,644,224,578,43,476,401,56,425,670,375,691,478,30,353,387,601,778,9,427,699,550,122,430,716,653,315,180,273,796,320,578,514,786,599,244,597,590,582,441,514,802,641,178,232,135,99,240,521,239,575,216,153,505,215,495,49,335,7,679,819,698,643,111,130,577,654,193,236,720,478,90,261,753,237,641,520,544,4,142,670,248,820,473,173,822,541,684,300,123,147,402,117,558,441,469,544,439,634,650,286,411,49,614,50,63,651,603,621,285,625,289,600,532,713,34,572,132,399,261,349,51,255,349,167,814,308,604,620,733,142,331,586,108,235,256,751,777,733,824,637,388,358,377,306,623,104,57,506,431,449,502,338,188,309,106,286,424,60,710,188,61,418,600,640,770,190,441,196,325,747,24,573,691,723,165,602,77,567,466,413,398,694,242,564,203,489,260,8,559,116,194,814,586,479,694,490,555,42,338,137,171,0,201,629,184,78,584,720,141,802,510,600,434,439,788,597,318,695,268,182,422,157,622,358,683,8,460,294,767,538,309,291,624,138,681,51,349,18,188,638,723,556,390,676,409,750,432,452,66,2,62,604,618,797,118,38,160,251,437,370,87,661,182,465,406,682,526,120,93,728,367,228,209,613,184,120,264,529,670,461,561,247,717,793,611,403,251,270,521,812,74,426,417,330,87,459,33,769,555,806,824,442,505,784,596,210,406,166,629,491,534,75,343,832,823,77,309,487,233,299,143,155,77,262,215,384,100,511,294,715,784,106,357,157,77,289,254,244,711,757,560,622,580,535,405,173,471,156,102,448,832,452,197,402,612,193,265,356,222,336,393,312,360,684,471,367,540,692,182,68,106,445,356,571,632,347,761,382,369,743,173,598,523,289,424,704,697,830,553,696,92,523,108,467,720,813,724,689,690,89,217,80,691,26,158,678,173,71,509,454,61,759,421,604,224,46,567,75,77,8,448,828,88,808,145,317,574,145,644,274,699,501,119,476,77,717,359,829,817,122,822,521,51,382,776,433,84,832,119,776,230,549,130,271,368,352,33,615,807,70,120,640,49,151,164,651,457,37,32,538,236,338,626,416,122,664,168,606,420,514,396,627,455,374,138,221,163,794,507,752,297,617,396,221,647,672,599,293,319,249,711,464,536,41,12,221,672,40,709,631,133,412,247,663,428,2,591,336,827,391,511,643,542,767,135,411,588,31,792,829,738,62,15,330,283,123,356,248,578,110,61,675,768,11,414,552,679,545,233,521,265,328,49,142,668,0,76,83,330,663,30,544,579,662,352,794,561,461,36,756,790,813,737,354,629,683,216,547,595,174,172,430,323,795,561,623,517,140,177,348,300,720,517,762,208,771,776,764,299,674,624,516,370,10,461,188,397,172,98,686,82,163,454,420,433,170,219,23,666,633,79,171,516,268,76,811,556,200,540,568,187,771,423,139,702,628,451,777,207,213,750,310,413,798,566,816,487,832,113,496,543,131,318,181,603,297,252,338,673,830,497,819,769,453,463,624,549,129,536,515,355,420,96,450,464,233,616,702,307,152,106,125,760,727,345,754,508,299,564,497,269,400,313,514,276,408,266,392,743,772,578,33,173,688,831,330,455,755,389,422,35,19,481,98,60,215,774,105,555,779,46,203,428,243,14,617,441,791,182,822,305,396,650,289,645,233,285,63,768,751,551,29,109,793,287,356,489,9,279,607,399,822,96,409,278,632,292,670,197,288,24,541,402,390,699,554,596,593,37,112,379,262,566,449,592,712,58,585,46,22,45,288,370,87,58,636,777,531,756,202,411,30,358,466,750,231,424,217,299,728,217,110,486,461,85,220,690,429,445,707,445,381,618,105,55,387,528,282,186,167,218,559,554,804,547,224,19,386,290,640,249,331,204,619,326,169,121,67,687,734,96,380,28,429,648,354,197,561,662,823,648,84,611,243,241,39,789,780,264,153,131,565,718,380,792,332,179,831,182,657,170,279,168,586,677,111,365,745,333,767,253,119,734,251,427,760,627,667,651,258,379,225,713,303,239,473,658,702,690,386,221,443,506,248,503,746,48,22,92,791,429,246,583,561,544,178,50,715,731,329,545,227,172,510,418,269,579,383,530,196,624,323,355,60,186,10,495,186,278,752,349,600,499,638,402,645,598,590,742,260,778,286,385,202,32,7,152,498,814,599,781,416,766,657,754,811,323,122,824,436,744,824,116,504,55,237,536,499,393,412,444,342,601,623,785,82,736,145,202,18,428,240,725,310,569,697,444,180,716,476,480,435,482,245,59,780,655,325,64,73,81,394,620,777,206,324,624,209,109,363,106,739,775,324,676,312,475,529,620,438,119,161,661,510,182,780,117,770,229,301,275,253,321,331,278,593,327,246,269,101,562,280,636,461,826,459,806,659,625,205,281,643,651,483,605,429,735,168,823,681,350,751,113,656,741,518,130,563,60,228,345,734,794,338,472,675,618,128,565,271,302,297,432,286,25,484,183,91,534,346,73,177,635,311,188,731,350,822,796,265,749,205,434,695,496,136,224,313,173,36,360,64,671,514,736,171,159,555,5,814,827,623,578,289,132,653,740,758,742,511,102,611,710,562,213,811,797,804,175,577,229,189,189,613,337,787,241,374,714,243,578,353,503,779,446,375,531,520,592,711,587,20,767,733,499,275,435,405,713,173,656,604,450,691,444,183,689,398,779,28,344,404,306,602,290,395,60,740,223,666,376,78,605,296,804,139,354,305,92,486,559,341,766,766,66,263,435,758,243,679,31,825,569,34,162,347,31,488,31,765,431,447,352,581,404,463,65,454,9,352,717,685,41,524,424,188,9,608,614,707,282,25,676,84,761,486,95,75,561,168,724,140,781,469,295}
{656636,999367,655361,655981,125002,999573,124378,657756,657561,658326,654336,124252,654776,123466,999782,656486,124366,999771,999582,655246,657511,124500,999660,123546,123910,124994,657031,999513,124584,657826,654941,657026,654831,655541,657656,123534,123808,124890,654636,124956,999721,124792,123554,999173,123482,123788,999978,123636,124880,656771,655571,657466,999639,999577,999835,654616,999457,658221,657336,999258,654461,124064,657396,999664,123778,999736,657761,999195,655711,124924,999787,999912,999682,124234,999239,124574,999898,999342,124420,656436,123818,655466,999743,999422,999466,654356,124010,654686,657776,999384,999525,655731,124954,655256,999659,123670,125030,999334,999438,124452,999623,658151,124774,999465,999555,999434,999932,657616,999315,655621,658031,657001,124494,999277,657591,656831,123760,656401,123574,658076,123738,654561,124742,654651,124632,999556,124648,657671,655066,999284,124962,656421,656131,655451,999969,655301,123488,999329,658401,123610,999671,999546,123742,658421,124162,999179,123614,123588,124796,124490,123718,999866,999267,999788,657626,999183,124346,124124,125008,999792,124026,124664,123726,124990,655316,655631,123866,123860,999709,124508,123468,999217,999951,999515,999172,657161,657506,124838,123578,658281,999459,654536,656481,123888,124610,999858,999654,999392,124676,654641,124350,656136,658136,999204,656881,658336,124752,123962,999482,658376,999863,999860,123960,999360,124316,657706,124930,999730,656616,124374,124330,999460,657806,655201,655511,999543,999670,655041,655166,657876,654576,999561,124844,655566,124146,999388,658191,999621,123812,654711,656851,999447,124552,999890,124264,999806,657261,999491,656861,656966,657571,655386,124550,655991,999855,999922,999784,657936,123872,999765,999479,999492,999468,999377,999955,654731,123702,124258,999779,999210,655906,655156,999521,999981,654441,999710,999429,123986,655946,123558,123472,999365,999318,999702,124820,999611,999777,125102,655786,655491,658196,654746,124602,124622,656081,658081,655221,125060,999946,124922,657686,123680,123926,658016,124966,999537,654836,123480,999553,656446,999706,123762,123892,656921,999177,654991,123674,124254,124554,999474,654516,999395,124758,124304,124360,658131,999598,999458,999369,654881,124042,656366,658286,124432,999264,124210,655986,124192,658331,658106,999320,123972,654671,654666,656226,999630,655021,124314,999755,655791,655836,999925,123568,999222,657011,999387,124386,999291,124056,999701,656506,124644,123500,999534,999262,124132,999234,999841,124904,999733,124160,657941,124098,124118,999323,999964,655421,124016,656321,658461,124334,656381,999418,656846,999928,999207,655121,657846,999995,999370,999503,123836,658206,999382,655086,656901,999326,654846,124278,655761,656621,124054,658061,999878,656891,999956,654366,123506,125064,999691,655896,999317,654501,655326,124348,999462,657321,656571,124310,124670,124778,655006,657331,656296,999411,658321,124312,999351,657531,657471,999455,999301,124044,123646,124364,656686,123918,655001,999944,999347,125016,123748,999489,123770,656431,999288,999396,654701,124876,657491,656106,124342,999989,655771,124096,654876,999888,999945,656776,999358,999811,999261,658071,999640,655656,999991,656786,999649,124336,124718,655461,123794,999361,125072,124246,999231,999260,124262,999987,657226,999551,999549,999184,123474,999421,999872,123598,124536,999804,124526,657371,124502,999435,654841,658291,657356,999842,124194,999791,124866,999829,655661,123840,656026,123684,124024,123772,999538,999401,125046,999607,124048,654591,999169,999463,999651,655766,124152,657361,124972,656596,124560,657956,124134,999568,999624,999433,124232,999530,124620,125056,123990,124704,123936,656101,654821,125108,999867,654511,124650,999734,124106,124458,124400,999496,124828,999362,124784,999511,999988,999707,999505,999376,656521,123734,999244,999695,999560,124284,124006,655846,999957,124414,124320,999838,999906,124344,999745,999579,654761,124370,123952,657416,123850,655381,999740,999419,124410,999626,999668,124658,999415,124546,658181,999727,999312,124514,125104,999254,655376,657191,124754,655141,657996,125074,999378,999857,655591,655921,123956,657291,999873,123988,656286,124746,656676,124964,999650,656726,658271,124630,124720,124776,654926,658051,655781,999601,999747,654781,655551,656746,999208,657096,657376,654786,124662,123486,999809,124308,657306,654806,124164,999751,124430,657426,124082,656456,656801,124794,124174,656556,999487,999182,999293,124328,124090,125048,124588,125050,124404,123722,999578,999327,123688,124936,999655,657631,123608,125098,999698,125112,657071,655851,123882,999718,655501,657281,658261,999216,999509,123750,999171,654721,124466,656311,655646,999339,654371,124816,999843,124380,124940,124198,123708,999517,999900,124960,657146,654481,999819,654811,123832,124572,655276,655356,999720,999201,654521,125032,124290,656761,999336,124578,123524,999552,657121,999590,999880,999218,654531,124724,656511,656021,123620,124110,123460,656351,999794,999363,657871,655271,124084,999580,658166,654771,999330,125106,999584,999810,124322,123528,999569,123648,124700,657286,655936,654726,124104,999271,999223,125114,123816,123576,999731,999545,124100,999637,123776,657731,125010,123706,999305,655641,657751,123644,658201,124470,999246,999420,656856,655926,999994,657696,124368,657931,123602,657091,657156,124868,124842,123856,124974,125058,123820,124478,125082,124398,999984,656916,999522,999454,999750,124786,999732,999724,999413,999916,123580,124906,655856,655666,123942,999450,124684,123526,999341,655726,656886,999221,999696,658456,124678,999902,999947,657051,124396,658211,124128,656071,656906,658366,999869,656011,656391,999286,654396,124516,124888,124248,124770,658086,999614,656681,654606,999481,124530,657496,657016,999862,999357,655056,124666,655716,657896,999675,999908,123824,124178,124712,657061,658116,124244,999375,656146,655046,124694,999767,124182,123846,999504,124102,124390,999604,999232,999692,123624,124036,656491,655701,999273,123938,999340,658146,124772,999921,123746,123652,124672,124710,655161,655456,657181,999719,124228,656416,999712,123628,124862,656816,999783,657766,999658,124422,999441,999197,999193,999970,999227,125000,999725,999786,999404,124340,657566,999764,655556,999738,124352,999694,999763,656396,656476,124558,656791,999490,999931,999713,654411,123920,656691,655866,999456,124062,999424,999600,654981,124688,124078,999717,124934,124108,124952,658466,656671,657791,999894,123848,123510,655341,654471,123522,123630,999406,124324,124570,999500,655561,999918,657946,999657,999540,124274,657151,999583,124170,654936,999739,999826,123678,656566,124798,656241,657991,656756,999907,124982,655371,999255,999285,124692,123612,655616,123954,123492,999961,124050,123594,656371,123566,654346,655911,657076,656376,125110,657276,999464,124812,124576,658231,654791,124474,654856,123700,654986,657316,123842,655966,124522,999822,123784,999967,656176,657661,999444,657836,999753,124568,123974,123730,124958,124046,124300,999979,999845,657231,999999,999200,123570,655996,654681,124750,123590,656961,999714,999574,124716,999893,655971,124242,124434,656866,124172,655406,654571,656246,124850,999533,999311,654526,124834,657576,999188,999174,655606,655811,125038,999920,999242,999328,125024,654596,124356,125014,656526,999414,999684,123600,124052,999672,124760,999943,999519,657926,999563,999394,999983,124498,124476,655076,999473,999661,999643,999776,657526,999762,999298,657811,124988,655306,125042,123714,124230,999938,999485,999319,123834,999889,124154,124894,124186,124654,655336,655796,124158,656091,999853,658476,656536,999542,123672,999669,999697,999769,656911,999638,999834,124168,656926,123830,999274,999741,123618,999972,124076,123456,655546,658341,999700,124766,999629,999294,655031,999748,999949,657741,657881,657106,655151,656346,123592,999816,124626,999663,123662,657056,655396,999212,999308,123606,124914,999426,124542,123852,124726,123498,655886,999209,999405,123968,999353,123560,657726,654766,999620,125066,657921,999547,999876,999589,124272,999891,999975,657586,999449,124532,999272,999253,124848,657386,655741,124058,999423,124756,124266,999933,999562,999996,124354,124790,124624,999688,999617,655146,999374,124822,656461,999368,655261,124912,124556,999830,124902,656406,655801,123804,999400,656426,999512,999176,123930,999331,657801,999774,657126,123790,656361,124782,999844,656711,123828,656821,999307,999296,656061,999631,123512,657541,999190,655251,123514,124638,656591,123768,123502,657861,656466,657486,999493,655401,999997,125116,123792,655831,999250,999905,657856,999728,656736,655186,124238,124910,999196,657256,124690,125018,656471,655941,124218,124510,999335,125054,999324,655436,124504,124188,999219,999440,123898,123980,999313,999443,655596,999667,999594,999825,654646,655516,999215,999820,124306,123894,999203,124970,123668,654706,999846,999332,124598,125004,658011,124018,655116,655976,657961,999856,999952,123572,999295,657676,123692,123896,124286,123632,999942,999191,124636,655061,656931,999558,999627,999300,999935,999389,123764,999864,123998,656766,999673,123870,654341,657601,999772,999793,124204,999299,999770,657916,999570,656001,657436,123604,654391,999746,999676,999608,999211,658441,124856,657266,658276,656016,656336,999233,999322,123924,656981,656326,123504,999524,657516,654976,655266,657021,658236,999393,999715,999572,999800,124464,124136,999708,124406,655226,655311,999656,999963,655521,124600,656716,999818,124586,124976,656076,655211,999960,123530,123992,999279,654891,999282,657381,656116,655106,123716,999247,654611,654966,125096,999887,656531,123470,123582,999383,656276,999266,999575,655601,124220,999354,654816,124114,654491,124148,657641,999205,655891,124116,657211,999564,124898,124808,123640,656301,657501,656731,999722,654956,999402,999749,999759,999276,124012,999287,123712,999808,123822,999923,999965,124382,124592,999910,123650,999803,656256,124372,657201,999903,124326,654601,123858,999685,999484,999302,999901,124998,123758,657636,123914,999497,123766,123876,656411,123494,124858,656601,654546,999799,656751,655071,657116,999689,657606,123934,124640,999797,1000000,657911,124362,655391,123682,124270,999364,124836,124450,999333,999235,124714,655291,657796,654906,123552,999185,124480,999824,124214,123874,657301,124086,124506,124294,124996,657441,999268,123676,655441,124854,999990,124886,123868,999986,999805,124460,999495,654916,999453,655101,124216,999861,124616,999518,124520,657781,124206,655126,999535,654351,123520,999408,124534,124292,124942,999557,656701,999781,123864,123844,999870,124926,656206,999683,656586,999924,656386,656741,124138,656646,658411,656996,123886,999930,655131,657221,999885,999499,999662,123736,124004,124824,655536,124094,123932,658451,123478,657771,124288,124446,999249,999742,999475,999467,654626,657906,999966,656796,656046,123654,124436,658391,655776,125062,124212,999379,999488,656141,999711,123660,999897,658481,123798,999817,123906,124744,999854,655526,658361,657986,654716,124948,123564,124928,999837,999780,124706,658121,125086,999875,999390,999653,999680,999851,656291,124800,124236,124486,657351,999181,124540,123664,656546,999927,657166,124840,656871,124518,125118,999241,999593,124222,999761,999766,999265,656086,123950,658226,124454,999306,999189,123720,124596,999237,124488,124358,999815,658436,999859,999228,999350,658111,654996,658351,654696,658306,999251,124196,999471,657131,654496,654451,999381,656096,124968,125084,124830,999206,124180,999756,123970,125034,999548,658036,654796,658266,999610,124184,999936,124882,123538,999977,999202,999356,999821,124088,657451,999648,999520,124900,657366,999941,655281,124008,656271,999849,123616,999283,656971,656341,657556,124140,999915,124872,658161,123536,999428,124852,999892,656041,123622,999729,999913,655686,124696,124686,999599,999865,123658,999939,999899,125052,999263,657711,124190,125120,999373,999220,658026,999850,999452,123806,123916,999985,999778,999168,655931,657136,654486,999828,999827,657551,125090,999958,999536,658426,124144,654866,999934,999417,656991,658406,999840,124226,654331,999678,655826,999886,999976,999281,656051,655481,657891,123978,124156,999243,999445,124418,655496,124412,999831,999399,656261,124810,999813,658301,999259,655236,999591,999397,999618,999187,658216,999248,657701,124590,656516,658056,656451,123966,655016,999372,999186,123780,123540,125020,999744,124566,123862,999588,124606,124408,999407,999348,999904,999448,123802,657391,658381,999606,999726,999502,124826,124538,999514,999587,123586,124986,999681,999416,655676,123946,656251,999470,999602,999752,654416,999982,655051,656121,999576,124240,125006,999998,657646,124282,654961,123976,999480,999430,999359,124768,999980,655011,999954,999642,125078,123756,657111,124944,657041,999529,656581,656941,999236,124762,656576,655736,654581,124122,124338,656171,654466,123826,654911,658156,658126,124674,999224,123634,123694,658251,654676,999386,999636,655901,123940,657241,999790,999616,655111,124142,123542,999775,124846,123562,123958,999917,999446,656066,999427,999412,124814,654426,656666,656541,124916,124302,123948,654421,656006,656876,124788,654551,999823,999310,656896,656611,999199,999785,658316,999170,999911,657341,655476,999647,655296,999225,999425,124028,654661,125022,655841,999566,657536,658471,124080,658396,657476,658021,654556,656641,657141,123928,124646,999619,124984,658386,124698,656186,124892,123884,999214,999652,123584,124492,656196,657951,124604,124060,123532,124512,657066,123496,655806,999478,999592,999432,654921,124642,123732,124950,124562,999704,658091,999230,999632,657421,999836,123880,124074,654361,999290,123518,658066,656331,656166,657901,999613,999795,999909,658296,124548,999737,124150,655471,655531,656211,658431,124428,124832,999586,655706,654586,658446,999757,654376,124112,655696,123982,657036,655681,657401,656706,654756,658041,999973,999385,124748,654326,999758,999950,123900,999690,999325,124416,124000,123656,125044,999641,124256,657736,657456,999398,655091,123626,125068,124804,124176,999716,654506,657216,999437,123728,124860,999879,999802,124802,656606,124736,999526,656216,999674,123796,124040,655871,125100,657611,999554,658046,124066,124730,999703,657786,655816,654456,999645,656781,655581,657681,123774,999192,999352,124394,999516,657431,999346,657886,654381,999409,999666,654886,999585,124444,656236,123544,999609,124426,999883,658141,655026,999929,657841,124318,654541,999693,999528,999269,654736,656936,654476,123912,124918,123724,999345,124818,655651,658416,657621,999812,999316,654321,657581,999436,999337,999292,999240,654431,999476,124032,658001,657981,124908,656306,124020,657831,124732,654386,999289,657481,656201,654901,124608,123904,999483,123516,657596,999768,657196,656151,999612,999380,124738,657411,658176,999559,123782,655671,124938,999314,655881,124722,655181,124680,999180,657046,999848,124932,999884,658346,123462,655096,124298,124896,999343,124864,124280,999439,999226,999833,999304,655506,658101,999839,656561,656951,123490,124438,123890,657236,123710,999773,999371,124260,657716,654656,999948,656161,999541,658256,999705,655486,999523,657296,656221,124442,656126,124946,123690,657446,999198,999754,999338,123754,657176,124978,655446,656111,655081,657406,999798,124484,655231,999868,655821,124652,124384,654801,999953,999238,657186,999278,999679,656031,655351,999442,656656,656721,999597,999735,657346,123696,656231,655426,124582,655416,124030,655366,655411,123854,999596,999178,656036,123642,656806,999882,123548,999245,124564,125092,999403,658006,123838,123550,999539,654861,999527,656501,124376,999175,657821,124022,657971,657816,124208,999391,656811,999603,999410,657651,656441,999544,123996,124296,124806,999665,124884,656826,124544,124780,123786,655746,999321,658096,123556,655721,657171,655626,654621,999881,124070,655206,658356,655916,656356,123810,124660,123964,123878,125012,654631,655961,654946,657851,999971,125094,656316,124268,123698,999565,124482,124870,123464,655216,657271,124618,999832,656496,999677,999571,655286,999472,654406,999506,655196,656631,656986,654851,656181,999686,124462,655756,124392,999270,999633,124708,123596,657866,655036,655951,656661,999213,656651,656841,124448,124764,123814,657976,999852,654871,654401,124332,124038,999550,999510,999622,655171,655346,657206,999297,655876,999194,655611,656056,999789,999760,999501,124388,657081,123484,999595,999477,124734,656156,999926,999451,656946,655191,124092,999532,656976,999508,124628,999507,658246,124580,123666,125076,655586,124980,124126,124200,999605,123908,124612,999807,124120,999355,654751,124920,657461,999494,125088,123752,999635,655861,999275,658371,124456,657326,124874,999962,657691,999644,654971,999847,124468,999229,654691,655241,999796,999937,124682,658186,123508,658241,655751,655331,999349,123944,999634,123744,123638,999257,999914,123458,125080,124130,124524,655636,123984,124528,658311,124878,657521,123922,124276,124002,999877,124496,124166,655956,657101,124014,124702,125040,999919,656266,655691,124072,656696,999959,124668,124202,999461,999280,654951,654436,657251,999974,656956,999895,654566,125028,125036,658171,999303,999486,124728,656551,124614,655321,655576,124634,999366,654446,123994,657966,999309,999687,999567,124424,999993,124656,999699,657546,999256,123740,999940,124068,655176,123800,656191,999431,654896,125026,999344,655136,123902,124402,124740,123686,654931,125070,655431,999469,999646,657311,124250,657746,123476,657666,999498,124594,124440,124034,654741,999723,999531,999814,657006,124472,124224,999581,999625,656626,999252,999874,657721,657246,999992,999615,999801,999628,123704,654826,999968,999896,999871,124992,657086,656836,656281}
Returns: 93855305784
This should hopefully break optimized Bellman Fords (takes at least 15s in Java, so C++ will probably time out too).
Submissions are judged against all 63 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class MaliciousPath with a public method long long minPath(int N, int K, vector<int> from, vector<int> to, vector<int> cost) · 63 test cases · 2 s / 256 MB per case