CSES - HIIT Open 2018 - Results
Submission details
Task:Find a Word
Sender:Tefyn virallinen maajoukkue
Submission time:2018-05-26 14:30:32
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.02 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.02 sdetails
#4ACCEPTED0.01 sdetails
#5ACCEPTED0.01 sdetails
#6ACCEPTED0.01 sdetails
#7ACCEPTED0.01 sdetails
#8ACCEPTED0.01 sdetails
#9ACCEPTED0.01 sdetails
#10ACCEPTED0.01 sdetails
#11--details
#12--details
#13--details
#140.01 sdetails
#15--details
#16--details

Code

#include <bits/stdc++.h>

using namespace std;
int n, k;
string s[33];
int64_t r[33][33];

string hae(string lol, int64_t k, int64_t a, int64_t b, int i, int j){
    if(k < a || k >= b)
        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];
            string re = hae(lol+s[i][j], k, a+ri, b, i+1, j);
            string re3 = hae(lol+s[i][j], k, a, a+down, i+1, j);
            if(re.length() == 0){
                re = hae(lol+s[i][j], k, a, a+ri, i, j+1);
            }
            if(re3.length() == 0){
                re3 = hae(lol+s[i][j], k, a+down, b, i, j+1);
            }

            if(re3.length() > re.length())
                re = re3;

            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(){
    cin >> n >> k;
    for(int i = 0; i < n; ++i)
        cin >> s[i];
    r[n-1][n-1] = 1;
    for(int i = n-1; i >= 0; --i){
        for(int j = n-1; j >= 0; --j){
            if(i < n-1)
                r[i][j] += r[i+1][j];
            if(j< n-1)
                r[i][j] += r[i][j+1];
        }
    }
    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:

input
30 1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
(empty)

Test 12

Verdict:

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
(empty)

Test 13

Verdict:

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
(empty)

Test 14

Verdict:

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

user output
QRXZYLYURTAYRYZQUKZCYOPKYKLPQX...

Test 15

Verdict:

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
(empty)

Test 16

Verdict:

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
(empty)