Thứ Sáu, 29 tháng 3, 2019

Bài E - Codeforces Round 62 (Div.2)

Bài E:
Đề bài: Chúng ta kí hiệu rằng một mảng b nào đó là tồi tệ nếu nó chứa một mảng con b(l),b(l+1),...,b(r) với độ dài lẻ và lớn hơn 1 (l<r và r-l+1 là số lẻ) thỏa mãn $\forall i\in \left\{0,1,...,r-l\right\} b_{l+i}=b_{r-i}$.
Nếu một mảng không xấu, thì đó mảng tốt.
Bây giờ bạn được cho một mảng a(1),a(2),...,a(n). Một vài phần tử được thay thế bằng -1. Tính số mảng tốt bạn có thể đạt được bằng cách thay mỗi số -1 bằng 1 số nguyên nào đó từ 1 đến k.
Bởi vì câu trả lời có thể rất lớn, in ra nó modulo 998244353
Đầu vào:
+ Dòng đầu tiên chứa hai số nguyên n và k (2<=n,k<=2.10^5) - chiều dài của mảng a và kích thước của "alphabet"
+ Dòng thứ 2 chứa n số nguyên a(1),a(2),...,a(n) (a(i)=-1 hoặc 1<=a(i)<=k)- mảng a.
Đầu ra:
In ra một số nguyên - số mảng tốt bạn có thể đạt được , modulo 998244353.
Ví dụ:
Đầu vào:
2 3
-1 -1
Đầu ra:
9
/**/
Đầu vào:
5 2
1 -1 -1 1 2
Đầu ra:
0
/**/
Đầu vào:
5 3
1 -1 -1 1 2
Đầu ra: 2
/**/
Đầu vào:
4 200000
-1 -1 12345 -1
Đầu ra:
735945883.
Hướng dẫn:
 Đầu tiên, mảng chứa một mảng con đối xứng >=3 tương đương với mảng chứa một mảng con đối xứng có độ dài là 3.
Vì vậy, chúng ta cần tính số mảng mà không đối xứng có độ dài là 3. Điều này tương đương với mảng mà a[i]#a[i+2] với mọi i hợp lý.
Chú ý ràng, i và i+2 có cùng tính chẵn lẽ, vì vậy tất cả vị trí lẻ và vị trí chẵn trong mảng độc lập nhau, và câu trả lời là tích các cách chọn các số ở vị trí lẻ, và số cách chọn các số ở vị trí chẵn.
Về mặt tương đương hình thái điều kiện, a[i]#a[i+1] và chúng ta cần tính tất cả các cách để thay các số -1 bằng một cách nào đó các cặp phần tử liên tiếp là khác nhau.
  Để tính nó, chúng ta hãy nhìn vào chuỗi các số (-1) liên tiếp. Họ sẽ thấy rằng a,-1,-1,...,-1,b với l số (-1), ở đây a và b là các số nguyên dương (trường hợp a ở đây không có thể xét như k.(a,-1,-1,...,b với l-1 số -1)), trường hợp b rỗng được giải theo cách tương tự.
  Cuối cùng chúng ta cần tính số các dãy như vậy. Có hai loại dãy chúng ta cần xét tới đó là a,-1,..,-1,a (đầu và cuối giống nhau) và a,-1,-1,...,-1,b (đầu và cuối khác nhau). Giá trị chính xác của a và b không phải là vấn đề.
  Chúng ta sẽ tìm hai giá trị (đặt tên chúng là cntSame và cntDiff) với l số (-1) liên tiếp với thời gian O(log(l)). Các giá trị cơ sở: cntSame(0)=0,cntDiff(0)=1.
  Chúng ta thử chọn giá trị của -1 nằm ở giữa của dãy : Nếu l mod 2=1, thì chúng ta có thể tách thành hai dãy có độ dài [l/2] và cntSame(l)=cntSame(l/2)^2+(k-1).cntDiff(l/2)^2 và cntDiff(l)=2.cntSame(l/2).cntDiff(l/2)+(k-2).cntDiff(l/2)^2.
Nếu l mod 2= 1thì chỉ cần lặp giá trị cuối cùng -1m thì cntSame(l)=(k-1).cntDiff(l-1) và cntDiff(l)=cntSame(l-1)+(k-2).cntDiff(l-1).
Độ phức tạp cuối cùng là O(n).
Lời giải:
#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef pair<int, int> pt;

const int MOD = 998244353;
int norm(int a) {
    while(a >= MOD) a -= MOD;
    while(a < 0) a += MOD;
    return a;
}
int mul(int a, int b) {
    return int(a * 1ll * b % MOD);
}

int n, k;
vector<int> a;

inline bool read() {
    if(!(cin >> n >> k))
        return false;
    a.resize(n);
    fore(i, 0, n)
        cin >> a[i];
    return true;
}

pair<int, int> calc(int len) {
    if(len == 0) return {0, 1};
    if(len & 1) {
        auto res = calc(len >> 1);
        return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))),
                norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))};
    }
    auto res = calc(len - 1);
    return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))};
}

vector<int> curArray;

int calcSeg(int l, int r) {
    if(r >= sz(curArray)) {
        int len = r - l - 1, cf = 1;
        if(l < 0)
            len--, cf = k;
        if(len == 0) return cf;

        auto res = calc(len - 1);
        return mul(cf, norm(res.x + mul(k - 1, res.y)));
    }
    if(l < 0) {
        if(r - l == 1) return 1;
        auto res = calc(r - l - 2);
        return norm(res.x + mul(k - 1, res.y));
    }
    auto res = calc(r - l - 1);
    return curArray[l] == curArray[r] ? res.x : res.y;
}

inline void solve() {
    int ans = 1;
    fore(k, 0, 2) {
        curArray.clear();
        for(int i = 0; 2 * i + k < n; i++)
            curArray.push_back(a[2 * i + k]);

        int lst = -1;
        fore(i, 0, sz(curArray)){
            if(curArray[i] == -1) continue;
            ans = mul(ans, calcSeg(lst, i));
            lst = i;
        }
        ans = mul(ans, calcSeg(lst, sz(curArray)));
    }
    cout << ans << endl;
}

int main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    int tt = clock();
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);

    if(read()) {
        solve();

#ifdef _DEBUG
        cerr << "TIME = " << clock() - tt << endl;
        tt = clock();
#endif
    }
    return 0;
}


Bài C - Google Bye 2018

Bài C:
Đề bài: Cho n người ngồi theo 1 vòng tròn, được đánh số từ 1 đến n. Có nghĩa là, với mọi i chạy từ 1 đến n-1, thì người có chỉ số i và i+1 ngồi kề nhau. Người thứ n và người thứ 1 cũng ngồi kề nhau.
Người với chỉ số là 1 ban đầu có 1 trái bóng. Anh ta lấy một số nguyên k (k<=n), và chuyền trái banh này đến người hàng xóm thứ k của anh ta theo chiều tăng dần của các chỉ số, người đó chuyền bóng cho người hàng xóm thứ k của mình theo cùng hướng, và cứ thế cho đến khi người với chỉ số 1 nhận được bóng. Khi anh ta nhận được bóng, mọi người sẽ không chuyền bóng nữa.
Ví dụ, nếu n=6 và k=4, thì quả bóng sẽ được chuyển theo thứ tự [1,5,3,1].
 Xét tập tất cả các người mà chạm vào quả bóng. Độ vui của game là tổng các chỉ số của người mà chạm vào quả bóng. Ở trường hợp trên, độ vui của game là 1+5+3=9.
Tìm và báo cáo tập các giá trị vui có thể cho tất cả các lựa chọn số nguyên dương k. Có thể chỉ ra ràng buộc của vấn đề quả bóng cuối cùng luôn ở trong tạy người thứ 1 sau nhiều bước chuyền bóng chính xác và không có quá 105 giá trị vui có thể của n.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n (2<=n<=10^9) - số lượng người chơi bóng.
Đầu ra:
+ Giả sử ta có một tập các giá trị vui là f(1),f(2),....,f(m)
+ In ra một 1 dòng duy nhất chứa m số từ f(1) đến f(m) theo thứ tự tăng dần.
Ví dụ:
Đầu vào:
6
Đầu ra:
1 5 9 21
Đầu vào:
16
Đầu ra:
1 10 28 64 136
Chú thích:
Ở ví dụ đầu tiên, chúng ta đã có sẵn với k=4, chúng ta được giá trị vui vẻ là 9, cũng như với k=2. Với k=6, ta được giá trị vui vẻ là 1. Ứng với k=3, ta được giá trị vui vẻ là 5, và ứng với k=1 hoặc 5, giá trị vui vẻ là 21.

Ở ví dụ 2, các giá trị 1,10,28,64 và 136 đạt được là với k=16,8,4,10 và 11 lần lượt.
Hướng dẫn:
 Trừ 1 từ tất cả các giá trị cho tiện. Điều chỉnh giá trị k. Chúng ta được các giá trị a.k mod n với a từ 0 cho đến đạt 0 lại. Giá trị này có thể được viết a.k-b.n. Theo định lý Bezout, phương trình a.k-b.n=c có nghiệm cho a và b khi và chỉ khi c chia hết cho gcd(k,n).
Hơn thế nữa, tất cả các giá trị của c sẽ được duyệt qua trước khi nó quay về 0. Ở đây, bởi vì phần từ k/gcd(k,n) sinh ra nhóm $\mathbb{Z}_{n/gcd(k,n)}$.
Chúng ta có thể xét các giá trị k là ước của n. Chúng ta có thể tìm tất cả chúng bằng độ phức tạp $O(\sqrt{n})$. Với mỗi trong số chúng, chúng ta có thể tìm một giải pháp dạng đóng bằng cách tổng hợp chuỗi số học.
Lời giải:
#include <bits/stdc++.h>
using namespace std;

int main()
{
 long long n,i,x;
 cin>>n;
 set<long long> a;
 for(i=1;i*i<=n;i++){
  if(n%i) continue;
  x=n/i;
  a.insert((1+n-i+1)*x/2);
  a.insert((1+n-x+1)*i/2);
 }
 for(auto it:a) printf("%lld\n",it);
 return 0;
}


Bài C - Codeforces Beta Round #10

Bài C:
Đề bài: Cách đây không lâu, Billy bắt gặp một vấn đề, đó là: cho ba số tự nhiên A,B và C thuộc dãy [1..N], và chúng ta phải kiểm tra liệu rằng phương trình AB=C có đúng hay không?. Gần đây, Billy đã học về khái niệm digital root của 1 số. Chúng tôi nên nhắc lại rằng digital root d(x) của một số x là tổng s(x) của tất cả các chữ số, nếu s(x)<=9, ngược lại nó là d(s(x)). Ví một, digital root của số 6543 được tính như sau: d(6543)=d(6+5+4+3)=d(18)=d(9). Billy phải điểm rằng digital root của một tích các số có bằng digital root của tích các digital root các số, nghĩa là d(xy)=d(d(x).d(y)). Và lời giải dưới đây có ảnh hưởng đến tâm trí của anh ấy: để tính digital root và kiểm tra rằng điều kiện này đã đáp ứng chưa. Tuy nhiên, Billy nghi ngờ rằng điều kiện này đã đủ chưa. Và đó là lý do anh ta hỏi bạn để tìm ra nhiều ví dụ cho vấn đề được cho này thỏa mãn thuật toán được đề nghị bởi Billy có lỗi.
Đầu vào:
+ Dòng đầu tiên chứa 1 số duy nhất N (1<=N<=10^6).
Đầu ra:
+ In ra 1 số - số lượng các số A,B và C được yêu cầu từ dãy [1..N]
Ví dụ:
Đầu vào:
4
Đầu ra:
2
/**/
Đầu vào:
5
Đầu ra:
6
Chú thích
Ở ví dụ đầu tiên ta có bộ ba (3,4,3) và (4,3,3)
Lời giải:
#include<iostream>
int n,i,j;
__int64 t,a[9];
int main()
{
 std::cin>>n;
 for(i=1;i<=n;i++)a[i%9]++,t-=n/i;
 for(i=0;i<9;i++)for(j=0;j<9;j++)t+=a[i]*a[j]*a[i*j%9];
 std::cout<<t;
}

Bài C - Codeforces Beta Round Round #7

Bài C:
Đề bài: Một đường thẳng trên mặt phẳng được mô tả bằng phương trình $Ax+By+C=0$. Bạn phải tìm bất kỳ điểm nào trên đường thẳng này, thỏa mãn tọa độ của những điểm này nguyên từ -5.10^(18) đến 5.10^(18), hoặc chỉ ra rằng không có điểm nào như vậy thỏa mãn.
Đầu vào:
+ Dòng đầu tiên chứa 3 số nguyên A,B và C (-2.10^(9)<=A,B,C<=2.10^(9))- tương ứng với hệ số của phương trình đường thẳng trên. Nó được đảm bào rằng $A^2+B^2>0$.
Đầu ra:
+ Nếu có điểm tồn tại, in ra tọa độ của điểm đó, ngược lại in ra -1.
Ví dụ:
Đầu vào:
2 5 3
Đầu ra:
6 -3
Hướng dẫn:
Lời giải:
#include<cstdio>
typedef long long ll;
ll a,b,c,d,x,y;
void exgcd(ll a,ll b,ll& x,ll& y)
{
    if(!b){d=a,x=1,y=0;}else{exgcd(b,a%b,y,x);y-=x*(a/b);}
}
int main()
{
    scanf("%I64d%I64d%I64d",&a,&b,&c);c=-c;
    exgcd(a,b,x,y);
    if(c%d!=0)return puts("-1"),0;else printf("%I64d %I64d\n",x*c/d,y*c/d);
}

Thứ Năm, 28 tháng 3, 2019

Bài A - Codeforces Round #422 (Div.2)

Bài A:
Đề bài:
Đầu vào: Cho hai số nguyên A và B (1<=A,B<=10^9,min(A,B)<=12).
Đầu ra: Ước chung lớn nhất của A! và B!.
Lời giải:
#include<iostream>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    a=a<b?a:b;
    for(b=a;--a;)b*=a;
    cout<<b;
return 0;
}

Bài B - Codeforces Round #545 (Div.2)

Bài B:
Đề bài: Polycarp là người đứng đầu đoàn xiếc. Có n (n chẵn) nghệ sĩ trong đoàn xiếc. Được biết, nghệ sĩ thứ i có thể biểu diễn như một chú hề (nếu có, thì c(i)=1, ngược lại c(i)=0) và liệu họ có thể thực hiện như một acrobat (nếu có, thì a(i)=1, ngược lại a(i)=0).
Chia các nghệ sĩ thành 2 buổi biểu diễn theo cách sau đây:
+ mỗi nghệ sĩ đóng chính xác 1 buổi biểu diễn.
+ số lượng nghệ sĩ ở trong 2 buổi biểu diễn bằng nhau (tức là đều bằng n/2).
+ số lượng nghệ sĩ có thể biểu diễn như 1 chú hề trong buổi biểu diễn thứ nhất bằng với số lượng nghệ sĩ biểu diễn như 1 acrobats ở buổi biểu diễn thứ 2.
Đầu vào:
+ Dòng đầu tiên chứa số nguyên n (2<=n<=5000, n là số chẵn) - là số nghệ sĩ trong đoàn xiếc.
+ Dòng thứ hai chứa n chữ số c(1),c(2),...,c(n) - với c(i)=1 khi người thứ i là chú hề và c(i)=0 trong trường hợp ngược lại.
+ Dòng thứ ba chứa n chữ số a(1),a(2),...,a(n) - với a(i)=1 khi người thứ i là acrobat và a(i)=0 trong trường hợp ngược lại.
Đầu ra:
+ In ra n/2 số nguyên - là chỉ số các nghệ sĩ sẽ đóng kịch ở buổi biểu diễn đầu tiên.
Nếu có nhiều câu trả lời, in ra đáp án bất kỳ.
Nếu không có nghiệm nào, in ra -1.
Ví dụ:
Đầu vào:
0011
0101
Đầu ra:
1 4
/**/
Đầu vào:
6
000000
111111
Đầu ra:
-1
/**/
Đầu vào:
4
0011
1100
Đầu ra:
4 3
/**/
Đầu vào:
8
00100101
01111100
Đầu ra:
1 2 3 6
Chú thích:
 Ở ví dụ đầu tiên, một trong những các chia hợp lý thành 2 buổi biểu diễn như sau: Ở buổi biểu diễn đầu tiên nghệ sĩ 1 và 4 sẽ tham gia. Thì số lượng nghệ sĩ ở buổi biểu đầu tiên, người mà biểu diễn như các chú hề sẽ bằng 1. Và số lượng người biểu diễn ở buổi thứ 2, người mà biểu diễn như 1 acrobat cũng là 1.
Ở ví dụ thứ 2, không có cách nào để chia.
Ở ví dụ thứ 3, một trong những cách chia thỏa mãn: ở buổi biểu diễn thứ nhất nghệ sĩ thứ 3 và thứ 4 sẽ tham gia. Thì khi đó buổi biểu diễn đầu tiên có 2 nghệ sĩ người mà biểu diễn như một chú hề. Và số lượng nghệ sĩ ở buổi biểu diễn thứ 2 người mà biểu diễn như acrobats cũng là 2.
Hướng dẫn:
Chú ý rằng, chỉ có 4 loại nghệ sĩ: <<0;0>>,<<0;1>>,<<1;0>>,<<1;1>>
Vì vậy tất cả vấn đề được mô tả với 4 số nguyên - số họa sĩ của mỗi loại. Chúng ta nói rằngm có n(a) <<0;0>> nghệ sĩ, n(b) <<0;1>> nghệ sĩ, n(c) <<1;0>> nghệ sĩ, n(d) <<1;1>> nghệ sĩ.
Cùng cách đó, việc lựa chọn các nghệ sĩ cho buổi biểu diễn đầu tiên có thể được mô tả với 4 số nguyên 0<=a<=n(a),0<=b<=n(b),0<=c<=n(c),0<=d<=n(d).
Chú ý rằng, có một số hạn chế trên a,b,c,d
Cụ thể, chúng ta cần chọn chính xác một nữa nghệ sĩ: a+b+c+d=n/2;
Chúng ta cũng có một yêu cầu rằng số chú hề ở buổi biểu diễn đầu tiên c+d phải bằng số acrobats ở buổi biểu diễn thứ 2 (n(b)-b+n(d)-d):c+d=n(b)-b+n(d)-d, vì vậy chúng ta có: b+c+2d=n(b)+n(d).
Câu hỏi này là cần thiết và đủ. Vì vậy chúng ta có 4 biến và 2 phương trình. Chúng ta có thể chạy trâu với 2 biến bất kỳ, tính sử dụng 2 biến khác nhau. Và nếu mọi thứ đến tốt đẹp, in ra kết quả.
Độ phức tạp O(n^2).
Lời giải:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100000;
int n;
char s[maxn + 10], t[maxn + 10];
vector<int> a, b, c, d;

int main() {
 scanf("%d", &n);
 scanf("%s%s", s + 1, t + 1);
 for (int i = 1; i <= n; ++i)
  if (s[i] == '0' && t[i] == '0') a.push_back(i);
  else if (s[i] == '1' && t[i] == '0') b.push_back(i);
  else if (s[i] == '0' && t[i] == '1') c.push_back(i);
  else if (s[i] == '1' && t[i] == '1') d.push_back(i);
 for (int i = 0; i <= (int)b.size(); ++i)
  for (int j = 0; j <= (int)d.size(); ++j) {
   int s = (int)c.size() - i - 2 * j + (int)d.size();
   if (s >= 0 && s <= (int)c.size()) {
    int all = i + s + j;
    int k = n / 2 - all;
    if (k >= 0 && k <= (int)a.size()) {
     for (int p = 0; p < k; ++p) printf("%d ", a[p]);
     for (int p = 0; p < i; ++p) printf("%d ", b[p]);
     for (int p = 0; p < s; ++p) printf("%d ", c[p]);
     for (int p = 0; p < j; ++p) printf("%d ", d[p]);
     return 0;
    }
   }
  }
 printf("-1"); 
}

Bài B - Codeforces Round #518 (Div.2)

Bài B:
Đề bài: Ivan có một số b. Anh ấy sắp xếp các số a từ 1 đến 10^(18), với mỗi số a anh ấy viết $\frac{[a,b]}{a}$ lên bảng đen. Ở đây $[a,b]$ là bội chung nhỏ nhất của a và b. Ivan rất lười nhát, đó là lý do tại sao nhiệm vụ lần này làm phiền anh ấy. Nhưng anh ấy thú vị về việc đếm thử có bao nhiêu số khác nhau khi anh ấy viết lên bảng . Hãy giúp anh ấy xác định số lượng các số khác nhau mà anh ấy viết trên bảng.
Đầu vào:
+ Dòng đầu tiên chứa 1 số nguyên b(1<=b<=10^(10)).
Đầu ra:
+ In ra một số nguyên - là câu trả lời của vấn đề.
Ví dụ:
Đầu vào:
1
Đầu ra:
1
/**/
Đầu vào:
2
Đầu ra:
2.
Chú thích:
+ Ở ví dụ đầu tiên [a,1]=a, vì vậy [a,b]/a luôn bằng 1.
+ Ở ví dụ 2 [a,2]=a hoặc 2.a điều này phụ thuộc vào tính chẵn lẻ của a. do đó [a,b]/a bằng 1 hoặc 2.
Lời giải:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define ll long long
//#define ull unsigned long long
#define BUG printf("************\n")
using namespace std;
ll gcd(ll a,ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a,ll b) {
    return a / gcd(a, b) * b;
}
ll pow_mod(ll a, ll b, ll mod) {
    ll ans = 1;
    while (b) {
        if (b & 1)ans = (ans * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return ans % mod;
}
bool is_prime(ll n) {
    if (n == 1 || n == 2)return 1;
    for (int i = 2; i <= sqrt(n); ++i)
        if (n % i == 0)return 0;
    return 1;
}
const ll mod = 1e8 + 7;
const int maxn = 4e5 + 10;
const int maxm = 1e6 + 10;
const double eps = 1e-8;

int p[10001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll b;
    cin>>b;
    ll t=(ll)sqrt(b);
    ll n=b;
    int cnt=0;
    for(ll i=2;i<=t;++i){
        if(n%i==0){
            ++cnt;
            while(n%i==0){
                ++p[cnt];
                n/=i;
            }
        }
    }
    if(n!=1){
        p[++cnt]++;
    }
    ll ans=1;
    for(int i=1;i<=cnt;++i){
        ans*=(p[i]+1);
    }
    cout<<ans<<endl;
    return 0;
}

Bài G - Educatioal Round 62

Đề bài: Bạn được cho 1 đồ thị vô hướng đặc biệt. Nó bao gồm $2n$ đỉnh được đánh số từ 1 đến 2n. Dưới đây là một số đặc tính của đồ thị: + ...