CSES - HIIT Open 2018 - Results
 Task: Find a Word Sender: Tefyn virallinen maajoukkue Submission time: 2018-05-26 15:12:05 +0300 Language: C++ Status: READY Result: WRONG ANSWER
Test results
testverdicttime
#1ACCEPTED0.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.01 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.02 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11ACCEPTED0.01 sdetails
#120.01 sdetails
#130.01 sdetails
#140.01 sdetails
#150.01 sdetails
#160.01 sdetails

### Code

```#include <bits/stdc++.h>

using namespace std;
int n;
string s[33];
int64_t r[33][33];
string pp[33][33];
int np[33][33];
string hae(string lol, int64_t k, int64_t a, int64_t b, int i, int j){
//cout << lol+s[i][j] << " " << k << " " << a << " " << b << " " << i << " " << j << " " << np[i][j] << " " <<pp[i][j] << endl;
if(k < a || k >= b){
// cout << "re1" << endl;
return "";
}
if(i == n-1 && j == n-1){
if(k >= a && k < b)
return lol+s[i][j];
return "";
}

if(i < n-1 && j < n-1){
if(s[i+1][j] < s[i][j+1]){
int down = r[i+1][j];
string re = hae(lol+s[i][j], k, a, a+down, i+1, j);
if(re.length() == 0){
re = hae(lol+s[i][j], k, a+down, b, i, j+1);
}
return re;
}
else if(s[i+1][j] > s[i][j+1]){
int ri = r[i][j+1];
string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
if(re.length() == 0){
re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
}
return re;
}
else {
int ri = r[i][j+1];
int down = r[i+1][j];
if(np[i][j] == 1){
string re3 = hae(lol+s[i][j], k, a, a+down, i+1, j);
if(re3.length() == 0){
re3 = hae(lol+s[i][j], k, a+down, b, i, j+1);
}
return re3;
}
else {
string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
if(re.length() == 0){
re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
}
return re;
}
}
}
else if(i < n-1){
return hae(lol+s[i][j], k, a, b, i+1, j);
}
else if(j < n-1){
return hae(lol+s[i][j], k, a, b, i, j+1);
}
return "";
}

int main(){
int k;
cin >> n >> k;
for(int i = 0; i < n; ++i)
cin >> s[i];
r[n-1][n-1] = 1;
pp[n-1][n-1] = s[n-1][n-1];
for(int i = n-1; i >= 0; --i){
for(int j = n-1; j >= 0; --j){
string c1 = "0";
c1[0] = 'Z'+1;
string c2 = "0";
c2[0] = 'Z'+1;
if(i < n-1){
r[i][j] += r[i+1][j];
c1 = s[i][j]+pp[i+1][j];
}
if(j< n-1){
r[i][j] += r[i][j+1];
c2 = s[i][j]+pp[i][j+1];
}
if(i < n-1 || j < n-1){
if(c1 < c2){
np[i][j] = 1;
pp[i][j] = c1;
}
else{
pp[i][j] = c2;
}
}
//cout << i << " " << j << " " << pp[i][j] << endl;
}
}
cout << hae("", k-1, 0, r[0][0], 0, 0) << endl;
return 0;
}```

### Test details

#### Test 1

Verdict: ACCEPTED

input
4 1
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

#### Test 2

Verdict: ACCEPTED

input
4 2
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

#### Test 3

Verdict: ACCEPTED

input
4 10
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

#### Test 4

Verdict: ACCEPTED

input
4 19
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

#### Test 5

Verdict: ACCEPTED

input
4 20
AAAA
AAAA
AAAA
AAAA

correct output
AAAAAAA

user output
AAAAAAA

#### Test 6

Verdict: ACCEPTED

input
4 1
QNJP
EVJU
XHZF
RXCV

correct output
QEVHXCV

user output
QEVHXCV

#### Test 7

Verdict: ACCEPTED

input
4 2
QNJP
EVJU
XHZF
RXCV

correct output
QEVHZCV

user output
QEVHZCV

#### Test 8

Verdict: ACCEPTED

input
4 10
QNJP
EVJU
XHZF
RXCV

correct output
QEXRXCV

user output
QEXRXCV

#### Test 9

Verdict: ACCEPTED

input
4 19
QNJP
EVJU
XHZF
RXCV

correct output
QNVJZCV

user output
QNVJZCV

#### Test 10

Verdict: ACCEPTED

input
4 20
QNJP
EVJU
XHZF
RXCV

correct output
QNVJZFV

user output
QNVJZFV

#### Test 11

Verdict: ACCEPTED

input
30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

#### Test 12

Verdict:

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
...

#### Test 13

Verdict:

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
...

#### Test 14

Verdict:

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

user output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...

#### Test 15

Verdict:

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
...

#### Test 16

Verdict:

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
...