27544번 - コイン集め 2 (Coin Collecting 2) 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 3 | 3 | 3 | 100.000% |
문제
机の上に，縦 H 行，横 W 列の長方形状にコインが並べられている． 最初，上から i 行目 (1 ≦ i ≦ H)，左から j 列目 (1 ≦ j ≦ W) のコインは， Si,j= # のとき表面，Si,j= . のとき裏面が見えている状態である．
葵と凛は，これらのコインを用いてゲームを行うことにした．ゲームは以下のような流れで行われる．
- 葵がどれか 1 つの行を選び，その行のコインをすべてひっくり返す．
- 凛がどれか 1 つの列を選び，その列のコインをすべてひっくり返す．
- 葵が，表面が見えるコインをすべて獲得する．また凛が，裏面が見えるコインをすべて獲得する．
葵と凛はそれぞれ，できるだけ多くのコインを獲得したい．
ゲーム開始時のコインの状態が与えられたとき， 両者が最善を尽くした場合にそれぞれが獲得できるコインの枚数を求めるプログラムを作成せよ．
입력
入力は以下の形式で与えられる．
H W S1,1 S1,2 … S1,W S2,1 S2,2 … S2,W ︙ SH,1 SH,2 … SH,W
출력
葵と凛の得点をこの順に空白区切りで出力せよ．
제한
- H ≧ 1．
- W ≧ 1．
- H × W ≦ 500 000．
- Si, j は
#，.のいずれかである (1 ≦ i ≦ H，1 ≦ j ≦ W)． - H, W は整数である．
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 2 | H = 1，W = 1． |
| 2 | 8 | H = 1，W ≦ 40． |
| 3 | 9 | H ≦ 40，W = 1． |
| 4 | 14 | H = 2，W = 2． |
| 5 | 23 | H ≦ 40，W ≦ 40． |
| 6 | 18 | H ≦ 250，W ≦ 250． |
| 7 | 26 | 追加の制約はない． |
예제 입력 1
1 1 #
예제 출력 1
1 0
この入力例では，必ず以下のようにゲームが進行する．
- まず，葵が 1 行目のすべてのコインをひっくり返す．
- 次に，凛が 1 列目のすべてのコインをひっくり返す．
このとき，唯一のコインの見える面は「表→裏→表」と変化するため，葵が 1 枚のコインを獲得できるが，凛はコインを獲得できない．したがって，1，0 をこの順に空白区切りで出力する．
なお，この入力例は小課題 1, 2, 3, 5, 6, 7 の制約を満たす．
예제 입력 2
5 5 ##### ####. ###.. ##... #....
예제 출력 2
13 12
両者が最善を尽くした場合の，ゲームの進行の一例を下図に示す．
この入力例は小課題 5, 6, 7 の制約を満たす．
예제 입력 3
1 40 ..........##########..........##########
예제 출력 3
19 21
この入力例は小課題 2, 5, 6, 7 の制約を満たす．
예제 입력 4
7 1 # # # # # # #
예제 출력 4
1 6
この入力例は小課題 3, 5, 6, 7 の制約を満たす．
예제 입력 5
5 5 .###. ...## ..##. .##.. ##...
예제 출력 5
11 14
この入力例は小課題 5, 6, 7 の制約を満たす．
예제 입력 6
10 40 ........................................ ..######.....####.....#####.....####.... .....#......#....#......#......#........ .....#......#....#......#......#........ .....#......#....#......#......#........ .....#......#....#......#......#..####.. ..#..#......#....#......#......#....#... ..#..#......#....#......#......#....#... ...##........####.....#####.....####.... ........................................
예제 출력 6
104 296
この入力例は小課題 5, 6, 7 の制約を満たす．
출처
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics for Girls > JOIG 2023 4번
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호