راه‌حل‌های سؤالات مسابقهٔ دستگرمی الگوریتم کدکاپ ۷ در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.
با توجه به اینکه مقدار nای که به برنامه‌ی شما داده می‌شود خیلی بزرگ نیست، میتوان رشته‌ی codecup6codecup6... را تا حداقل ۱۰۰ کاراکتر در رشته‌ای مثل s ذخیره کرده و با دریافت n مقدار s[n] را چاپ کرد.
راه‌حل به زبان سی‌پلاس‌پلاس:
#include <iostream>
using namespace std;
int main()
{
string s = "";
for (int i = 0; i < 13; i++)
s += "codecup6";
int n;
cin >> n;
cout << s[n - 1] << endl;
return 0;
}
راه‌حل به زبان پایتون:
s = "codecup6" * 13
n = int(input())
print(s[n - 1])
مسئله برای هر تست را جدا حل می‌کنیم. مجموع هزینه‌ای که باید همه‌ی افراد بپردازند برابر است با:
پس اگر بخواهیم همه به اندازه‌ی برابر در هزینه‌ها شریک باشند، هرکس باید:
از حسابش کم شود. پس همه (به جز مادرخرج) باید:
\frac{S + (n - 1)a}{n} - a = \frac{S - a}{n}بنابراین در صورتی که S - a بر n بخش‌پذیر و یا مثبت نباشد، باید 1- را چاپ کرده و در غیر این‌صورت \frac{S - a}{n} را چاپ می‌کنیم.
راه‌حل به زبان سی‌پلاس‌پلاس:
#include <iostream>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--)
{
int n, S, a;
cin >> n >> S >> a;
if (S - a <= 0 || (S - a) % n != 0)
cout << "-1\n";
else
cout << (S - a) / n << "\n";
}
return 0;
}
راه‌حل به زبان پایتون:
t = int(input())
for i in range(t):
n, s, a = map(int, input().split())
if s - a <= 0 or (s - a) % n != 0:
print(-1)
else:
print((s - a) // n)
می‌خواهیم رشته‌ی داده‌شده را تغییر دهیم تا به مسیری با طول بهینه برسیم. توجه کنید که ترتیب قرار گرفتن کاراکترها در رشته‌ی داده‌شده، تغییری در پاسخ مسئله ایجاد نمی‌کند. (چرا؟)
پس می‌توانیم یک مسیر را با ۶ عدد صحیح و نامنفی cnt_A، cnt_B، cnt_C، cnt_D، cnt_E و cnt_F نشان دهیم.
میتوان با توجه به جهت بردارها گفت:
- حرکت A و D برعکس یکدیگرند.
- حرکت B و E برعکس یکدیگرند.
- حرکت C و F برعکس یکدیگرند.
پس میتوان فرض کرد که از هرکدام از این ۳ دسته، حداکثر یک حرکت وجود دارد. چون در غیر این صورت از هر دو نوع حرکت یک واحد کم می‌کنیم.
همچنین با توجه به قانون جمع بردارها میتوان گفت:
- دو حرکت A و C معادل یک حرکت B است.
- دو حرکت B و D معادل یک حرکت C است.
- دو حرکت C و E معادل یک حرکت D است.
- دو حرکت D و F معادل یک حرکت E است.
- دو حرکت E و A معادل یک حرکت F است.
- دو حرکت F و B معادل یک حرکت A است.
پس میتوان فرض کرد از ۶ حرکت موجود، حداکثر ۲ نوع حرکت میتوان داشت (چرا؟) و پاسخ مسئله برابر جمع این دو عدد است.
راه‌حل به زبان سی‌پلاس‌پلاس:
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int t;
cin >> t;
while (t--)
{
string s;
cin >> s;
int cnt[6] = {0, 0, 0, 0, 0, 0};
for (int i = 0; i < (int)s.size(); i++)
cnt[s[i] - 'A']++;
for (int i = 0; i < 3; i++)
{
int m = min(cnt[i], cnt[i + 3]);
cnt[i] -= m;
cnt[i + 3] -= m;
}
for (int i = 0; i < 6; i++)
{
int m = min(cnt[i], cnt[(i + 2) % 6]);
cnt[i] -= m;
cnt[(i + 2) % 6] -= m;
cnt[(i + 1) % 6] += m;
int idx = (i + 1) % 6;
m = min(cnt[idx], cnt[(idx + 3) % 6]);
cnt[idx] -= m;
cnt[(idx + 3) % 6] -= m;
}
int ans = 0;
for (int i = 0; i < 6; i++)
ans += cnt[i];
cout << ans << '\n';
}
return 0;
}
راه‌حل به زبان پایتون:
t = int(input())
for r in range(t):
s = input()
cnt = [0, 0, 0, 0, 0, 0]
for c in s:
cnt[ord(c) - ord('A')] += 1
for i in range(3):
m = min(cnt[i], cnt[i + 3])
cnt[i] -= m
cnt[i + 3] -= m
for i in range(6):
m = min(cnt[i], cnt[(i + 2) % 6])
cnt[i] -= m
cnt[(i + 2) % 6] -= m
cnt[(i + 1) % 6] += m
idx = (i + 1) % 6
m = min(cnt[idx], cnt[(idx + 3) % 6])
cnt[idx] -= m
cnt[(idx + 3) % 6] -= m
print(sum(cnt))
میتوان ثابت کرد اگر پاسخی برای مسئله موجود باشد می‌تواند یک پیشوند از دنباله‌ی b باشد. (چرا؟)
حال می‌خواهیم برای هر پیشوند از b بررسی کنیم که آیا می‌تواند یک پاسخ برای مسئله باشد یا نه. برای این کار نیاز داریم بررسی کنیم که آیا دو زیردنباله‌ی به‌هم‌چسبیده از b با هم برابر هستند یا نه. که برای مقایسه‌ی چنین چیزی می‌توانیم از الگوریتم‌های درهم‌سازی یا hashing یا Z-Algorithm استفاده کنیم.
توجه کنید که اگر همه‌ی زیررشته‌ها را بررسی کنیم، مرتبه زمانی از O(m.log(m)) خواهد شد. چون برای مقایسه کردن پیشوند به طول k باید \lceil\frac{m}{k}\rceil زیردنباله‌ی متوالی از b را با هم مقایسه کنیم.
پس اگر فرض کنیم هر مقایسه با استفاده از درهم‌سازی از O(1) انجام می‌شود، مرتبه‌ی زمانی کل راه‌حل برابر است با:
\sum_{k=1}^{m} \lceil\frac{m}{k}\rceil - 1 \leq \sum_{k=1}^{m}\frac{m}{k} = m\sum_{k=1}^{m}\frac{1}{k} = m.H(m) \in O(m.log(m))راه‌حل به زبان سی‌پلاس‌پلاس:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6;
int z[maxn], b[maxn];
void solve()
{
int m;
cin >> m;
for (int i = 0; i < m; i++)
cin >> b[i];
int L = 0, R = 0;
for (int i = 1; i < m; i++)
{
if (i > R)
{
L = R = i;
while (R < m && b[R - L] == b[R])
R++;
z[i] = R - L;
R--;
}
else
{
int k = i - L;
if (z[k] < R - i + 1)
z[i] = z[k];
else
{
L = i;
while (R < m && b[R - L] == b[R])
R++;
z[i] = R - L;
R--;
}
}
}
for (int n = 1; n <= m; n++)
{
bool okay = true;
for (int i = n; i + n <= m; i += n)
if (z[i] < n)
{
okay = false;
break;
}
if (m % n != 0 && z[(m / n) * n] < (m % n))
okay = false;
if (okay)
{
cout << n << '\n';
for (int i = 0; i < n; i++)
cout << b[i] << ' ';
cout << '\n';
return;
}
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int tc;
cin >> tc;
while (tc--)
solve();
return 0;
}
راه‌حل به زبان پایتون:
t = int(input())
for i in range(t):
m = int(input())
a = list(map(int, input().split()))
base = 313
mod = [
int(1e9 + 7),
int(1e9 + 9),
]
h = [
[0] * (m + 1), [0] * (m + 1)
]
p = [
[1] * (m + 1), [1] * (m + 1)
]
for j in range(m):
p[0][j + 1] = (p[0][j] * base) % mod[0]
p[1][j + 1] = (p[1][j] * base) % mod[1]
for j in range(m):
h[0][j + 1] = (h[0][j] * base + a[j]) % mod[0]
h[1][j + 1] = (h[1][j] * base + a[j]) % mod[1]
for j in range(1, m + 1):
if h[0][m - j] == ((h[0][m] - p[0][m-j] * h[0][j]) % mod[0] + mod[0]) % mod[0]:
if h[1][m - j] == ((h[1][m] - p[1][m-j] * h[1][j]) % mod[1] + mod[1]) % mod[1]:
print(j)
for k in range(j):
print(a[k], end=' ')
print()
break
