본문으로 이동
코드패스 by Devin.KR
로그인 Devin.KR

문제 5635 · 기가 III

라이더 단말 패킷의 상태 플래그

인증 제출 통계 · 5분마다 갱신 · 정답 비율 = 정답 제출 / 전체 제출
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1000ms / 테스트 (언어별 보정은 아래 표)메모리: 측정하지 않음(브라우저 채점)0000.00%

문제

배달 앱 서버는 라이더 단말이 보낸 32비트 부호 없는 정수 패킷을 순서대로 N개 받았다. 패킷의 상위 8비트(31번~24번 비트)가 정확히 16진수 D0이고, 32비트 전체에서 값이 1인 비트의 개수가 짝수이면 정상 패킷이다. 둘 중 하나라도 어긋나면 비정상 패킷이다. 정상 패킷의 하위 24비트(23번~0번 비트)는 주문 상태 플래그 마스크이다. 각 비트는 배차, 픽업, 이동, 도착 같은 상태 하나를 뜻한다. 서버에는 점검 대상 상태 집합 T(24비트 마스크)가 있다. 연속한 패킷 구간이 다음 세 조건을 모두 만족하면 유효 구간이라 부른다. 첫째, 구간 안의 모든 패킷이 정상 패킷이다. 둘째, 구간 안의 모든 정상 패킷의 마스크가 T의 부분집합이다. 즉 마스크에서 켜진 비트는 모두 T에서도 켜져 있다. 셋째, 구간 안 모든 마스크를 비트 OR로 합친 값이 T와 정확히 같다. 구간은 시작과 끝 위치로 구분하며 패킷 값이 같아도 위치가 다르면 서로 다른 구간이다. 길이가 1인 구간도 구간이다. 유효 구간의 개수를 구하라. T가 0이면 정상 패킷의 마스크는 0이 될 수 없으므로 답은 0이다.

입력

첫 줄에 패킷 수 N과 T가 공백으로 주어진다. T는 6자리 16진수(대문자 0-9, A-F)이며 0 이상 FFFFFF 이하이다. 이어지는 N개의 줄에 패킷이 하나씩 8자리 16진수(대문자)로 주어진다. 1 ≤ N ≤ 200000이다.

출력

유효 구간의 개수를 한 줄에 정수로 출력한다.

예제 입력 1

10 000007
D0000001
D0000002
D0000004
D0000003
D0000007
D0000010
D0000001
D0000002
D0000004
D0000004

예제 출력 1

4

예제 입력 2

3 000001
D0000001
D0000001
D0000001

예제 출력 2

6
힌트 펼치기
  • 비정상 패킷과 T에 없는 비트를 가진 패킷은 구간을 끊는 장벽이다.
  • 오른쪽 끝을 고정하면 왼쪽 시작점에 따른 OR 값은 최대 25가지뿐이다. OR 값이 같은 시작점을 묶어 개수와 함께 관리한다.

출처: Devin.KR 자체 제작

알고리즘 분류비트 연산구현해시

풀이 작성

연습 채점은 공개 테스트로 실행합니다. 인증 제출은 코드를 봉인한 뒤 새 입력을 실행하고 서버에서 출력을 대조하며 코드와 판정을 저장합니다.

Python 기본 시간 제한 = 문제 시간 제한 × 3 + 2초. 문제별 예외는 아래 표에 반영됩니다. 표준 라이브러리만 지원합니다.

Ctrl+Enter: 연습 채점 · Tab: 들여쓰기 · Esc 후 Tab: 다음 요소로 이동. 언어별 초안은 이 브라우저에 저장됩니다. JavaScript 입력: require('fs').readFileSync(0, 'utf8'), readline 또는 input().

로그인하면 인증 제출을 사용할 수 있습니다.

풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.

    연습 기록은 이 브라우저에 최근 50개를 저장합니다. 인증 기록은 내 제출에서 확인하세요.

    이 브라우저의 연습 기록

      언어별 제한

      테스트 케이스마다 새 전역에서 실행하며 준비 시간은 제외합니다. 시간 초과된 출력은 검사하지 않습니다. 브라우저·기기 성능에 따라 실행 시간이 달라집니다.

      언어엔진(버전)시간 제한메모리
      javascript사용자 브라우저 JavaScript 엔진 (버전은 브라우저에 따라 다름)1000ms / 테스트측정하지 않음(브라우저 채점)
      pythonPyodide 314.0.7 (CPython 3.14 WASM)5000ms / 테스트측정하지 않음(브라우저 채점)