Областная олимпиада по информатике, 2008 год, 9-10-11 классы

(Ойын)

Ограничение по времени:

2 секунд

Ограничение по памяти:

256 мегабайт

Жуырда Амир жаңа ойынды ойлап тапты. Ол $N \times M$ қара және ақ түсті тор көздерден тұратын тақта. Тор көзге басқанда, оған көршілес тор көздер қарама қарсы түске өзгереді. Ойын мақсаты: тақтадағы бастапқы бояудан берілген түпкі бояуды алу. Сіздің міндетіңіз — жеңу, яғни қай тор көздерді және қанша рет басу керек екенін анықтау.

Формат входного файла

Енгізу файлдың бірінші жолында екі бүтін сан берілген $N$ және $M$ берілген ($1 \le N, M \le 10$). Ыңғайлы болу үшін түстер келесі сандармен белгіленген: $1$ — қара, $2$ — ақ. Келесі $N$ жолдың әрқайсысы $1$-ден $2$-ге дейінгі $M$ бүтін саннан сәйкес бастапқы тақтадағы тор көздің түсі берілген. Келесі $N$ жолдың әрқайсысы $1$-ден $2$-ге дейінгі $M$ бүтін саннан сәйкес түпкі тақтадағы тор көздің түсі берілген. Жолдағы сандар бос орынмен бөлінген.

Формат выходного файла

Егер ойынды жеңуге болса, онда әрқайсысы $0$-ден $1$-ге дейінгі $M$ саннан — сәйкес тор көзді қанша рет басу керек, түратын $N$ жолды шығарыңыз. Егер ойынды жеңуге болмаса, онда $No solution$-ді шығарыңыз.

Пример:

Вход

2 2
2 1
1 2
1 1
1 1

Ответ

0 1
0 0

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

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

 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <cmath>
 #include <string>
 #include <set>
 #include <map>
 #include <unordered_map>
 #include <iomanip>
 #include <stack>
 #include <queue>
 #include <deque>
using namespace std;
struct node{
    node *next[26];
    long long strings;
    node(){
        for(long long i=0;i<26;i++){
            next[i]=nullptr;
        }
        strings=0;
    }
};
node *root=new node();
void add(const string& s){
    node *cur_v=root;
    for(long long i = 0;i < s.size();i++){
        char c = s[i];
        if(cur_v->next[c-'a'] == nullptr){
            cur_v->next[c-'a'] = new node();
        }
        cur_v = cur_v->next[c-'a'];
    }
    cur_v->strings++;
}
long long ans;
void calc(long long prev, node *v = root){
    if(v->strings>0){
        ans+=(v->strings*prev);
        ans+=(v->strings*(v->strings-1))/2;
    }
    for(long long i = 0;i <26 ;i++){
        if(v->next[i]!=nullptr){
            calc(prev+(v->strings),v->next[i]);
        }
    }
}
int main(){
    long long n;
    cin>>n;
    for(long long i=0;i<n;i++){
        string s;
        cin>>s;
        add(s);
    }
    calc(0);
    cout<<ans;
}

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

 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <cmath>
 #include <string>
 #include <set>
 #include <map>
 #include <unordered_map>
 #include <iomanip>
 #include <stack>
 #include <queue>
 #include <deque>
using namespace std;
struct node{
    node *next[26];
    long long strings;
    node(){
        for(long long i=0;i<26;i++){
            next[i]=nullptr;
        }
        strings=0;
    }
};
node *root=new node();
void add(const string& s){
    node *cur_v=root;
    for(long long i = 0;i < s.size();i++){
        char c = s[i];
        if(cur_v->next[c-'a'] == nullptr){
            cur_v->next[c-'a'] = new node();
        }
        cur_v = cur_v->next[c-'a'];
    }
    cur_v->strings++;
}
long long ans;
void calc(long long prev, node *v = root){
    if(v->strings>0){
        ans+=(v->strings*prev);
        ans+=(v->strings*(v->strings-1))/2;
    }
    for(long long i = 0;i <26 ;i++){
        if(v->next[i]!=nullptr){
            calc(prev+(v->strings),v->next[i]);
        }
    }
}
int main(){
    long long n;
    cin>>n;
    for(long long i=0;i<n;i++){
        string s;
        cin>>s;
        add(s);
    }
    calc(0);
    cout<<ans;
}