|
|
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 < N-1; 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 e-mail 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[you-know-what]inbox[you-know-what-again]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! 1-4-3-2 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 1-4-2-3 4*[1000/10]+3*[1000/4]+5*[1000/3]+10*[1000/5]= 400+750+5*333+10*200=1150+2000+1665=4815 and 1-4-3-2 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. |
|
|
|