29205번 - 마라톤 서브태스크다국어

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB197191712.977%

문제

$K$명의 KSA 학생들은 벌점 누적에 대한 벌칙으로 마라톤을 하러 왔다. 마라톤 경기장은 $N$개의 체크포인트와 서로 다른 두 체크포인트를 양방향으로 연결하는 $M$개의 길로 이루어져 있다. $i$번 길은 $A_i$번 체크포인트와 $B_i$번 체크포인트를 연결하고, 이 길을 지나는 데 $C_i$의 시간이 걸린다. 임의의 체크포인트에서 다른 체크포인트로 가는 경로는 항상 존재한다.

학생들은 $1$번 체크포인트를 출발해서 $N$번 체크포인트에서 마라톤을 끝내야 한다. $j$번 학생은 초기에 벌점이 $j$점이고 체크포인트를 한 번 지날 때마다 벌점을 $1$점 감점받는다. 이때, 처음 출발하는 $1$번 체크포인트와 $N$번 체크포인트에서도 벌점이 감점되며, 같은 체크포인트를 여러 번 지나도 된다. 단, 길 중간에서 되돌아올 수는 없다.

학생들은 벌점이 $0$점이 된 이후에 체크포인트를 지나서는 안 되며, 마라톤이 끝났을 때 벌점이 정확히 $0$점이어야 한다. 빨리 쉬고 싶은 학생들을 위해 각 학생이 마라톤을 끝내기 위한 최소 시간을 구해보자.

입력

첫 번째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다.

$i+1$번째 줄에 세 정수 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다. $(1 \leq i \leq M)$

출력

$i$번 학생이 마라톤을 끝내기 위한 최소 시간을 $D_i$라고 할 때, $D_1 + D_2 + \cdots + D_K$를 $998244353$으로 나눈 나머지를 출력한다.

단, $i$번 학생이 마라톤을 끝낼 방법이 없는 경우에는 $D_i=0$이다.

제한

  • $2 \leq N \leq 1500$
  • $N-1 \leq M \leq 3000$
  • $1 \leq K \leq 10^9$
  • $1 \leq A_i < B_i \leq N$ ($1 \leq i \leq M$)
  • $1 \leq C_i \leq 10^9$ ($1 \leq i \leq M$)
  • $(A_i, B_i) \neq (A_j, B_j)$ $(1 \leq i < j \leq M)$
  • $1 \leq i < j \leq N$인 모든 $i$, $j$에 대해서 $i$번 체크포인트와 $j$번 체크포인트를 연결하는 경로가 존재

서브태스크

번호배점제한
17

$K \leq 1500$

241

$K \leq 3 \times 10^6$

324

$M = N-1$

428

추가 제약 조건 없음

예제 입력 1 

2 1 7
1 2 10

예제 출력 1 

90

$1$, $3$, $5$, $7$번 학생은 마라톤을 끝내는 것이 불가능하다.

$2$번 학생은 마라톤을 끝내는데 $10$의 시간이 걸린다. 이때 경로는 $1$ → $2$이다.

$4$번 학생은 마라톤을 끝내는데 $30$의 시간이 걸린다. 이때 경로는 $1$ → $2$ → $1$ → $2$이다.

$6$번 학생은 마라톤을 끝내는데 $50$의 시간이 걸린다. 이때 경로는 $1$ → $2$ → $1$ → $2$ → $1$ → $2$이다.

예제 입력 2 

5 5 5
1 2 1
2 3 4
3 5 3
1 4 2
4 5 3

예제 출력 2 

20

$1$, $2$번 학생은 마라톤을 끝내는 것이 불가능하다.

$3$번 학생은 마라톤을 끝내는데 $5$의 시간이 걸린다. 이때 경로는 $1$ → $4$ → $5$이다.

$4$번 학생은 마라톤을 끝내는데 $8$의 시간이 걸린다. 이때 경로는 $1$ → $2$ → $3$ → $5$이다.

$5$번 학생은 마라톤을 끝내는데 $7$의 시간이 걸린다. 이때 경로는 $1$ → $2$ → $1$ → $4$ → $5$이다.

예제 입력 3 

6 9 20
1 2 1
1 3 1
2 3 2
2 4 2
3 4 3
2 6 1
4 5 2
4 6 3
5 6 1

예제 출력 3 

198
W3sicHJvYmxlbV9pZCI6IjI5MjA1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViOWM4XHViNzdjXHVkMWE0IiwiZGVzY3JpcHRpb24iOiI8cD4kSyRcdWJhODVcdWM3NTggS1NBIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWJjOGNcdWM4MTAgXHViMjA0XHVjODAxXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWJjOGNcdWNlNTlcdWM3M2NcdWI4NWMgXHViOWM4XHViNzdjXHVkMWE0XHVjNzQ0IFx1ZDU1OFx1YjdlYyBcdWM2NTRcdWIyZTQuIFx1YjljOFx1Yjc3Y1x1ZDFhNCBcdWFjYmRcdWFlMzBcdWM3YTVcdWM3NDAgJE4kXHVhYzFjXHVjNzU4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YzY0MCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVjNTkxXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCAkTSRcdWFjMWNcdWM3NTggXHVhZTM4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICRpJFx1YmM4OCBcdWFlMzhcdWM3NDAgJEFfaSRcdWJjODggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNjQwICRCX2kkXHViYzg4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWFjZTAsIFx1Yzc3NCBcdWFlMzhcdWM3NDQgXHVjOWMwXHViMDk4XHViMjk0IFx1YjM3MCAkQ19pJFx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LiBcdWM3ODRcdWM3NThcdWM3NTggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI4NWMgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgJDEkXHViYzg4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWNkOWNcdWJjMWNcdWQ1NzRcdWMxMWMgJE4kXHViYzg4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YzVkMFx1YzExYyBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gJGokXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWNkMDhcdWFlMzBcdWM1ZDAgXHViYzhjXHVjODEwXHVjNzc0ICRqJFx1YzgxMFx1Yzc3NFx1YWNlMCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVkNTVjIFx1YmM4OCBcdWM5YzBcdWIwYTAgXHViNTRjXHViOWM4XHViMmU0IFx1YmM4Y1x1YzgxMFx1Yzc0NCAkMSRcdWM4MTAgXHVhYzEwXHVjODEwXHViYzFiXHViMjk0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Y2M5OFx1Yzc0YyBcdWNkOWNcdWJjMWNcdWQ1NThcdWIyOTQgJDEkXHViYzg4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1YzY0MCAkTiRcdWJjODggXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHVjNWQwXHVjMTFjXHViM2M0IFx1YmM4Y1x1YzgxMFx1Yzc3NCBcdWFjMTBcdWM4MTBcdWI0MThcdWJhNzAsIFx1YWMxOVx1Yzc0MCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWI5N2MgXHVjNWVjXHViN2VjIFx1YmM4OCBcdWM5YzBcdWIwOThcdWIzYzQgXHViNDFjXHViMmU0LiBcdWIyZTgsIFx1YWUzOCBcdWM5MTFcdWFjMDRcdWM1ZDBcdWMxMWMgXHViNDE4XHViM2NjXHVjNTQ0XHVjNjJjIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWJjOGNcdWM4MTBcdWM3NzQgJDAkXHVjODEwXHVjNzc0IFx1YjQxYyBcdWM3NzRcdWQ2YzRcdWM1ZDAgXHVjY2I0XHVkMDZjXHVkM2VjXHVjNzc4XHVkMmI4XHViOTdjIFx1YzljMFx1YjA5OFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDE4XHViYTcwLCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NzQgXHViMDVkXHViMGFjXHVjNzQ0IFx1YjU0YyBcdWJjOGNcdWM4MTBcdWM3NzQgXHVjODE1XHVkNjU1XHVkNzg4ICQwJFx1YzgxMFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YmU2OFx1YjlhYyBcdWMyNmNcdWFjZTAgXHVjMmY2XHVjNzQwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0NCBcdWM3MDRcdWQ1NzQgXHVhYzAxIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1Yzc5MC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEzOCBcdWM4MTVcdWMyMTggJE4kLCAkTSQsICRLJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JGkrMSRcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzEzOCBcdWM4MTVcdWMyMTggJEFfaSQsICRCX2kkLCAkQ19pJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGVxIGkgXFxsZXEgTSkkPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JGkkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHVhZTMwIFx1YzcwNFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0ICREX2kkXHViNzdjXHVhY2UwIFx1ZDU2MCBcdWI1NGMsICREXzEgKyBEXzIgKyBcXGNkb3RzICsgRF9LJFx1Yjk3YyAkOTk4MjQ0MzUzJFx1YzczY1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU4LCAkaSRcdWJjODggXHVkNTU5XHVjMGRkXHVjNzc0IFx1YjljOFx1Yjc3Y1x1ZDFhNFx1Yzc0NCBcdWIwNWRcdWIwYmMgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJERfaT0wJFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDIgXFxsZXEgTiBcXGxlcSAxNTAwJDxcL2xpPlxyXG5cdDxsaT4kTi0xIFxcbGVxIE0gXFxsZXEgMzAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgSyBcXGxlcSAxMF45JDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBBX2kgJmx0OyBCX2kgXFxsZXEgTiQgKCQxIFxcbGVxIGkgXFxsZXEgTSQpPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIENfaSBcXGxlcSAxMF45JCAoJDEgXFxsZXEgaSBcXGxlcSBNJCk8XC9saT5cclxuXHQ8bGk+JChBX2ksIEJfaSkgXFxuZXEgKEFfaiwgQl9qKSQgJCgxIFxcbGVxIGkgJmx0OyBqIFxcbGVxIE0pJDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBpICZsdDsgaiBcXGxlcSBOJFx1Yzc3OCBcdWJhYThcdWI0ZTAgJGkkLCAkaiRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjICRpJFx1YmM4OCBcdWNjYjRcdWQwNmNcdWQzZWNcdWM3NzhcdWQyYjhcdWM2NDAgJGokXHViYzg4IFx1Y2NiNFx1ZDA2Y1x1ZDNlY1x1Yzc3OFx1ZDJiOFx1Yjk3YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVhY2JkXHViODVjXHVhYzAwIFx1Yzg3NFx1YzdhYzxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8cD4kSyBcXGxlcSAxNTAwJDxcL3A+XHJcbiIsInN1YnRhc2syIjoiPHA+JEsgXFxsZXEgMyBcXHRpbWVzIDEwXjYkPFwvcD5cclxuIiwic3VidGFzazMiOiI8cD4kTSA9IE4tMSQ8XC9wPlxyXG4iLCJzdWJ0YXNrNCI6IjxwPlx1Y2Q5NFx1YWMwMCBcdWM4MWNcdWM1N2QgXHVjODcwXHVhYzc0IFx1YzVjNlx1Yzc0YzxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzEiOiI8cD4kMSQsICQzJCwgJDUkLCAkNyRcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQwIFx1YjljOFx1Yjc3Y1x1ZDFhNFx1Yzc0NCBcdWIwNWRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JDIkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwICQxMCRcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1YWNiZFx1Yjg1Y1x1YjI5NCAkMSQgJnJhcnI7ICQyJFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JDQkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwICQzMCRcdWM3NTggXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjliMFx1YjJlNC4gXHVjNzc0XHViNTRjIFx1YWNiZFx1Yjg1Y1x1YjI5NCAkMSQgJnJhcnI7ICQyJCAmcmFycjsgJDEkICZyYXJyOyAkMiRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPiQ2JFx1YmM4OCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHViOWM4XHViNzdjXHVkMWE0XHVjNzQ0IFx1YjA1ZFx1YjBiNFx1YjI5NFx1YjM3MCAkNTAkXHVjNzU4IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YjBcdWIyZTQuIFx1Yzc3NFx1YjU0YyBcdWFjYmRcdWI4NWNcdWIyOTQgJDEkICZyYXJyOyAkMiQgJnJhcnI7ICQxJCAmcmFycjsgJDIkICZyYXJyOyAkMSQgJnJhcnI7ICQyJFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+JDEkLCAkMiRcdWJjODggXHVkNTU5XHVjMGRkXHVjNzQwIFx1YjljOFx1Yjc3Y1x1ZDFhNFx1Yzc0NCBcdWIwNWRcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JDMkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwICQ1JFx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVhY2JkXHViODVjXHViMjk0ICQxJCAmcmFycjsmbmJzcDskNCQgJnJhcnI7ICQ1JFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JDQkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwICQ4JFx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVhY2JkXHViODVjXHViMjk0ICQxJCAmcmFycjsmbmJzcDskMiQgJnJhcnI7Jm5ic3A7JDMkICZyYXJyOyZuYnNwOyQ1JFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+JDUkXHViYzg4IFx1ZDU1OVx1YzBkZFx1Yzc0MCBcdWI5YzhcdWI3N2NcdWQxYTRcdWM3NDQgXHViMDVkXHViMGI0XHViMjk0XHViMzcwICQ3JFx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVhYzc4XHViOWIwXHViMmU0LiBcdWM3NzRcdWI1NGMgXHVhY2JkXHViODVjXHViMjk0ICQxJCAmcmFycjsmbmJzcDskMiQgJnJhcnI7Jm5ic3A7JDEkICZyYXJyOyZuYnNwOyQ0JCAmcmFycjsgJDUkXHVjNzc0XHViMmU0LjxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI5MjA1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFyYXRob24iLCJkZXNjcmlwdGlvbiI6IjxwPiRLJCBzdHVkZW50cyBmcm9tIEtTQSBoYXZlIGNvbWUgdG8gcGFydGljaXBhdGUgaW4gYSBtYXJhdGhvbiBhcyBhIHB1bmlzaG1lbnQgZm9yIGFjY3VtdWxhdGluZyBkZW1lcml0IHBvaW50cy4gVGhlIG1hcmF0aG9uIGNvdXJzZSBjb25zaXN0cyBvZiAkTiQgY2hlY2twb2ludHMgYW5kICRNJCByb2FkcyB0aGF0IGNvbm5lY3QgdHdvIGRpZmZlcmVudCBjaGVja3BvaW50cyBpbiBib3RoIGRpcmVjdGlvbnMuIFJvYWQgJGkkIGNvbm5lY3RzIGNoZWNrcG9pbnQgJEFfaSQgYW5kIGNoZWNrcG9pbnQgJEJfaSQsIGFuZCBpdCB0YWtlcyAkQ19pJCB0aW1lIHRvIHBhc3MgdGhyb3VnaCB0aGlzIHJvYWQuIFRoZXJlIGFsd2F5cyBleGlzdHMgYSBwYXRoIGZyb20gYW55IGNoZWNrcG9pbnQgdG8gYW5vdGhlciBjaGVja3BvaW50LjxcL3A+XHJcblxyXG48cD5UaGUgc3R1ZGVudHMgbXVzdCBzdGFydCBmcm9tIGNoZWNrcG9pbnQgJDEkIGFuZCBmaW5pc2ggdGhlIG1hcmF0aG9uIGF0IGNoZWNrcG9pbnQgJE4kLiBJbml0aWFsbHksIHN0dWRlbnQgJGokIGhhcyZuYnNwOyRqJCBkZW1lcml0IHBvaW50cywgYW5kIHRoZXkgcmVjZWl2ZSBhIGRlZHVjdGlvbiBvZiAkMSQgcG9pbnQgZXZlcnkgdGltZSB0aGV5IHBhc3MmbmJzcDthIGNoZWNrcG9pbnQuIEluIGFkZGl0aW9uLCBkZW1lcml0IHBvaW50cyBhcmUgZGVkdWN0ZWQgYXQgdGhlIHN0YXJ0aW5nIGNoZWNrcG9pbnQgJDEkIGFuZCB0aGUgZmluaXNoaW5nIGNoZWNrcG9pbnQgJE4kLCBhbmQgdGhleSBhcmUgYWxsb3dlZCB0byBwYXNzIHRocm91Z2ggdGhlIHNhbWUgY2hlY2twb2ludCBtdWx0aXBsZSB0aW1lcy4gSG93ZXZlciwgdGhleSBjYW5ub3QgdHVybiBiYWNrIGluIHRoZSBtaWRkbGUgb2YgYSByb2FkLjxcL3A+XHJcblxyXG48cD5UaGUgc3R1ZGVudHMgbXVzdCBub3QgcGFzcyBhbnkgY2hlY2twb2ludHMgYWZ0ZXIgdGhlaXIgZGVtZXJpdCZuYnNwO3BvaW50cyByZWFjaCZuYnNwOyQwJCwgYW5kIHRoZXkgbXVzdCBoYXZlIGV4YWN0bHkgJDAkIGRlbWVyaXQgcG9pbnRzIHdoZW4gdGhleSBmaW5pc2ggdGhlIG1hcmF0aG9uLiBMZXQmIzM5O3MgZmluZCB0aGUgbWluaW11bSB0aW1lIHJlcXVpcmVkIGZvciBlYWNoIHN0dWRlbnQgdG8gZmluaXNoIHRoZSBtYXJhdGhvbiwgZm9yIHRoZSBzdHVkZW50cyB3aG8gd2FudCB0byByZXN0IGFzIHNvb24gYXMgcG9zc2libGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBjb250YWlucyB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnMgJE4kLCAkTSQsIGFuZCAkSyQuPFwvcD5cclxuXHJcbjxwPlRoZSAkKGkrMSkkLXRoIGxpbmUgY29udGFpbnMgdGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRBX2kkLCAkQl9pJCwgYW5kICRDX2kkLiAkKDEgXFxsZXEgaSBcXGxlcSBNKSQ8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5XaGVuICREX2kkIGlzIHRoZSBtaW5pbXVtIHRpbWUgZm9yIHRoZSZuYnNwO3N0dWRlbnQgJGkkIHRvIGZpbmlzaCB0aGUgbWFyYXRob24sIHByaW50ICREXzEgKyBEXzIgKyBcXGNkb3RzICsgRF9LJCBtb2R1bG8gJDk5ODI0NDM1MyQuPFwvcD5cclxuXHJcbjxwPklmIHRoZSZuYnNwO3N0dWRlbnQgJGkkIGNhbm5vdCBmaW5pc2ggdGhlIG1hcmF0aG9uLCAkRF9pPTAkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+JDIgXFxsZXEgTiBcXGxlcSAxNTAwJDxcL2xpPlxyXG5cdDxsaT4kTi0xIFxcbGVxIE0gXFxsZXEgMzAwMCQ8XC9saT5cclxuXHQ8bGk+JDEgXFxsZXEgSyBcXGxlcSAxMF45JDxcL2xpPlxyXG5cdDxsaT4kMSBcXGxlcSBBX2kgJmx0OyBCX2kgXFxsZXEgTiQgKCQxIFxcbGVxIGkgXFxsZXEgTSQpPFwvbGk+XHJcblx0PGxpPiQxIFxcbGVxIENfaSBcXGxlcSAxMF45JCAoJDEgXFxsZXEgaSBcXGxlcSBNJCk8XC9saT5cclxuXHQ8bGk+JChBX2ksIEJfaSkgXFxuZXEgKEFfaiwgQl9qKSQgJCgxIFxcbGVxIGkgJmx0OyBqIFxcbGVxIE0pJDxcL2xpPlxyXG5cdDxsaT5Gb3IgYWxsICRpJCwgJGokIHNhdGlzZnlpbmcgJDEgXFxsZXEgaSAmbHQ7Jm5ic3A7aiBcXGxlcSBOJCwgYSBwYXRoIGNvbm5lY3RpbmcgY2hlY2twb2ludCAkaSQgYW5kIGNoZWNrcG9pbnQmbmJzcDskaiQmbmJzcDtleGlzdHM8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHA+JEsgXFxsZXEgMTUwMCQ8XC9wPlxyXG4iLCJzdWJ0YXNrMiI6IjxwPiRLIFxcbGVxIDMgXFx0aW1lcyAxMF42JDxcL3A+XHJcbiIsInN1YnRhc2szIjoiPHA+JE0gPSBOLTEkPFwvcD5cclxuIiwic3VidGFzazQiOiI8cD5ObyBhZGRpdGlvbmFsIGNvbnN0cmFpbnRzPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlN0dWRlbnRzICQxJCwmbmJzcDskMyQsICQ1JCwgYW5kICQ3JCBjYW5ub3QgZmluaXNoIHRoZSBtYXJhdGhvbi48XC9wPlxyXG5cclxuPHA+U3R1ZGVudCAkMiQgdGFrZXMgJDEwJCB0aW1lIHRvIGZpbmlzaCB0aGUgbWFyYXRob24uIFRoZSBwYXRoIGlzICQxJCAmcmFycjsgJDIkLjxcL3A+XHJcblxyXG48cD5TdHVkZW50ICQ0JCB0YWtlcyAkMzAkIHRpbWUgdG8gZmluaXNoIHRoZSBtYXJhdGhvbi4gVGhlIHBhdGggaXMgJDEkICZyYXJyOyAkMiQgJnJhcnI7ICQxJCAmcmFycjsgJDIkLjxcL3A+XHJcblxyXG48cD5TdHVkZW50ICQ2JCB0YWtlcyAkNTAkIHRpbWUgdG8gZmluaXNoIHRoZSBtYXJhdGhvbi4gVGhlIHBhdGggaXMgJDEkICZyYXJyOyAkMiQgJnJhcnI7ICQxJCAmcmFycjsgJDIkICZyYXJyOyAkMSQgJnJhcnI7ICQyJC48XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8yIjoiPHA+U3R1ZGVudCAkMSQgYW5kICQyJCBjYW5ub3QgZmluaXNoIHRoZSBtYXJhdGhvbi48XC9wPlxyXG5cclxuPHA+U3R1ZGVudCAkMyQgdGFrZXMgJDUkIHRpbWUgdG8gZmluaXNoIHRoZSBtYXJhdGhvbi4gVGhlIHBhdGggaXMgJDEkICZyYXJyOyAkNCQgJnJhcnI7ICQ1JC48XC9wPlxyXG5cclxuPHA+U3R1ZGVudCAkNCQgdGFrZXMgJDgkIHRpbWUgdG8gZmluaXNoIHRoZSBtYXJhdGhvbi4gVGhlIHBhdGggaXMgJDEkICZyYXJyOyAkMiQgJnJhcnI7ICQzJCAmcmFycjsgJDUkLjxcL3A+XHJcblxyXG48cD5TdHVkZW50ICQ1JCB0YWtlcyAkNyQgdGltZSB0byBmaW5pc2ggdGhlIG1hcmF0aG9uLiBUaGUgcGF0aCBpcyAkMSQgJnJhcnI7ICQyJCAmcmFycjsgJDEkICZyYXJyOyAkNCQgJnJhcnI7ICQ1JC48XC9wPlxyXG4ifV0=

출처

School > 한국과학영재학교 > 2023 KSA Automata Summer Contest J번

채점 및 기타 정보

  • 예제는 채점하지 않는다.

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

  • 사업자 등록 번호: 541-88-00682
  • 대표자명: 최백준
  • 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
  • 전화번호: 02-521-0487 (이메일로 연락 주세요)
  • 이메일: contacts@startlink.io
  • 통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)