Show all threads Hide all threads Show all messages Hide all messages  WA 2, pls help me, what's wrong?  Bogdanov Klim  1663. The Hobbit or There and Back Again 2  29 Jul 2017 23:10  2  #include <iostream> #include <string> #include <map> #include <vector> #include <cctype> #include <algorithm> #include <math.h> #include <iostream> using namespace std; int main() { int N, ch; int h = 1; int max = 0; int second_max = 0; cin >> N; vector <int> m(N); vector<int> v(N); vector<int> k; for (int i = 0; i < N; i++) { cin >> ch; v[i] = ch; } for(int i = 1; i < N; i++) { if(v[i] > max) { second_max = max; max = v[i]; } else { if (v[i] > second_max) { second_max = v[i]; } } } for (int i = 0; i < N; i++) { if (v[i] != max && v[i] != second_max && v[i] != v[0]) { k.push_back(v[i]); } } sort(begin(k), end(k)); m[0] = v[0]; m[1] = second_max; m[N  1] = max; for (int i = 2; i < N1; i++) { m[i] = k[k.size()  h]; h++; } for (auto j = 0; j < N; j++) { for (auto i = 0; i < N; i++) { if(m[j] == v[i]) { cout << i + 1 << " "; i = N; } } } return 0; } Please explain your solution  Any clue for this problem?  Vedernikoff Sergey (HSE: АОП)  1663. The Hobbit or There and Back Again 2  5 May 2009 14:17  3  How to solve it? Any hints? Thanks in advance. We must minimize the value of [1000/P1]*Pi1 + [1000/P2]*Pi2 + ... + [1000/Pn]*Pin, where (i1, i2, ... in)  some permutation of (1, 2, ... n), which defines the cycle. If we forget about the cycle, the minimum value will be reached when i1=1, i2=2, ... in=n (think why). I obtained the solution using this idea and intuition) If you need more help, you may email me P.S. I would be very thankful for any help on 1653 ;) Edited by author 05.05.2009 14:22 Thanks, I'll think. Regarding problem 1653  I didn't face any troubles with test 16 of the problem, so I don't know what's the reason for such verdict. Check  maybe your program just handles some solids incorrectly? IMHO, it's the only reason. If you still need help  mail me at goryinyich[youknowwhat]inbox[youknowwhatagain]ru Edited by author 05.05.2009 14:18  Basic test  Ekvilon  1663. The Hobbit or There and Back Again 2  18 Jan 2009 16:38  6  If Hobbit moves in order 1>4>2>3 (like in basic test answer), he will pay 2816. But if he moves in order 1>3>4>2, he will pay only 2050. So why minimal price way is "1 4 2 3"? 1>4>2>3 10*1000/4 + 4*1000/3 + 3*1000/5 = 4433 1>3>4>2 10*1000/5 + 5*1000/4 + 4*1000/3 = 4583 So? 1>3>2>4 10*1000/5+5*1000/3+3*1000/4==4415 Edited by author 20.12.2008 15:07 Edited by author 20.12.2008 15:07 Why not so! 1432 4*[1000/10]+5*[1000/4]+3*[1000/5]+10*[1000/3]= 4*100+5*250+3*200+10*333=400+1250+600+3330=5580 and 1423 4*[1000/10]+3*[1000/4]+5*[1000/3]+10*[1000/5]= 400+750+5*333+10*200=1150+2000+1665=4815 and 1432 is better! Edited by author 10.01.2010 05:25 Edited by author 10.01.2010 05:28 Read the task carefuly! "Remember that Bilbo starts his travel from the city with number 1, visits each city exactly once and returns to the city with number 1 only in the end." Bilbo will return to city 1 in the end, so we must calculate the cost of 1>4>2>3>1 and it is equal to: 4*[1000/10] + 3*[1000/4] + 5*[1000/3] + 10*[1000/5] = = 4*100 + 3*250 + 5*333 + 10*200 = 4815. 

