Anyone has any tests for WA #6? I am out of ideas already. The problem seems too simple... This test helps you: 10 1 2 3 4 5 6 7 8 9 0 4 3 answer: 39 6 Getting WA#11, give some tests pls When do we go from one-dimensional array to two-dimensional? This will be so rad! //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; const int maxn = (int) 1e5; int a[maxn]; int main() { int n; scanf("%d", &n); fo(i, n) scanf("%d", a + i); int p1, p2; scanf("%d%d", &p1, &p2); --p1, --p2; if (p1 == p2) { int sum1 = 0, sum2 = 0; fo(i, p1) sum1 += a[i]; for (int j = p1 + 1; j < n; ++j) sum2 += a[j]; cout << max(sum1, sum2) + a[p1] << ' '<< min(sum1, sum2) << endl; re 0; } bool _swap = p1 > p2; if (p1 > p2) swap(p1, p2); int middle = p1 + (p2 - p1 - 1) / 2 + (((p2 - p1 - 1) & 1) && !_swap); ll sum1 = 0, sum2 = 0; fo(i, n) { if (i <= middle) sum1 += a[i]; else sum2 += a[i]; } if (_swap) swap(sum1, sum2); cout << sum1 << ' '<< sum2 << endl; } Plesae! Give me some tests for check my program. 10 1 2 3 4 5 6 7 8 9 0 1 1 So what is the answer ? Is it 45 0 ? Yes, it should be "45 0". To play optimally, both players would first move towards each other and then from the point of their intersection they will take all the numbers from that point to their nearest boundaries. Let Player 1 start from X and Player 2 start from Y. Then, if (X < Y), player 1 will take all the numbers from A[1] to A[X] and player 2 will take all the numbers from A[Y] to A[N] and also player 1 will take the numbers from A[X] to A[(X+Y)/2] and player 2 will take the numbers from A[(X+Y)/2+1] to A[Y]. if (X > Y) same as above but now player 1 will work from X to N and player 2 will work from 1 to Y. if (X == Y), calculate the sum from A[1] to A[X-1] and another sum from A[X+1] to A[N], add A[X] to the greater sum and give it to player 1. I can't pass test 4, I just can't,,,,, thanks,, problem founded.... Edited by author 29.11.2013 11:03 it's problem with first_pos == second_pos Additional tests for those who stuck here: Test #1 3 1 2 0 2 2 Result 3 0 Test #2 3 0 2 1 2 2 Result 3 0 My algo pass all test discribed in this forum branch, but I can't pass this test :( help me plz! All my tests are working, but on the server WA 2??! Help! Give me some tests...please! I know that the starting positions may be the same! help a newbie) Держи тест: 10 6821 1272 5737 5860 2795 178 2014 2766 5853 1875 3 1 Answer: 28350 6821 У меня тест проходит, WA#6. 14 2642 8283 4175 7165 2543 3135 5667 524 6171 4602 8856 9085 8219 3630 11 8 Answer: 34392 40305 Спасибо за тест Edited by author 17.11.2013 02:10 Thank you! Thanks for answer! I found my mistakes! существует ли способ записи данных в массив без использования строк?? А причем тут строка и массив в принцепи? Берем и записываем в нужный индекс считанное число. // В случае C++ #include <iostream> #include <vector> int main() { int n; int start1, start2; std::vector<int> v; std::cin >> n; v.resize(n); for (size_t i = 0; i < n; i++) std::cin >> v[i]; std::cin >> start1 >> start2; // Решение return 0; } Edited by author 29.07.2014 22:22 any ideas on WA11 (solution passes all the tests posted here in discussions) ? sorry folks I found the mistake it was a runaway loop that was not i < n but i <= n ( less or equal). funny thing that it went through 10 tests with this - I did not expect anything this nasty because it went through 10 tests. I was trying to solve this and I kinda mis-understood in the first place, which makes the problem hard to solve. If the player can decide on the first move (just the first move), then it would be much more complex. For example, 5 1 2 3 4 5 3 3 The current answer is 12 3 because the first player takes 3, 4, 5 and the second player takes 0 2 1 However, if we allow players to skip their first pick, in other words, (move and pick) instead of (pick and move). So there are few more possibilities. if first player picks 3, then the second player can pick 4 and 5 ==> 6, 9 if the first player picks 4, then the second player can pick 3, 2 and 1 ==> 9, 6 maybe I think too much ? :) You helped me to solve this problem. But the result in this test case is 12, 3. :D Edited by author 20.06.2014 10:31 First of all, yes, the two players can be in the same cell, even at the beginning of the game. That only means that the first player that arrived there will take its value. Test: 5 1 2 3 4 5 1 1 Answer: 15 0 Test: 5 1 2 3 4 5 5 5 Answer: 15 0 Secondly, both players play optimally, so it is not a good idea to try and solve this problem using greedy methods. Furthermore, it is not even necessary to try and iterate each move. It suffices to find a technique that applies for each game and then it all reduces to computing a simple sum:) Good luck! If they both start from the same position, who eats the number from that position? If somebody has the same question - the first one eats the number. My algorithm finds the numbers on the left and right, and then compares them, and takes a step toward greater. But if the sum is equal, it compares to one until it finds one larger (and goes upwards). If comparing the results in one step, then goes in the direction of the enemy. What's wrong? Try these tests first test: 10 0 0 1 10 5 100 5 1 0 0 3 8 answer: 16 106 second test 10 0 0 1 100 5 10 5 1 0 0 3 8 106 16 answer: 106 16 I am slowpock. I go AC. Edited by author 17.11.2013 02:14 "Each player has his own specified starting position", means that the starting positions of the players is different? Yes, that actually means it. You could see both positions in the last string of input. No, in test 3, they both start in the same position. "At some moment of time two players can be located in the same cell." If this occurs, who will take the number in that cell? If both of them can take,then they can meet at some point and simultaneously take the number.That will maximize their score. They move in turns, not simultaneously, so even if they end up in one cell one of them (player one) must have stepped there first and therefore he must have taken the points from that cell. Thanks []zhi(Bozhin Katsarski) |
|