Overview
| SHA1 Hash: | d7959f8d5d461e3f8951354bc2713ac479e1beb1 |
|---|---|
| Date: | 2014-07-22 10:38:02 |
| User: | kinaba |
| Comment: | 627 |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added SRM/627-U/1A.cpp version [efb89f3f41758ae4]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 + 22 +class HappyLetterDiv1 { public: 23 + string getHappyLetters(string letters) 24 + { 25 + set<char> cs(letters.begin(), letters.end()); 26 + string ans; 27 + for(char c: cs) 28 + if(can_win(c, letters)) 29 + ans += c; 30 + return ans; 31 + } 32 + 33 + bool can_win(char c, const string& s) 34 + { 35 + string rest; 36 + string cs; 37 + for(char ch: s) (ch==c ? cs : rest) += ch; 38 + 39 + if(rest.size()%2==1) { 40 + rest += c; 41 + cs.resize(cs.size()-1); 42 + } 43 + 44 + while(!cs.empty()) { 45 + if(can_erase(rest)) 46 + return true; 47 + if(cs.size()<2) 48 + break; 49 + rest += string(2, c); 50 + cs.resize(cs.size()-2); 51 + } 52 + return false; 53 + } 54 + 55 + bool can_erase(string s) 56 + { 57 + map<char, int> cnt; 58 + int maxCnt = 0; 59 + for(char c: s) maxCnt = max(maxCnt, ++cnt[c]); 60 + return maxCnt*2 <= s.size(); 61 + } 62 +}; 63 + 64 +// BEGIN CUT HERE 65 +#include <ctime> 66 +double start_time; string timer() 67 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 68 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 69 + { os << "{ "; 70 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 71 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 72 +void verify_case(const string& Expected, const string& Received) { 73 + bool ok = (Expected == Received); 74 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 75 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 76 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 77 +#define END verify_case(_, HappyLetterDiv1().getHappyLetters(letters));} 78 +int main(){ 79 + 80 +CASE(0) 81 + string letters = "aabbacccc"; 82 + string _ = "abc"; 83 +END 84 +CASE(1) 85 + string letters = "aaaaaaaccdd"; 86 + string _ = "a"; 87 +END 88 +CASE(2) 89 + string letters = "ddabccadb"; 90 + string _ = "abcd"; 91 +END 92 +CASE(3) 93 + string letters = "aaabbb"; 94 + string _ = ""; 95 +END 96 +CASE(4) 97 + string letters = "rdokcogscosn"; 98 + string _ = "cos"; 99 +END 100 +/* 101 +CASE(5) 102 + string letters = ; 103 + string _ = ; 104 +END 105 +CASE(6) 106 + string letters = ; 107 + string _ = ; 108 +END 109 +*/ 110 +} 111 +// END CUT HERE
Added SRM/627-U/1B.cpp version [1e90d6c4d0058350]
1 +#include <iostream> 2 +#include <sstream> 3 +#include <iomanip> 4 +#include <vector> 5 +#include <string> 6 +#include <map> 7 +#include <set> 8 +#include <algorithm> 9 +#include <numeric> 10 +#include <iterator> 11 +#include <functional> 12 +#include <complex> 13 +#include <queue> 14 +#include <stack> 15 +#include <cmath> 16 +#include <cassert> 17 +#include <tuple> 18 +using namespace std; 19 +typedef long long LL; 20 +typedef complex<double> CMP; 21 +static const int INF = 0x7fffffff; 22 + 23 +template<typename T=LL> 24 +struct FenwickTree 25 +{ 26 + vector<T> x; 27 + FenwickTree(size_t n) : x(n) {} 28 + 29 + void incr( int k, const T& a ) { // z[k] += a; 30 + for(; k < x.size(); k|=k+1) 31 + x[k] += a; 32 + } 33 + T sum(int i, int j) { // Sigma z[i,j) excl. 34 + return sum_impl(j-1) - sum_impl(i-1); 35 + } 36 + T sum_impl(int j) { // Sigma z[0,j] incl. 37 + T v = T(); 38 + for(; j>=0; j=(j&(j+1))-1) 39 + v += x[j]; 40 + return v; 41 + } 42 +}; 43 + 44 +class GraphInversions { public: 45 + int getMinimumInversions(vector <int> A, vector <int> B, vector <int> V, int K) 46 + { 47 + int N = A.size(); 48 + vector<vector<int>> G(N); 49 + for(int i=0; i<N; ++i) { 50 + int a=A[i], b=B[i]; 51 + G[a].push_back(b); 52 + G[b].push_back(a); 53 + } 54 + 55 + int best = INF; 56 + for(int s=0; s<N; ++s) 57 + best = min(best, solveRooted(K, s, N, G, V)); 58 + return (best==INF ? -1 : best); 59 + } 60 + 61 + int solveRooted(size_t K, int S, int N, const vector<vector<int>>& G, const vector<int>& V) 62 + { 63 + int best = INF; 64 + 65 + vector<bool> vis(N, false); 66 + FenwickTree<int> fw(1001); 67 + vector<int> score_stack; 68 + 69 + function<void(int)> rec; 70 + rec = [&](int v) { 71 + int s = (score_stack.empty() ? 0 : score_stack.back()); 72 + s += fw.sum(V[v]+1, 1001); 73 + fw.incr(V[v], 1); 74 + score_stack.push_back(s); 75 + 76 + if(score_stack.size() == K) { 77 + best = min(best, score_stack.back()); 78 + fw.incr(V[v], -1); 79 + score_stack.pop_back(); 80 + return; 81 + } 82 + 83 + vis[v] = true; 84 + for(int u: G[v]) if(!vis[u]) 85 + rec(u); 86 + vis[v] = false; 87 + fw.incr(V[v], -1); 88 + score_stack.pop_back(); 89 + }; 90 + rec(S); 91 + return best; 92 + } 93 +}; 94 + 95 +// BEGIN CUT HERE 96 +#include <ctime> 97 +double start_time; string timer() 98 + { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); } 99 +template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) 100 + { os << "{ "; 101 + for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it) 102 + os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; } 103 +void verify_case(const int& Expected, const int& Received) { 104 + bool ok = (Expected == Received); 105 + if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; 106 + cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } } 107 +#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock(); 108 +#define END verify_case(_, GraphInversions().getMinimumInversions(A, B, V, K));} 109 +int main(){ 110 + 111 +CASE(0) 112 + int A_[] = {0,1,2}; 113 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 114 + int B_[] = {1,2,0}; 115 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 116 + int V_[] = {40,50,60}; 117 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 118 + int K = 3; 119 + int _ = 0; 120 +END 121 +CASE(1) 122 + int A_[] = {0,1,2,3}; 123 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 124 + int B_[] = {1,2,3,0}; 125 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 126 + int V_[] = {60,40,50,30}; 127 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 128 + int K = 3; 129 + int _ = 1; 130 +END 131 +CASE(2) 132 + int A_[] = {0,1,2,3,0}; 133 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 134 + int B_[] = {1,2,3,0,4}; 135 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 136 + int V_[] = {10,10,10,5,5}; 137 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 138 + int K = 5; 139 + int _ = 1; 140 +END 141 +CASE(3) 142 + int A_[] = {0,1,2,3,0,2}; 143 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 144 + int B_[] = {1,2,3,0,4,5}; 145 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 146 + int V_[] = {10,2,5,3,7,1}; 147 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 148 + int K = 6; 149 + int _ = -1; 150 +END 151 +CASE(4) 152 + int A_[] = {5,7,7,5,5,7,6,4}; 153 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 154 + int B_[] = {2,0,2,0,1,4,7,3}; 155 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 156 + int V_[] = {15,10,5,30,22,10,5,2}; 157 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 158 + int K = 6; 159 + int _ = 3; 160 +END 161 +CASE(4) 162 + int A_[] = {5,7,7,5,5,7,6,4}; 163 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 164 + int B_[] = {2,0,2,0,1,4,7,3}; 165 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 166 + int V_[] = {15,10,5,30,22,10,5,2}; 167 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 168 + int K = 1; 169 + int _ = 0; 170 +END 171 +CASE(4) 172 + int A_[] = {5,7,7,5,5,7,6,4}; 173 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 174 + int B_[] = {2,0,2,0,1,4,7,3}; 175 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 176 + int V_[] = {15,10,5,30,22,10,5,2}; 177 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 178 + int K = 2; 179 + int _ = 0; 180 +END 181 +CASE(5) 182 + int A_[] = {0,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,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,999}; 183 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 184 + int B_[] = {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,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,256,257,258,259,260,261,262,263,264,265,266,267,268,269,270,271,272,273,274,275,276,277,278,279,280,281,282,283,284,285,286,287,288,289,290,291,292,293,294,295,296,297,298,299,300,301,302,303,304,305,306,307,308,309,310,311,312,313,314,315,316,317,318,319,320,321,322,323,324,325,326,327,328,329,330,331,332,333,334,335,336,337,338,339,340,341,342,343,344,345,346,347,348,349,350,351,352,353,354,355,356,357,358,359,360,361,362,363,364,365,366,367,368,369,370,371,372,373,374,375,376,377,378,379,380,381,382,383,384,385,386,387,388,389,390,391,392,393,394,395,396,397,398,399,400,401,402,403,404,405,406,407,408,409,410,411,412,413,414,415,416,417,418,419,420,421,422,423,424,425,426,427,428,429,430,431,432,433,434,435,436,437,438,439,440,441,442,443,444,445,446,447,448,449,450,451,452,453,454,455,456,457,458,459,460,461,462,463,464,465,466,467,468,469,470,471,472,473,474,475,476,477,478,479,480,481,482,483,484,485,486,487,488,489,490,491,492,493,494,495,496,497,498,499,500,501,502,503,504,505,506,507,508,509,510,511,512,513,514,515,516,517,518,519,520,521,522,523,524,525,526,527,528,529,530,531,532,533,534,535,536,537,538,539,540,541,542,543,544,545,546,547,548,549,550,551,552,553,554,555,556,557,558,559,560,561,562,563,564,565,566,567,568,569,570,571,572,573,574,575,576,577,578,579,580,581,582,583,584,585,586,587,588,589,590,591,592,593,594,595,596,597,598,599,600,601,602,603,604,605,606,607,608,609,610,611,612,613,614,615,616,617,618,619,620,621,622,623,624,625,626,627,628,629,630,631,632,633,634,635,636,637,638,639,640,641,642,643,644,645,646,647,648,649,650,651,652,653,654,655,656,657,658,659,660,661,662,663,664,665,666,667,668,669,670,671,672,673,674,675,676,677,678,679,680,681,682,683,684,685,686,687,688,689,690,691,692,693,694,695,696,697,698,699,700,701,702,703,704,705,706,707,708,709,710,711,712,713,714,715,716,717,718,719,720,721,722,723,724,725,726,727,728,729,730,731,732,733,734,735,736,737,738,739,740,741,742,743,744,745,746,747,748,749,750,751,752,753,754,755,756,757,758,759,760,761,762,763,764,765,766,767,768,769,770,771,772,773,774,775,776,777,778,779,780,781,782,783,784,785,786,787,788,789,790,791,792,793,794,795,796,797,798,799,800,801,802,803,804,805,806,807,808,809,810,811,812,813,814,815,816,817,818,819,820,821,822,823,824,825,826,827,828,829,830,831,832,833,834,835,836,837,838,839,840,841,842,843,844,845,846,847,848,849,850,851,852,853,854,855,856,857,858,859,860,861,862,863,864,865,866,867,868,869,870,871,872,873,874,875,876,877,878,879,880,881,882,883,884,885,886,887,888,889,890,891,892,893,894,895,896,897,898,899,900,901,902,903,904,905,906,907,908,909,910,911,912,913,914,915,916,917,918,919,920,921,922,923,924,925,926,927,928,929,930,931,932,933,934,935,936,937,938,939,940,941,942,943,944,945,946,947,948,949,950,951,952,953,954,955,956,957,958,959,960,961,962,963,964,965,966,967,968,969,970,971,972,973,974,975,976,977,978,979,980,981,982,983,984,985,986,987,988,989,990,991,992,993,994,995,996,997,998,0, 0}; 185 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 186 + int V_[] = {137,1000,88,120,582,208,9,350,562,432,981,242,183,459,223,900,186,388,530,952,89,556,868,927,277,912,28,218,835,68,142,489,503,729,238,140,86,155,231,326,989,515,276,187,849,436,548,234,591,57,485,222,924,307,214,528,748,32,817,636,623,479,241,594,715,830,663,739,749,175,889,397,812,466,393,458,866,410,145,317,158,294,511,232,629,118,413,134,875,827,713,942,374,5,25,159,796,37,272,373,957,536,686,762,514,4,150,422,360,494,700,21,525,173,496,92,320,551,412,885,516,36,213,712,44,362,872,23,492,98,77,895,970,292,632,474,226,504,245,152,780,574,626,842,335,247,70,668,707,240,587,611,386,377,461,324,347,547,714,168,55,163,847,851,971,475,549,196,445,726,338,993,608,117,64,406,291,794,974,544,311,604,392,255,356,571,125,104,473,945,829,51,967,176,270,220,249,361,941,681,999,1000,400,658,178,79,275,627,27,677,217,287,982,246,581,280,63,441,184,826,1,201,598,266,435,289,710,421,926,308,965,462,693,674,887,566,876,949,84,731,946,532,96,293,622,521,405,283,928,824,848,793,185,709,428,288,682,304,33,983,382,807,20,327,771,526,107,29,41,61,589,439,774,207,313,938,584,734,575,603,934,278,894,832,583,790,651,735,13,998,899,181,675,169,228,954,524,453,344,988,256,612,881,480,251,416,447,861,891,342,724,69,379,58,787,755,490,914,764,250,100,366,538,133,45,923,925,661,833,404,139,570,878,153,476,640,510,94,102,992,991,588,808,215,6,329,630,420,138,922,325,741,281,654,235,157,786,221,585,761,684,920,939,509,740,389,593,339,606,778,976,264,643,53,834,452,959,273,552,862,483,110,358,518,561,752,792,619,905,631,437,417,50,760,953,290,703,229,99,670,837,702,396,573,470,194,933,664,968,108,803,427,719,537,759,555,381,372,706,672,52,691,917,180,602,932,442,701,224,904,814,628,545,192,72,501,454,297,24,472,285,642,305,770,506,90,364,296,864,73,973,543,368,767,669,690,121,892,298,550,35,87,76,115,825,558,996,143,888,346,129,782,844,870,144,721,613,261,216,75,502,414,487,415,805,777,898,295,401,860,22,321,219,692,783,191,482,529,678,340,541,666,802,995,49,695,597,797,237,434,10,937,964,921,747,638,233,349,577,823,328,947,132,122,963,56,399,863,500,901,425,478,135,310,127,230,659,595,711,341,65,810,789,652,936,568,839,345,689,67,111,212,154,580,854,16,34,151,633,54,517,443,80,209,30,609,621,314,306,610,248,337,596,732,378,756,979,426,172,858,18,813,493,383,685,519,791,601,836,704,2,856,31,534,271,486,81,497,353,463,334,174,166,19,554,471,542,614,114,688,97,488,648,411,244,535,975,728,553,109,82,673,977,316,394,897,407,267,935,484,206,637,641,818,644,333,958,831,39,161,444,720,656,170,969,811,438,204,91,365,819,838,708,911,910,419,846,456,505,758,879,662,744,865,929,768,564,639,653,750,309,586,855,60,705,576,873,160,269,804,569,997,730,351,200,395,972,431,599,560,165,7,164,210,252,650,660,776,448,916,391,559,867,520,357,303,171,418,123,74,687,539,179,944,716,375,119,12,676,785,130,913,930,424,799,620,429,877,101,980,987,15,274,477,754,572,850,763,149,908,769,753,369,315,840,821,880,14,883,635,370,655,513,940,343,788,253,148,457,330,195,961,918,962,262,348,667,199,254,46,605,822,498,727,845,906,182,617,47,286,284,318,696,557,646,376,112,239,956,806,430,423,455,189,380,355,645,624,546,95,909,853,984,717,757,579,540,105,902,615,859,893,698,948,211,227,512,449,371,481,828,93,450,17,886,745,156,300,177,775,131,994,563,190,943,857,843,440,3,665,259,795,11,83,126,202,282,465,634,578,66,103,38,841,398,903,680,592,600,966,820,468,198,40,869,124,671,197,162,319,302,567,403,128,147,363,737,884,896,907,48,116,616,71,390,257,523,990,408,527,260,385,657,331,809,590,736,402,522,193,533,683,499,694,746,188,265,931,106,773,738,919,955,205,647,742,141,951,352,78,798,816,59,607,62,203,915,950,301,978,469,146,531,874,43,495,387,508,751,359,722,882,890,113,263,772,718,42,781,384,167,766,312,26,679,725,765,225,85,268,433,460,446,332,733,279,243,985,852,258,565,464,507,986,236,354,367,625,697,136,336,723,743,322,871,491,784,618,800,299,699,323,8,779,409,467,451,649,1000,1000}; 187 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 188 + int K = 1000; 189 + int _ = -1; 190 +END 191 +/* 192 +CASE(6) 193 + int A_[] = ; 194 + vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_)); 195 + int B_[] = ; 196 + vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_)); 197 + int V_[] = ; 198 + vector <int> V(V_, V_+sizeof(V_)/sizeof(*V_)); 199 + int K = ; 200 + int _ = ; 201 +END 202 +*/ 203 +} 204 +// END CUT HERE