ГЖО 7-8 класс 2019 год

Есеп D. Жан достар

Уақытка қойылған шектеу:

1 second

Жадқа қойылған шектеу:

256 megabytes

Айбай мен Абар ойын ойнап отыр. Оларда $a$ және $b$ оң бүтін сандардың екі массиві бар. Айбай $a$ массивіндегі екі көршілес сандарды алып, оларды сол екі санның қосындысымен ауыстыра алады. Мысалы: $[2, 4, 1, 7]$ -> $[2, 5, 7]$. Абар сондай операцияны $b$ массивімен жасай алады. Олар жақсы достар болғандықтан, нәтижесінде алынған массивтер бірдей болуын қалайды. Бірақ, олар үлкен массивтерді өте жақсы көреді, сондықтан алынған массивтердің ұзын болуын қалайды. Алынған массивтердің барынша мүмкін ұзындығын табыңыз.

Оқу форматы

Бірінші жолда $n$ бүтін саны бар $(1 \ le n <= 300000)$ — бірінші массивтің ұзындығы. Екінші жолда $a_{1}, a_{2}, ..., a_{n}$ $(0 <= a_{i} <= 10^9)$ - $a$ массиві. Үшінші жолда $m$ бүтін саны бар $(1 <= m <= 300000)$ — екінші массивтің ұзындығы. Төртінші жолда $m$ бүтін сандары бар: $b_{1}, b_{2}, ..., b_{m}$ $(0 <= b_{i} <= 10^9)$ $b$ массивінің элементтері.

Жазу форматы

Бір санды — нәтижеcінде алынған массивтердің максималды ұзындығын шығарыңыз. Егер массивтерді бірдей жасау мүмкін болмаса, $-1$ шығарыңыз.

Мысалдар:

Оқу

5
11 2 3 5 7
4
11 7 3 7

Жауап

3

Оқу

2
1 2
1
100

Жауап

-1

Оқу

3
1 2 3
3
1 2 3

Жауап

3

( Batyr Sardarbekov )

Комментарий/решение

кодты корсету/жасыру

#include <bits/stdc++.h>
#define ll long long
#define N 300010
#define pb push_back
#define si size()

using namespace std;

const int inf = 2e9;

ll a[N], b[N];

int main()
{
    int n;
    cin >> n;
    ll s1 = 0, s2 = 0;
    for(int i = 0; i < n; i++)
    {
    	cin >> a[i];
    	s1 += a[i];
	}
	int m;
	cin >> m;
	for(int i = 0; i < m; i++)
	{
		cin >> b[i];
		s2 += b[i];
	}
	if(s1 != s2)
	{
		cout << -1;
		return 0;
	}
	vector<ll> t1;
	vector<ll> t2;
	t1.pb(a[0]);
	t2.pb(b[0]);
	int pos1 = 1, pos2 = 1;
	while(pos1 < n && pos2 < m)
	{
		ll l1 = t1[t1.si - 1], l2 = t2[t2.si - 1];
		if(l1 == l2)
		{
			t1.pb(a[pos1]);
			t2.pb(b[pos2]);
			pos1++;
			pos2++;
			continue;
		}
		if(l1 > l2)
		{
			t2[t2.si - 1] += b[pos2];
			pos2++;
		}
		else
		{
			t1[t1.si - 1] += a[pos1];
			pos1++;
		}
	}
	cout << t1.size();
}

#include <bits/stdc++.h>

#define yes cout << "Yes\n"

#define no cout << "No\n"

#define Zhussip ios_base::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr)

#define all(a) (a).begin(),(a).end()

typedef long long ll;

#define int long long

const int maxn = 4e5 + 2008;

const long long inf = 1e18 + 2008;

const int mod = 1e9 + 7;

using namespace std;

int a[maxn], b[maxn], pref[maxn], prefb[maxn], n, m;

int rec(int v, int vb) {

int left = vb + 1;

if (vb >= m || v >= n) return 0;

for (int l = v + 1; l <= n; l++) {

while (prefb[left] - prefb[vb] < pref[l] - pref[v] && left < m) {

left++;

}

if (pref[l] - pref[v] == prefb[left] - prefb[vb]) {

return rec(l, left) + 1;

}

}

return 0;

}

void keepcoding() {

cin >> n;

for (int i = 1; i <= n; i++) {

cin >> a[i];

pref[i] = pref[i - 1] + a[i];

}

cin >> m;

for (int i = 1; i <= m; i++) {

cin >> b[i];

prefb[i] = prefb[i - 1] + b[i];

}

if (prefb[m] != pref[n]) {

cout << -1;

return;

}

int ans = rec(0, 0);

cout << ans;

}

signed main() {

Zhussip;

srand(time(0));

int _ = 1;

while (_ > 0) {

keepcoding();

_--;

}

return 0;

}

кодты корсету/жасыру

#include <bits/stdc++.h>

#define yes cout << "Yes\n"
#define no cout << "No\n"

#define Zhussip ios_base::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr)

#define all(a) (a).begin(),(a).end()

typedef long long ll;

#define int long long

const int maxn = 4e5 + 2008;
const long long inf = 1e18 + 2008;
const int mod = 1e9 + 7;

using namespace std;

int a[maxn], b[maxn], pref[maxn], prefb[maxn], n, m;

int rec(int v, int vb) {
	int left = vb + 1;
	if (vb >= m || v >= n) return 0;
	for (int l = v + 1; l <= n; l++) {
		while (prefb[left] - prefb[vb] < pref[l] - pref[v] && left < m) {
			left++;
		}
		if (pref[l] - pref[v] == prefb[left] - prefb[vb]) {
			return rec(l, left) + 1;
		}
	}
	return 0;
}

void keepcoding() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i];
		prefb[i] = prefb[i - 1] + b[i];
	}
	if (prefb[m] != pref[n]) {
		cout << -1;
		return;
	}
	int ans = rec(0, 0);
	cout << ans;
}

signed main() {
	Zhussip;
	srand(time(0));
	int _ = 1;
	while (_ > 0) {
		keepcoding();
		_--;
	}
	return 0;
}