CSES - HIIT Open 2018 - Results
Submission details
Task:Find a Word
Sender:Ukkonen Fan Club
Submission time:2018-05-26 12:03:13
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.02 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
#12ACCEPTED0.01 sdetails
#13ACCEPTED0.02 sdetails
#14ACCEPTED0.01 sdetails
#15ACCEPTED0.01 sdetails
#16ACCEPTED0.01 sdetails

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 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: ACCEPTED

input
30 15033633249770520
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 13

Verdict: ACCEPTED

input
30 30067266499541040
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
...

correct output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

user output
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

Test 14

Verdict: ACCEPTED

input
30 1
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

user output
QNJLGFBBMJBHCCBOCEFBPLDCFGDJKB...

Test 15

Verdict: ACCEPTED

input
30 15033633249770520
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
QNXZYLYURTAYRYZQUKZCYOPKYKLQPX...

Test 16

Verdict: ACCEPTED

input
30 30067266499541040
QNJPEVJUXHZFRXCVKBSJKUURVPLYUI
RXLGFBNQPBKQQRQFHLXUIUPLUOUOQW
FZNNUBMTLXUMTSJOOGBDBEVEYVWOLP
WYLTEQJBJRPSEMPOESVKFTQKEMSIAP
...

correct output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...

user output
QRXZYLYURTAYRYZQUKZCYOPKYKLQPX...