Task: | Find a Word |

Sender: | Ukkonen Fan Club |

Submission time: | 2018-05-26 12:03:13 |

Language: | C++ |

Status: | READY |

Result: | ACCEPTED |

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

#1 | ACCEPTED | 0.02 s | details |

#2 | ACCEPTED | 0.01 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.02 s | details |

#9 | ACCEPTED | 0.01 s | details |

#10 | ACCEPTED | 0.01 s | details |

#11 | ACCEPTED | 0.01 s | details |

#12 | ACCEPTED | 0.01 s | details |

#13 | ACCEPTED | 0.02 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> typedef long long ll; using namespace std; ll dp[40][40]; ll dp2[40][40]; char t[40][40]; int main() { ll n,k; cin>>n>>k; dp[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 && j == n-1) continue; dp[i][j] = dp[i+1][j] + dp[i][j+1]; } } /* for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { cout<<dp[i][j]<<' '; } cout<<'\n'; } */ for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { cin>>t[i][j]; } } string res;; for(int i = 0; i < n+n-1; ++i) res.push_back('.'); ll cnt = 0; for(int pos = 0; pos < n+n-1; ++pos) { ll mahd = 0; //cout<<pos<<'\n'; for(int c = 'A'; c <= 'Z'; ++c) { res[pos] = c; memset(dp2, 0, sizeof dp2); for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(t[i][j] != res[i+j]) { continue; } if(i == 0 && j == 0) { dp2[i][j] = 1; } if(i > 0) { dp2[i][j] += dp2[i-1][j]; } if(j > 0) { dp2[i][j] += dp2[i][j-1]; } } } ll more = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { //cout<<dp2[i][j]<<' '; if(i+j == pos) { more += dp2[i][j] * dp[i][j]; } } //cout<<'\n'; } //cout<<'\n'; //cout<<mahd<<' '<<more<<'\n'; if(mahd + more + cnt >= k) { cnt += mahd; break; } mahd += more; } } cout<<res<<'\n'; }

### 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... |