OJ – 第3页 – 柳婼の blog

1024. Palindromic Number (25)-PAT甲级真题（大整数相加）

A number that will be the same when it is written forwards or backwards is known as a Palindromic Number. For example, 1234321 is a palindromic number. All single digit numbers are palindromic numbers.

Non-palindromic numbers can be paired with palindromic ones via a series of operations. First, the non-palindromic number is reversed and the result is added to the original number. If the result is not a palindromic number, this is repeated until it gives a palindromic number. For example, if we start from 67, we can obtain a palindromic number in 2 steps: 67 + 76 = 143, and 143 + 341 = 484.

Given any positive integer N, you are supposed to find its paired palindromic number and the number of steps taken to find it.

Input Specification:

Each input file contains one test case. Each case consists of two positive numbers N and K, where N (<= 10^10) is the initial numer and K (<= 100) is the maximum number of steps. The numbers are separated by a space.

Output Specification:

For each test case, output two numbers, one in each line. The first number is the paired palindromic number of N, and the second number is the number of steps taken to find the palindromic number. If the palindromic number is not found after K steps, just output the number obtained at the Kth step and K instead.

Sample Input 1:
67 3
Sample Output 1:
484
2
Sample Input 2:
69 3
Sample Output 2:
1353
3
题目大意：给定一个数字，和允许翻转后相加的次数cnt，求要多少次才能变成一个回文数字，输出那个回文数字和翻转相加了多少次，如果本身就是回文数字就输出0次，如果超过给定的次数cnt了，就输出那个不是回文的结果，并且输出给定的次数cnt
分析：1、会超出long int类型（会有两个点溢出错误），所以用字符串存储，大整数相加
2、可以通过对字符串翻转后比较来判断是否为回文串

#include <iostream>
#include <algorithm>
using namespace std;
string s;
void add(string t) {
    int len = s.length(), carry = 0;
    for(int i = 0; i < len; i++) {
        s[i] = s[i] + t[i] + carry - '0';
        carry = 0;
        if(s[i] > '9') {
            s[i] = s[i] - 10;
            carry = 1;
        }
    }
    if(carry) s += '1';
    reverse(s.begin(), s.end());
}
int main() {
    int cnt, i;
    cin >> s >> cnt;
    for(i = 0; i <= cnt; i++) {
        string t = s;
        reverse(t.begin(), t.end());
        if(s == t || i == cnt) break;
        add(t);
    }
    cout << s << endl << i;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

string s;

void add(string t) {

int len = s.length(), carry = 0;

for(int i = 0; i < len; i++) {

s[i] = s[i] + t[i] + carry - '0';

carry = 0;

if(s[i] > '9') {

s[i] = s[i] - 10;

carry = 1;

}

if(carry) s += '1';

reverse(s.begin(), s.end());

}

int main() {

int cnt, i;

cin >> s >> cnt;

for(i = 0; i <= cnt; i++) {

string t = s;

reverse(t.begin(), t.end());

if(s == t || i == cnt) break;

add(t);

}

cout << s << endl << i;

return 0;

}

L3-001. 凑零钱-PAT团体程序设计天梯赛GPLT（01背包，动态规划）

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式：

输入第一行给出两个正整数：N（<=104）是硬币的总个数，M（<=102）是韩梅梅要付的款额。第二行给出N枚硬币的正整数面值。数字间以空格分隔。

输出格式：

在一行中输出硬币的面值 V1 <= V2 <= … <= Vk，满足条件 V1 + V2 + … + Vk = M。数字间以1个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出“No Solution”。

注：我们说序列{A[1], A[2], …}比{B[1], B[2], …}“小”，是指存在 k >= 1 使得 A[i]=B[i] 对所有 i < k 成立，并且 A[k] < B[k]。

输入样例1：
8 9
5 9 8 7 2 3 4 1
输出样例1：
1 3 5
输入样例2：
4 8
7 2 4 3
输出样例2：
No Solution

分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010];
int w[10010];
bool choice[10010][10010];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010];

int w[10010];

bool choice[10010][10010];

int cmp1(int a, int b){return a > b;}

int main() {

int n, m;

scanf("%d%d", &n, &m);

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

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

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

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

for(int i = 0; i < arr.size(); i++) {

if(i != 0) printf(" ");

printf("%d", arr[i]);

}

return 0;

}

1068. Find More Coins (30)-PAT甲级真题（01背包）

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.

Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].

Sample Input 1:
8 9
5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8
7 2 4 3
Sample Output 2:
No Solution
题目大意：用n个硬币买价值为m的东西，输出使用方案，使得正好几个硬币加起来价值为m。从小到大排列，输出最小的那个排列方案
分析：01背包问题，因为要输出从小到大的排列，可以先把硬币面额从大到小排列，然后用bool类型的choice[i][j]数组dp[i][j]是否选取，如果选取了就令choice为true；然后进行01背包问题求解，如果最后求解的结果不是恰好等于所需要的价值的，就输出No Soultion，否则从choice[i][j]判断选取的情况，i从n到1表示从后往前看第i个物品的选取情况，j从m到0表示从容量m到0是否选取(j = j – w[i])，把选取情况压入arr数组中，最后输出arr数组

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int dp[10010], w[10010];
bool choice[10010][110];
int cmp1(int a, int b){return a > b;}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        scanf("%d", &w[i]);
    sort(w + 1, w + n + 1, cmp1);
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= w[i]; j--) {
            if(dp[j] <= dp[j-w[i]] + w[i]) {
                choice[i][j] = true;
                dp[j] = dp[j-w[i]] + w[i];
            }
        }
    }
    if(dp[m] != m) printf("No Solution");
    else {
        vector<int> arr;
        int v = m, index = n;
        while(v > 0) {
            if(choice[index][v] == true) {
                arr.push_back(w[index]);
                v -= w[index];
            }
            index--;
        }
        for(int i = 0; i < arr.size(); i++) {
            if(i != 0) printf(" ");
            printf("%d", arr[i]);
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int dp[10010], w[10010];

bool choice[10010][110];

int cmp1(int a, int b){return a > b;}

int main() {

int n, m;

scanf("%d%d", &n, &m);

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

scanf("%d", &w[i]);

sort(w + 1, w + n + 1, cmp1);

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

for(int j = m; j >= w[i]; j--) {

if(dp[j] <= dp[j-w[i]] + w[i]) {

choice[i][j] = true;

dp[j] = dp[j-w[i]] + w[i];

}

if(dp[m] != m) printf("No Solution");

else {

vector<int> arr;

int v = m, index = n;

while(v > 0) {

if(choice[index][v] == true) {

arr.push_back(w[index]);

v -= w[index];

}

index--;

}

for(int i = 0; i < arr.size(); i++) {

if(i != 0) printf(" ");

printf("%d", arr[i]);

}

return 0;

}

L3-008. 喊山-PAT团体程序设计天梯赛GPLT（广度优先搜索）

喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。
一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：

输入第一行给出3个正整数n、m和k，其中n（<=10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（<=10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：

依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：
7 5 4
1 2
2 3
3 1
4 5
5 6
1 4 5 7
输出样例：
2
6
4
0

分析：用二维数组，结点push_back的方式存储，因为每次都从1遍历到n会超时，而只要遍历到v[top].size()就不会超时。
用广度优先搜索，level记录当前结点的层数，level为自己的上一层结点的level+1，遇到更大层数的时候就令ans又为最大值，让ans取当层的最小值（在不等于被搜索结点本身的时候）。book记录当前结点有没有被访问过，如果没有被访问过就压入队列中，因为可能重复然后导致无限循环，无法输出～

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> v(10010);
int book[10010];
int main() {
    int n, m, k, a, b;
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        v[b].push_back(a);
    }
    for(int i = 0; i < k; i++) {
        scanf("%d", &a);
        queue<int> q;
        fill(book, book + 10010, 0);
        q.push(a);
        int level[10010];
        int ans = 10010, maxlevel = 0;
        book[a] = 1;
        while(!q.empty()) {
            int top = q.front();
            q.pop();
            if(level[top] > maxlevel) {
                maxlevel = level[top];
                ans = 10010;
            }
            if(top != a)
                ans = min(ans, top);
            for(int j = 0; j < v[top].size(); j++) {
                if(book[v[top][j]] == 0) {
                    q.push(v[top][j]);
                    book[v[top][j]] = 1;
                    level[v[top][j]] = level[top] + 1;
                }
            }
        }
        if(ans != 10010) printf("%d\n", ans);
        else printf("0\n");
    }
    return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

vector<vector<int>> v(10010);

int book[10010];

int main() {

int n, m, k, a, b;

scanf("%d%d%d", &n, &m, &k);

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

scanf("%d%d", &a, &b);

v[a].push_back(b);

v[b].push_back(a);

}

for(int i = 0; i < k; i++) {

scanf("%d", &a);

queue<int> q;

fill(book, book + 10010, 0);

q.push(a);

int level[10010];

int ans = 10010, maxlevel = 0;

book[a] = 1;

while(!q.empty()) {

int top = q.front();

q.pop();

if(level[top] > maxlevel) {

maxlevel = level[top];

ans = 10010;

}

if(top != a)

ans = min(ans, top);

for(int j = 0; j < v[top].size(); j++) {

if(book[v[top][j]] == 0) {

q.push(v[top][j]);

book[v[top][j]] = 1;

level[v[top][j]] = level[top] + 1;

}

if(ans != 10010) printf("%d\n", ans);

else printf("0\n");

}

return 0;

}

L2-016. 愿天下有情人都是失散多年的兄妹-PAT团体程序设计天梯赛GPLT（广度优先bfs）

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

输入格式：

输入第一行给出一个正整数N（2 <= N <= 104），随后N行，每行按以下格式给出一个人的信息：

本人ID 性别父亲ID 母亲ID

其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。

接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。

注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式：

对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出“Never Mind”；如果是异性并且关系出了五服，输出“Yes”；如果异性关系未出五服，输出“No”。

输入样例：
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011
输出样例：
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

分析：我用的方法是广度优先，然后把每个人和他们的祖先们压入一个set里面，判断set前后有没有大小改变，如果没改变说明重复了，所以有相同祖先，所以就输出No，用level数组标记他们当前的层数在push一层的时候令他们的层数为上一层+1，一直到五层判断结束。如果结束了还没有输出过No，那么就输出yes。（其实后来想到可以用数组标记的方法，不用集合来这么复杂的。。）
有三个注意点：1.一开始有三个测试点不过，然后。。发现。。每次在输入的时候把它们父母的性别也要标记一下，因为！测试数据里面可能会判断某个人的父亲（但是不在给出的本人id的列表中），或者母亲和某个人是否能结婚。。。。也就是说测试数据里面如果出现了09999，它是某个人的父母，那么也可能会被判断。。所以。。所以。。要在输入的时候加上父母的性别的标记。。。PAT教我做人。。
【有可爱的小伙伴和我说不太明白第一个注意点的意思，我的意思是，测试用例里面，除了测试样例那样常规的9种询问的是否可以通婚的用例，还有可能会问02222和03333是否可以通婚，02222和04444是否可以通婚。但是我们不知道02222和03333和04444的父母是谁，所以就默认他们之间是没有血缘关系的，接下来考虑的就是他们的性别问题了，因为02222是男的（因为他是父亲嘛）而03333是女的，那就要输出可以通婚；同理，04444是男的，就要输出never mind~】
2.因为我开的是全局数组，用全局数组的时候就千万要记得，用完之后记得把它。。置回0啊啊啊。。。因为下一组测试数据用这个数组的时候可能会不小心用到了上一组测试数据保存的结果。。。就会出错了。。
3.用exist数组标记是否存在这个结点，否则避免不小心把0压入。。。到队列里面（就是求对于一个父母，他们可能不存在在本人id里面，那么把他们的孩子结点放入queue里面就会出现0.。不断标记0的话把0当他们的共同祖先可能会误输出No）

#include <cstdio>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct node {
    int f, m, sex;
};
node v[100010];
int level[100010];
bool exist[100010];
int main() {
    int n, m, id, father, mother, a, b;
    scanf("%d", &n);
    char c;
    for(int i = 0; i < n; i++) {
        scanf("%d %c %d %d", &id, &c, &father, &mother);
        v[id].f = father, v[id].m = mother;
        if(c == 'M') v[id].sex = 0;
        else v[id].sex = 1;
        exist[id] = true;
        v[father].sex = 0;
        v[mother].sex = 1;
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        fill(level, level + 100010, 0);
        scanf("%d%d", &a, &b);
        if(v[a].sex == v[b].sex) {
            printf("Never Mind\n");
            continue;
        }
        queue<int> q;
        q.push(a);
        q.push(b);
        level[a] = 1;
        level[b] = 1;
        set<int> s;
        int flag = 0;
        while(!q.empty()) {
            int top = q.front();
            q.pop();
            int size = s.size();
            s.insert(top);
            if(size == s.size()) {
                printf("No\n");
                flag = 1;
                break;
            }
            if(exist[top] == false) continue;
            if(level[top] <= 4) {
                int fa = v[top].f;
                int mo = v[top].m;
                if(fa != -1) {
                    q.push(fa);
                    level[fa] = level[top] + 1;
                }
                if(mo != -1) {
                    q.push(mo);
                    level[mo] = level[top] + 1;
                }
            }
        }
        if(flag == 0) printf("Yes\n");
    }
    return 0;
}

#include <cstdio>

#include <set>

#include <queue>

#include <algorithm>

using namespace std;

struct node {

int f, m, sex;

};

node v[100010];

int level[100010];

bool exist[100010];

int main() {

int n, m, id, father, mother, a, b;

scanf("%d", &n);

char c;

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

scanf("%d %c %d %d", &id, &c, &father, &mother);

v[id].f = father, v[id].m = mother;

if(c == 'M') v[id].sex = 0;

else v[id].sex = 1;

exist[id] = true;

v[father].sex = 0;

v[mother].sex = 1;

}

scanf("%d", &m);

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

fill(level, level + 100010, 0);

scanf("%d%d", &a, &b);

if(v[a].sex == v[b].sex) {

printf("Never Mind\n");

continue;

}

queue<int> q;

q.push(a);

q.push(b);

level[a] = 1;

level[b] = 1;

set<int> s;

int flag = 0;

while(!q.empty()) {

int top = q.front();

q.pop();

int size = s.size();

s.insert(top);

if(size == s.size()) {

printf("No\n");

flag = 1;

break;

}

if(exist[top] == false) continue;

if(level[top] <= 4) {

int fa = v[top].f;

int mo = v[top].m;

if(fa != -1) {

q.push(fa);

level[fa] = level[top] + 1;

}

if(mo != -1) {

q.push(mo);

level[mo] = level[top] + 1;

}

if(flag == 0) printf("Yes\n");

}

return 0;

}

L3-004. 肿瘤诊断-PAT团体程序设计天梯赛GPLT（广度优先搜索）

在诊断肿瘤疾病时，计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域，请你计算肿瘤的体积。

输入格式：

输入第一行给出4个正整数：M、N、L、T，其中M和N是每张切片的尺寸（即每张切片是一个M×N的像素矩阵。最大分辨率是1286×128）；L（<=60）是切片的张数；T是一个整数阈值（若疑似肿瘤的连通体体积小于T，则该小块忽略不计）。

最后给出L张切片。每张用一个由0和1组成的M×N的矩阵表示，其中1表示疑似肿瘤的像素，0表示正常像素。由于切片厚度可以认为是一个常数，于是我们只要数连通体中1的个数就可以得到体积了。麻烦的是，可能存在多个肿瘤，这时我们只统计那些体积不小于T的。两个像素被认为是“连通的”，如果它们有一个共同的切面，如下图所示，所有6个红色的像素都与蓝色的像素连通。

输出格式：

在一行中输出肿瘤的总体积。

输入样例：

3 4 5 2
1 1 1 1
1 1 1 1
1 1 1 1
0 0 1 1
0 0 1 1
0 0 1 1
1 0 1 1
0 1 0 0
0 0 0 0
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 1
0 0 0 1
1 0 0 0

输出样例：

分析：三维的广度优先搜索～XYZ三个数组判断方向，对每一个点广度优先累计肿瘤块的大小，如果大于等于t就把结果累加。用visit数组标记当前的点有没有被访问过，被访问过的结点是不会再访问的。。judge判断是否超过了边界，或者是否当前结点为0不是肿瘤～

#include <cstdio>
#include <queue>
using namespace std;
struct node {
    int x, y, z;
};
int m, n, l, t;
int X[6] = {1, 0, 0, -1, 0, 0};
int Y[6] = {0, 1, 0, 0, -1, 0};
int Z[6] = {0, 0, 1, 0, 0, -1};
int arr[1300][130][80];
bool visit[1300][130][80];
bool judge(int x, int y, int z) {
    if(x < 0 || x >= m || y < 0 || y >= n || z < 0 || z >= l) return false;
    if(arr[x][y][z] == 0 || visit[x][y][z] == true) return false;
    return true;
}
int bfs(int x, int y, int z) {
    int cnt = 0;
    node temp;
    temp.x = x, temp.y = y, temp.z = z;
    queue<node> q;
    q.push(temp);
    visit[x][y][z] = true;
    while(!q.empty()) {
        node top = q.front();
        q.pop();
        cnt++;
        for(int i = 0; i < 6; i++) {
            int tx = top.x + X[i];
            int ty = top.y + Y[i];
            int tz = top.z + Z[i];
            if(judge(tx, ty, tz)) {
                visit[tx][ty][tz] = true;
                temp.x = tx, temp.y = ty, temp.z = tz;
                q.push(temp);
            }
        }
    }
    if(cnt >= t)
        return cnt;
    else
        return 0;
    
}
int main() {
    scanf("%d %d %d %d", &m, &n, &l, &t);
    for(int i = 0; i < l; i++)
        for(int j = 0; j < m; j++)
            for(int k = 0; k < n; k++)
                scanf("%d", &arr[j][k][i]);
    int ans = 0;
    for(int i = 0; i < l; i++) {
        for(int j = 0; j < m; j++) {
            for(int k = 0; k < n; k++) {
                if(arr[j][k][i] == 1 && visit[j][k][i] == false)
                    ans += bfs(j, k, i);
            }
        }
    }
    printf("%d", ans);
    return 0;
}

#include <cstdio>

#include <queue>

using namespace std;

struct node {

int x, y, z;

};

int m, n, l, t;

int X[6] = {1, 0, 0, -1, 0, 0};

int Y[6] = {0, 1, 0, 0, -1, 0};

int Z[6] = {0, 0, 1, 0, 0, -1};

int arr[1300][130][80];

bool visit[1300][130][80];

bool judge(int x, int y, int z) {

if(x < 0 || x >= m || y < 0 || y >= n || z < 0 || z >= l) return false;

if(arr[x][y][z] == 0 || visit[x][y][z] == true) return false;

return true;

}

int bfs(int x, int y, int z) {

int cnt = 0;

node temp;

temp.x = x, temp.y = y, temp.z = z;

queue<node> q;

q.push(temp);

visit[x][y][z] = true;

while(!q.empty()) {

node top = q.front();

q.pop();

cnt++;

for(int i = 0; i < 6; i++) {

int tx = top.x + X[i];

int ty = top.y + Y[i];

int tz = top.z + Z[i];

if(judge(tx, ty, tz)) {

visit[tx][ty][tz] = true;

temp.x = tx, temp.y = ty, temp.z = tz;

q.push(temp);

}

if(cnt >= t)

return cnt;

else

return 0;

}

int main() {

scanf("%d %d %d %d", &m, &n, &l, &t);

for(int i = 0; i < l; i++)

for(int j = 0; j < m; j++)

for(int k = 0; k < n; k++)

scanf("%d", &arr[j][k][i]);

int ans = 0;

for(int i = 0; i < l; i++) {

for(int j = 0; j < m; j++) {

for(int k = 0; k < n; k++) {

if(arr[j][k][i] == 1 && visit[j][k][i] == false)

ans += bfs(j, k, i);

}

printf("%d", ans);

return 0;

}