Task: | Find a Word |

Sender: | Tefyn virallinen maajoukkue |

Submission time: | 2018-05-26 15:17:30 +0300 |

Language: | C++ |

Status: | READY |

Result: | ACCEPTED |

test | verdict | time | |
---|---|---|---|

#1 | ACCEPTED | 0.01 s | details |

#2 | ACCEPTED | 0.02 s | details |

#3 | ACCEPTED | 0.01 s | details |

#4 | ACCEPTED | 0.01 s | details |

#5 | ACCEPTED | 0.01 s | details |

#6 | ACCEPTED | 0.01 s | details |

#7 | ACCEPTED | 0.01 s | details |

#8 | ACCEPTED | 0.01 s | details |

#9 | ACCEPTED | 0.02 s | details |

#10 | ACCEPTED | 0.01 s | details |

#11 | ACCEPTED | 0.01 s | details |

#12 | ACCEPTED | 0.02 s | details |

#13 | ACCEPTED | 0.01 s | details |

#14 | ACCEPTED | 0.01 s | details |

#15 | ACCEPTED | 0.01 s | details |

#16 | ACCEPTED | 0.01 s | details |

### 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]){ int64_t 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]){ int64_t 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 { int64_t ri = r[i][j+1]; int64_t 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(){ int64_t 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 1AAAA AAAA AAAA AAAA |

correct output |
---|

AAAAAAA |

user output |
---|

AAAAAAA |

#### Test 2

Verdict: ACCEPTED

input |
---|

4 2AAAA AAAA AAAA AAAA |

correct output |
---|

AAAAAAA |

user output |
---|

AAAAAAA |

#### Test 3

Verdict: ACCEPTED

input |
---|

4 10AAAA AAAA AAAA AAAA |

correct output |
---|

AAAAAAA |

user output |
---|

AAAAAAA |

#### Test 4

Verdict: ACCEPTED

input |
---|

4 19AAAA AAAA AAAA AAAA |

correct output |
---|

AAAAAAA |

user output |
---|

AAAAAAA |

#### Test 5

Verdict: ACCEPTED

input |
---|

4 20AAAA AAAA AAAA AAAA |

correct output |
---|

AAAAAAA |

user output |
---|

AAAAAAA |

#### Test 6

Verdict: ACCEPTED

input |
---|

4 1QNJP EVJU XHZF RXCV |

correct output |
---|

QEVHXCV |

user output |
---|

QEVHXCV |

#### Test 7

Verdict: ACCEPTED

input |
---|

4 2QNJP EVJU XHZF RXCV |

correct output |
---|

QEVHZCV |

user output |
---|

QEVHZCV |

#### Test 8

Verdict: ACCEPTED

input |
---|

4 10QNJP EVJU XHZF RXCV |

correct output |
---|

QEXRXCV |

user output |
---|

QEXRXCV |

#### Test 9

Verdict: ACCEPTED

input |
---|

4 19QNJP EVJU XHZF RXCV |

correct output |
---|

QNVJZCV |

user output |
---|

QNVJZCV |

#### Test 10

Verdict: ACCEPTED

input |
---|

4 20QNJP EVJU XHZF RXCV |

correct output |
---|

QNVJZFV |

user output |
---|

QNVJZFV |

#### Test 11

Verdict: ACCEPTED

input |
---|

30 1AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ... |

correct output |
---|

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |

user output |
---|

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |

#### Test 12

Verdict: ACCEPTED

input |
---|

30 15033633249770520AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ... |

correct output |
---|

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |

user output |
---|

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |

#### Test 13

Verdict: ACCEPTED

input |
---|

30 30067266499541040AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA ... |

correct output |
---|

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |

user output |
---|

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA... |

#### Test 14

Verdict: ACCEPTED

input |
---|

30 1QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ... |

correct output |
---|

QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB... |

user output |
---|

QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB... |

#### Test 15

Verdict: ACCEPTED

input |
---|

30 15033633249770520QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ... |

correct output |
---|

QNXZYLYURTAYRYZQUKZCYOPKYKLQPX... |

user output |
---|

QNXZYLYURTAYRYZQUKZCYOPKYKLQPX... |

#### Test 16

Verdict: ACCEPTED

input |
---|

30 30067266499541040QNJPEVJUXHZFRXCVKBSJKUURVPLYUI RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP WYLTEQJBJRPSEMPOESVKFTQKEMSIAP ... |

correct output |
---|

QRXZYLYURTAYRYZQUKZCYOPKYKLQPX... |

user output |
---|

QRXZYLYURTAYRYZQUKZCYOPKYKLQPX... |