/
盛水最多的容器.py
73 lines (70 loc) · 22.4 KB
/
盛水最多的容器.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#-*- coding:utf8 -*-
#author : Lenovo
#date: 2018/10/9
# class Solution(object):
# def maxArea(self, height):
# """
# :type height: List[int]
# :rtype: int
# """
# #错误解答 我的思路是 定义左右边界 右边界每次加1 然后从新的有边界到左边界依次找比原来大的边界 找到left变为对应边界 找不到则再次更新
# #这样的思路解决一些例子是没有问题的 通过了80%的测试 但是存在一些特例 应该是这个题的精髓
# #我有一个困惑 可能存在局部比存储的结果大导致我们改了letf左边界 但这个左边界并不是全局最优
# #在纸上画了一下 找到这样一个例子 [3,5,1,1,5,1,1,3]
# #按照上面的思路 当right移动到4时 出现 [1,4] > [0,4] 此时将left已经左移 但是最终的结果应该是[0,7] 而不是 [1,7] 说明这种思路是有问题的
# #我又产生了另一个办法 当我们每次需要左移时，存储被左移的left 的索引 和此时的右索引 当我们得到最终结果时 在把存储的左移的索引所对应的结果 进行比较 是不是能够解决错误的情况 使用例子 [1,1,3,5,1,1,5,1,1,3,1,1]
# left=0
# right=1
# end=len(height)-1
# tem=[0]
# res=min(height[left],height[right])
# flag=1
# while left<right and right<end:
# right+=1
# for i in range(left,right+1):
# ss=min(height[right],height[i])*(right-i)
# if ss>res:
# if i!=left:
# tem.append(i)
# print(i,height[flag])
# left=i
# flag=right
# res=ss
# print(tem)
# print(flag,height[flag])
# for i in range(len(tem)):
# res=max(res,min(height[flag],height[tem[i]])*(flag-tem[i]))
# return res
#别人的代码 思路如下 对比我的代码 （每次只是移动右边边界）。。
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
"""
逼近法
每次左右两端都舍去短的那一端
若选择短的那一端【S=小于等于此端的高*小于等于当前的最大区间长度】
至多的面积也是选择最左最右的一个矩形，因此不必再考虑短的一端，直接舍去逼近
"""
# 记录当前最大容量的面积
max_area = 0
# 记录最左边的下标
left = 0
# 记录右边的下标
right = len(height) - 1
# 当右边下标大于左边下标的时候循环
while right > left:
# 当前循环中最大的容量面积，使用max方法比较上次的max_area和此次的容量面积，取最大值
# min(height[left], height[right]) * (right - left) 取左边和右边的高当中的最小值， 下标right-left为宽，两者相乘为最大面积
max_area = max(max_area, min(height[left], height[right]) * (right - left))
# 判断哪条高小，小的那边下标进行操作
if height[right] > height[left]:
left += 1
else:
right -= 1
return max_area
S=Solution()
res=S.maxArea([28,342,418,485,719,670,878,752,662,994,654,504,929,660,424,855,922,744,600,229,728,33,371,863,561,772,271,178,455,449,426,835,143,845,321,214,867,199,967,881,193,973,386,122,633,810,330,907,906,282,136,986,315,860,849,229,632,473,759,87,922,185,922,418,382,243,632,250,795,599,131,988,924,869,463,558,680,145,465,938,427,954,925,94,814,126,323,798,599,434,885,874,620,159,292,354,755,924,956,550,876,88,890,800,309,705,358,989,850,176,280,629,130,205,724,296,331,399,94,283,186,331,157,806,490,801,512,597,725,469,499,601,909,390,754,218,447,112,560,298,640,840,279,122,397,355,418,80,755,864,363,293,195,872,451,38,673,963,635,751,432,487,352,341,229,458,912,676,923,472,326,563,312,606,686,709,313,456,789,420,321,505,713,868,377,164,258,403,128,246,154,912,733,858,606,962,317,518,990,240,990,317,803,302,275,841,363,588,650,504,9,323,9,74,191,387,239,450,790,367,48,944,279,781,802,885,743,471,755,85,711,745,402,867,399,29,708,762,970,710,267,331,33,276,405,577,15,644,379,157,363,427,453,995,208,608,232,303,79,988,388,791,733,143,658,133,524,718,247,846,429,514,529,814,143,935,743,510,931,122,668,647,901,473,642,461,81,874,764,513,214,505,304,948,0,314,433,876,384,680,75,165,547,604,980,42,891,75,552,823,198,572,822,451,46,816,913,479,42,29,992,257,886,648,557,238,962,990,115,699,22,190,864,921,794,196,315,686,272,868,861,822,792,35,273,190,851,186,670,893,568,662,150,454,311,59,693,625,49,808,324,424,350,189,697,496,737,13,534,9,881,747,831,25,782,457,216,985,643,886,879,211,900,381,18,211,441,711,837,842,871,513,618,573,702,316,69,440,329,956,801,562,703,633,587,486,90,803,471,85,41,702,649,942,436,19,505,877,730,342,71,953,856,690,526,910,6,947,702,335,903,504,249,607,489,836,445,931,992,268,368,33,971,369,327,407,388,833,636,470,527,59,423,735,749,301,646,107,249,700,794,504,556,43,111,397,232,908,328,224,177,49,609,500,418,937,259,159,770,247,629,297,306,405,33,408,706,31,867,955,83,662,460,640,57,923,37,289,832,718,865,361,119,475,213,537,412,472,48,534,71,678,183,377,83,568,137,141,599,5,449,35,19,261,675,76,184,64,366,368,134,583,81,253,58,294,143,822,118,191,356,189,221,892,919,656,460,56,798,412,61,247,447,80,508,474,509,44,538,227,765,673,810,846,278,869,493,421,43,611,613,752,153,834,644,72,491,456,128,641,868,542,888,315,974,748,141,483,144,32,710,909,705,873,108,983,94,601,757,137,564,370,241,69,556,885,141,47,694,622,688,562,516,928,230,490,28,371,326,173,403,388,82,460,613,542,796,707,495,553,197,412,275,438,481,831,676,623,231,370,597,271,284,113,200,514,955,228,238,633,753,993,374,188,806,987,730,602,695,226,507,892,638,782,330,471,965,358,94,196,728,43,468,365,508,20,879,464,600,469,449,354,463,823,542,621,811,624,223,506,850,82,750,840,216,432,312,181,791,758,730,871,802,550,236,310,570,468,126,522,289,576,228,104,751,122,725,562,747,300,420,949,382,170,790,950,603,454,132,746,564,214,969,366,764,206,29,686,26,507,208,315,435,789,420,187,911,145,101,658,446,522,608,180,692,750,131,647,556,615,393,120,181,363,839,945,921,220,983,299,727,543,614,515,332,386,54,244,884,155,254,682,29,214,862,722,964,345,721,520,960,467,993,141,182,832,438,455,52,421,754,131,317,720,646,649,107,52,245,343,208,500,25,589,714,239,311,31,585,385,903,897,852,896,391,386,728,181,841,780,955,595,264,272,315,262,921,774,315,167,117,875,19,494,464,733,86,128,116,671,513,20,920,717,916,663,103,997,845,944,129,800,891,393,72,558,656,345,333,971,512,802,846,883,649,662,617,735,790,733,406,655,105,678,372,374,342,827,371,187,123,500,339,14,246,411,573,902,108,258,225,973,60,423,856,709,85,473,444,876,559,202,531,16,233,256,390,575,83,761,114,559,614,453,573,860,216,498,114,324,756,339,649,169,762,506,230,199,979,27,427,890,581,311,259,814,567,649,389,2,763,855,561,377,660,487,589,228,337,703,905,446,42,554,615,156,60,197,707,392,576,135,282,158,446,541,324,365,543,66,367,306,921,281,35,582,768,624,810,457,327,715,903,721,270,870,229,682,68,936,74,996,423,709,154,221,250,479,586,145,545,306,451,818,587,486,400,707,462,563,164,789,630,420,862,252,290,443,935,358,732,9,355,155,718,861,729,321,692,315,466,237,973,270,56,560,108,808,619,571,723,136,712,354,556,927,958,846,370,893,557,454,255,264,610,325,477,339,998,170,6,817,759,980,87,815,892,547,976,864,470,51,0,183,405,908,462,716,754,184,961,663,639,216,927,249,894,405,940,892,927,298,709,686,630,148,854,523,696,830,387,166,881,739,701,639,647,163,707,401,348,668,417,987,237,344,588,131,101,880,375,28,178,85,67,161,233,921,684,929,103,423,448,984,162,149,975,809,665,682,562,13,703,979,352,940,676,940,423,777,172,798,158,702,883,225,863,469,498,899,750,601,322,198,937,484,348,265,293,365,299,856,378,2,187,82,294,863,374,717,993,546,516,151,248,751,728,464,220,578,363,971,179,686,169,116,522,869,381,168,234,681,376,964,35,563,46,330,427,420,47,420,318,915,923,919,667,3,383,239,581,98,562,760,136,732,228,659,953,962,827,540,995,203,856,30,118,903,712,545,675,112,317,994,27,240,913,46,243,648,638,824,746,200,936,883,284,165,894,590,127,721,130,474,276,986,504,394,241,217,292,269,329,609,263,708,202,528,107,797,176,745,974,274,945,910,157,582,427,403,172,906,124,302,380,752,640,885,499,234,454,791,503,135,752,118,843,954,646,302,104,174,47,78,800,345,988,310,927,416,713,99,322,838,753,55,942,745,940,441,979,746,584,482,881,337,952,76,643,598,379,747,124,778,825,925,123,166,235,402,934,948,853,608,138,606,663,81,704,955,874,683,701,459,518,934,148,470,363,791,421,94,891,545,872,68,822,348,234,57,102,168,358,956,129,496,914,792,929,618,748,804,654,801,263,524,736,411,994,451,554,767,545,797,313,769,866,487,117,452,545,572,973,903,528,102,751,442,246,681,413,994,485,67,148,100,591,236,863,937,687,417,705,232,567,370,353,433,857,823,237,754,395,210,9,923,664,113,717,911,794,482,257,631,549,405,83,492,641,946,782,328,715,839,912,282,561,266,715,418,89,305,525,484,515,534,759,532,999,476,443,793,959,700,776,860,106,859,705,99,805,839,428,873,678,692,155,239,958,223,9,399,528,886,235,395,773,994,927,772,823,722,566,134,423,694,346,881,554,403,332,711,242,760,584,272,805,740,863,763,315,873,515,843,759,750,238,884,745,518,657,568,240,575,54,15,269,400,248,175,804,581,887,398,693,823,671,498,915,534,262,230,759,129,425,871,879,664,755,624,534,412,544,774,987,950,790,257,351,390,784,507,971,671,905,665,847,928,163,762,463,777,345,574,906,770,445,786,786,201,762,320,965,659,95,953,609,237,562,312,979,346,819,951,370,77,616,569,357,131,331,820,909,28,747,167,799,192,953,585,745,68,906,711,727,353,16,688,942,930,1,921,628,172,224,350,601,192,919,959,324,251,131,585,279,878,752,430,423,58,16,168,126,274,231,205,979,247,893,921,177,246,194,158,419,419,508,20,963,428,331,639,31,463,224,662,341,329,93,764,739,461,285,217,735,516,422,714,764,667,987,293,914,533,451,685,304,960,57,268,740,389,907,771,852,484,433,545,165,878,310,904,339,947,121,426,463,895,492,579,914,831,873,828,365,676,865,21,988,923,289,728,312,549,851,516,385,637,61,550,515,723,806,207,670,927,985,134,174,478,713,88,309,938,269,26,615,134,48,955,409,689,684,721,590,887,589,975,524,651,877,392,726,683,599,397,962,584,883,136,414,948,577,724,239,846,102,206,332,150,161,742,192,197,815,782,85,405,758,609,408,635,353,134,671,952,883,633,889,118,122,655,419,699,731,658,897,834,216,229,336,377,323,528,927,139,311,12,896,69,973,304,56,679,790,727,631,674,361,872,792,483,528,563,534,259,221,431,445,437,12,782,167,336,310,94,827,621,458,723,42,783,379,99,462,169,826,446,843,539,670,988,374,550,551,908,162,125,691,607,914,704,389,81,392,52,527,571,673,337,294,716,473,25,167,935,194,993,733,38,885,404,378,259,306,281,168,468,406,211,76,321,915,817,754,659,869,634,230,895,323,876,611,796,253,778,84,448,123,817,838,8,573,216,268,880,849,788,348,256,999,776,929,267,594,683,278,815,669,861,710,993,89,673,789,343,803,225,791,927,43,981,287,968,549,907,848,398,47,549,654,47,325,583,666,271,619,944,439,640,805,149,633,895,175,775,590,978,0,381,257,395,714,545,364,263,804,564,661,852,113,668,899,791,603,917,414,222,861,205,863,19,355,848,914,530,623,856,860,976,237,118,371,303,15,87,566,819,652,579,671,117,247,922,260,851,839,27,425,53,232,640,72,587,489,338,469,464,194,682,440,783,800,812,86,167,899,652,986,903,231,10,21,831,284,281,682,476,308,107,529,893,748,601,832,589,939,302,53,485,336,494,268,136,658,354,303,909,358,641,813,941,651,186,772,288,467,454,764,128,914,293,21,14,246,853,603,537,507,656,22,843,502,290,331,160,996,986,70,706,628,235,647,631,421,420,919,888,226,35,368,492,328,741,506,926,947,461,463,806,118,485,2,972,127,685,133,475,672,555,181,652,790,181,635,211,953,555,451,179,942,820,24,271,913,530,197,212,992,13,19,462,850,373,434,330,58,919,805,82,474,339,734,264,872,370,475,825,277,927,4,219,99,380,842,364,911,392,577,255,405,948,69,255,321,855,585,731,775,743,814,601,434,548,866,306,270,693,131,547,620,487,119,71,868,961,436,131,705,365,738,110,313,159,366,986,14,303,717,141,398,883,743,832,432,961,138,54,654,621,954,627,109,73,698,329,386,486,812,92,851,550,554,516,709,920,502,75,576,572,217,974,455,312,807,239,273,297,646,927,919,600,906,380,25,957,61,763,443,873,207,647,423,762,163,484,34,18,559,610,942,128,937,749,440,96,341,65,393,987,993,664,587,251,396,964,208,457,727,652,330,935,651,105,697,166,589,731,536,501,694,478,981,631,580,422,727,921,839,472,908,832,137,847,84,533,811,644,991,538,296,673,825,299,779,522,466,720,606,2,221,300,833,203,283,413,977,362,334,816,834,594,1,323,441,437,209,604,81,552,142,730,225,968,29,4,842,847,77,448,850,298,100,35,853,735,448,182,97,134,351,284,728,704,959,521,493,168,125,926,720,619,8,946,939,390,302,782,237,731,582,439,30,35,474,235,770,922,770,220,408,473,856,136,529,815,9,374,984,486,300,704,106,661,2,45,51,657,179,640,388,114,80,770,149,554,358,271,829,480,843,237,953,699,726,834,515,735,208,851,222,508,555,680,521,910,77,572,919,609,213,307,723,293,430,872,199,788,495,28,268,339,618,573,38,344,407,905,431,615,756,5,475,664,685,997,574,115,921,493,724,134,152,447,779,582,671,331,370,518,359,990,857,329,563,248,673,322,153,105,289,262,462,765,926,500,114,852,615,35,345,691,522,849,490,653,432,513,984,154,31,696,145,889,25,60,489,51,383,642,508,672,904,970,789,182,470,255,34,437,643,731,128,165,581,618,170,13,483,155,519,515,203,664,756,228,77,245,631,812,239,139,836,496,110,978,678,932,233,713,722,876,796,850,41,377,821,564,742,304,719,262,171,274,278,927,502,355,524,486,519,764,625,356,612,87,334,642,20,567,707,742,444,504,944,837,881,117,401,624,774,472,238,945,746,516,225,601,224,749,87,743,513,64,99,477,152,785,120,524,705,827,266,501,331,562,338,213,32,92,189,806,916,427,103,15,295,328,968,519,78,407,263,943,471,714,421,623,852,541,147,557,368,765,58,700,680,748,265,712,192,454,870,109,233,973,476,528,302,444,48,380,851,663,323,674,729,744,650,581,637,149,490,6,267,548,58,947,297,323,11,841,129,881,950,362,206,778,890,508,222,290,240,425,305,916,100,387,660,102,320,298,251,811,656,518,711,714,817,360,37,828,202,518,61,504,880,268,283,122,128,857,765,369,283,422,637,735,809,297,189,482,947,440,645,955,959,356,669,776,69,58,957,271,576,18,127,808,638,410,931,119,268,48,840,903,470,477,990,632,126,179,114,426,971,759,381,930,467,403,59,536,813,16,159,742,386,287,550,377,49,833,496,317,881,688,572,352,165,914,336,291,445,450,69,417,561,451,699,380,206,110,917,19,478,428,761,217,715,664,594,765,497,442,434,379,130,359,83,647,625,419,290,423,221,360,192,134,163,891,514,369,2,783,740,832,564,854,49,279,518,643,396,15,437,183,746,919,894,829,566,519,600,857,294,173,217,486,307,380,378,174,101,732,309,841,916,873,695,966,505,213,961,253,229,399,788,975,318,682,157,885,554,109,742,848,283,311,335,942,691,65,468,792,149,778,985,65,3,681,31,860,894,345,466,475,744,254,803,62,289,312,299,843,421,393,43,56,704,730,999,747,147,467,891,648,597,877,714,953,558,97,813,804,442,279,632,538,534,787,953,823,99,252,18,872,998,413,929,702,496,280,802,643,747,693,292,697,570,358,650,128,807,463,285,602,95,917,140,629,704,445,804,155,50,174,27,48,939,308,750,435,588,904,431,688,598,723,385,168,433,35,649,592,850,934,194,945,203,687,926,907,132,730,414,182,256,793,582,196,102,685,983,690,589,414,378,187,489,115,356,922,150,357,867,1,291,61,946,494,100,873,753,585,955,167,119,564,312,702,760,414,387,95,457,976,510,187,516,999,303,224,274,453,581,141,806,872,554,105,718,655,978,471,592,285,990,711,849,302,765,961,69,504,57,526,833,567,713,349,918,368,573,192,174,154,333,980,378,888,85,96,895,415,919,487,701,261,550,902,915,668,216,984,172,273,862,5,192,928,706,462,296,279,655,470,785,340,451,163,580,888,611,827,304,882,314,357,143,217,611,59,237,827,395,409,100,258,767,644,186,473,107,482,105,114,305,890,806,756,406,387,996,17,214,300,900,881,9,43,450,621,454,687,448,850,96,901,460,215,897,646,689,356,480,794,470,785,36,277,893,442,16,890,460,230,542,712,111,904,107,913,525,562,600,973,764,49,226,224,264,124,222,953,480,54,99,303,192,136,580,437,578,948,679,390,178,222,102,642,478,210,555,3,772,156,328,888,557,907,464,821,31,38,775,863,444,226,166,636,362,98,74,293,46,753,683,577,327,786,219,157,996,126,160,120,634,841,360,191,748,824,13,131,862,140,994,306,718,513,295,81,611,721,726,10,826,409,587,506,547,158,663,543,284,824,15,919,17,375,462,765,199,475,896,413,967,242,72,686,755,367,119,367,440,845,729,266,606,316,772,154,474,436,697,110,612,65,29,629,440,844,746,992,319,994,405,639,236,829,677,992,548,796,711,988,993,440,255,599,108,27,105,934,815,155,44,427,220,74,408,660,918,154,652,589,148,410,580,737,239,257,729,788,405,792,776,750,584,383,702,692,763,807,626,578,962,670,358,182,96,766,195,366,273,199,308,421,609,240,158,201,850,239,341,255,31,469,6,967,853,60,659,616,867,637,546,182,660,904,364,108,671,911,475,944,111,135,717,72,375,228,273,225,819,614,833,203,84,191,170,289,251,830,905,470,819,803,652,479,708,369,588,731,280,415,27,743,902,744,816,277,324,441,855,144,56,40,347,492,583,869,781,834,51,38,656,871,841,309,350,549,678,290,632,310,705,659,406,607,756,222,237,80,15,444,576,423,484,275,915,419,145,48,253,196,86,909,67,280,570,770,181,600,60,814,263,118,473,669,725,229,243,314,662,258,758,238,682,594,514,597,13,659,998,618,207,436,880,275,716,802,45,250,403,457,64,666,575,889,335,301,471,930,967,133,188,726,723,870,672,237,820,38,248,818,656,456,606,536,83,323,339,128,925,94,937,989,112,513,230,799,166,701,729,133,186,917,211,910,788,884,499,960,922,748,130,930,556,736,819,639,411,510,119,336,604,56,677,716,569,908,515,87,961,244,221,500,513,784,410,653,20,909,613,294,9,743,225,565,480,44,204,891,906,323,580,510,732,257,578,653,517,445,741,479,41,314,979,554,98,741,208,471,2,173,765,12,917,990,577,749,386,134,992,292,809,572,154,541,830,84,195,347,529,288,178,570,602,509,477,52,250,685,523,253,858,641,265,127,631,194,876,370,680,869,14,490,441,169,383,623,253,930,971,135,218,149,705,820,659,534,225,261,219,100,514,430,741,131,909,373,678,138,95,358,7,109,200,800,630,936,424,236,866,747,371,85,248,428,257,259,963,482,521,534,583,387,316,324,871,226,49,549,364,496,259,723,958,812,875,588,748,651,176,614,398,547,51,999,328,309,258,291,143,131,825,726,871,494,403,94,72,804,995,436,301,254,511,611,418,738,199,518,390,376,133,140,275,184,139,603,845,750,246,989,233,424,67,456,918,470,550,990,627,545,778,280,152,641,891,570,379,90,89,121,818,574,262,446,110,753,401,956,855,648,945,441,424,12,249,694,835,800,684,462,697,814,742,849,807,633,772,538,75,213,660,246,787,274,44,249,379,445,205,587,445,502,380,869,867,629,563,54,429,599,868,479,765,610,328,572,595,452,463,22,665,123,620,804,749,664,54,480,110,611,67,907,466,447,129,685,77,692,739,858,644,607,337,761,569,18,686,516,470,149,538,136,624,159,292,373,175,698,853,285,310,273,545,128,720,674,165,149,718,904,8,714,863,345,476,784,715,162,300,186,311,190,674,287,701,966,660,877,665,865,514,327,138,59,807,211,733,972,360,804,876,720,518,91,418,994,875,133,508,175,319,819,717,993,458,419,312,470,296,977,336,810,656,826,870,463,389,955,435,750,759,311,470,630,754,888,624,629,374,133,156,693,304,873,39,763,292,351,233,940,680,921,751,336,100,973,799,489,280,234,239,392,545,62,22,299,302,998,280,676,483,436,722,788,309,761,903,954,464,488,894,144,410,997,480,510,970,279,351,603,513,591,995,410,5,369,61,659,367,341,688,851,129,410,991,438,523,894,744,987,382,639,131,144,988,611,6,311,242,358,914,755,301,261,517,306,630,578,317,349,919,5,552,48,415,543,838,290,789,935,277,524,926,760,668,914,371,675,225,965,33,491,72,686,752,589,992,734,167,661,436,438,667,988,838,434,884,29,725,673,964,354,197,242,115,218,156,838,893,734,804,278,225,876,964,330,466,308,416,985,969,852,776,988,841,614,775,725,995,500,750,311,854,948,553,969,166,62,808,411,796,964,41,373,840,357,703,658,17,120,996,338,324,772,327,165,738,102,242,86,954,993,397,160,293,303,130,459,365,290,222,513,606,615,886,446,972,942,457,989,414,453,327,738,577,6,904,315,460,498,401,414,491,151,575,784,454,57,595,819,699,169,332,305,784,570,103,108,512,560,449,926,365,777,665,942,135,921,610,596,419,11,362,911,514,289,47,968,698,643,787,397,164,471,54,949,42,158,57,906,70,507,833,788,636,850,730,123,123,692,71,542,56,434,805,570,75,853,539,774,848,678,171,12,150,578,313,544,736,723,802,158,230,987,946,218,837,29,693,960,721,765,855,777,199,660,348,274,865,239,400,713,917,924,78,419,502,391,315,590,114,118,748,696,105,47,266,295,428,960,255,149,725,110,279,924,123,979,550,988,218,951,702,135,875,780,907,729,523,222,319,638,340,419,686,798,466,953,93,894,913,700,396,638,163,675,914,286,654,816,274,224,119,328,359,994,460,618,75,984,841,394,974,533,166,660,331,984,613,776,879,526,477,627,516,992,654,430,278,660,599,904,884,718,233,595,65,45,214,140,29,407,887,3,940,53,16,624,37,629,752,268,508,581,895,376,573,901,807,851,561,406,756,445,124,341,393,541,386,607,682,768,14,569,123,306,622,139,282,11,121,35,280,981,616,527,357,190,429,164,393,342,922,149,788,399,842,181,940,229,140,974,997,506,543,120,812,517,612,95,881,733,130,161,714,746,40,71,288,469,588,682,164,862,183,952,613,26,485,906,607,977,880,604,483,776,76,295,645,40,742,526,125,872,39,839,971,80,263,611,901,203,293,65,417,829,369,383,855,206,289,462,183,521,418,18,649,846,314,295,887,408,173,12,633,213,204,604,645,819,567,898,374,213,316,143,42,685,526,897,244,815,711,427,689,481,446,338,327,112,633,566,520,159,931,153,724,487,109,721,306,677,619,32,242,935,175,284,973,54,181,217,869,244,996,910,725,442,249,52,906,234,971,779,393,902,932,469,389,394,190,47,423,810,431,665,97,958,949,70,12,482,639,234,726,636,144,451,430,393,855,337,628,826,116,373,80,400,843,469,794,33,868,569,195,299,234,293,258,183,715,622,17,355,856,743,991,1,546,421,394,402,110,374,228,226,748,309,979,943,130,773,976,351,695,524,2,929,817,612,465,884,235,482,239,91,226,582,92,772,4,839,526,466,213,107,45,313,768,24,256,250,149,585,601,844,109,604,774,278,216,239,162,803,73,402,895,299,984,339,424,340,178,302,159,744,409,204,57,177,228,666,428,729,251,381,574,360,985,700,990,554,291,152,357,364,906,604,16,243,944,792,583,474,94,94,570,504,298,980,33,526,646,813,608,249,195,182,961,532,882,951,438,525,103,796,889,10,752,905,253,696,49,188,523,144,635,93,0,933,425,385,812,71,551,420,320,746,602,281,630,836,584,69,361,688,217,602,50,969,860,655,18,909,195,541,405,830,986,757,764,412,143,928,835,694,348,508,792,302,141,422,490,726,491,851,766,708,805,816,30,665,823,48,927,370,941,332,201,279,90,317,43,585,245,879,279,945,387,71,247,880,845,737,606,689,940,372,749,97,540,779,115,363,179,42,86,120,374,287,400,816,956,443,401,553,674,32,498,413,455,97,294,301,186,900,990,478,625,91,575,165,871,690,881,50,732,967,523,459,606,923,627,914,718,29,467,393,413,317,158,869,766,452])
print(res)