AtCoder Beginner Contest 243A-D4 전체 보도
읽은 사람이 무슨 일이 있으면 사양하지 말고 평론하세요.기다리고 있겠습니다.
A - Shampoo
문제문
고교군의 집에는 고교군, 고교군의 아버지, 고교군의 어머니 세 사람이 살고 모두 매일 저녁 욕실에서 머리를 감는다.
목욕할 때는 다카하시의 아버지, 다카하시의 어머니, 다카하시 순으로 각각 A, B, C㎖의 샴푸를 사용한다.
오늘 아침에는 병 안에 V밀리리터의 샴푸가 남아 있었다.이렇게 보충하지 않을 때, 첫 번째 샴푸가 부족할 때는 누가 써야 합니까?
구속
1≤V,A,B,C≤$10^5$
입력에 포함된 값은 모두 정수입니다.
입력
입력은 다음과 같은 형식으로 표준 입력에서 제공된다.
V A B C
고찰하다.
3명이 모두 사용하면 계속 사용하기 때문에 V$\quiv$V(mod(A+B+C)로 설정합니다.
V샘플 코드
a.py
V,A,B,C=map(int,input().split())
V%=(A+B+C)
cnt=0
if V<A:
print("F")
elif V<A+B:
print("M")
else:
print("T")
B - Hit and Blow 문제문
길이 N의 정수 열 $A=(A 1, A 2,\dots, A N), B=(B 1, B 2,\dots, B N)$.
A의 요소는 모두 다르다.B의 요소도 완전히 다르다.
다음 두 개를 출력하십시오.
$1\leq N\leq 1000$
$1\leq A_i\leq 10^9$
$1\leq B_i\leq 10^9$
$A_1,A_2,\dots ,A_다 달라.
$B_1,B_2,\dots ,B_다 달라.
모두 정수로 입력합니다.
입력
입력은 다음과 같은 형식으로 표준 입력에서 제공된다.
$N$
$A_1\\A_2\\\dots\\A_N$
$B_1\\B_2\\\dots\\B_N$
고찰하다.
첫 번째 출력은 매우 곧게 조사되었다.
두 번째 출력을 고려하다.
A와 B에 같은 값이 있으면 집합 후 중복되지 않을 수 있다.
A와 B의 총 2N에서 이것을 빼면 같은 값의 개수를 얻을 수 있다.
여기서 같은 위치에 맞는 값의 개수(첫 번째 해)를 빼면 얻은 값
샘플 코드
b.py
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans1=0
for i in range(N):
if A[i]==B[i]:
ans1+=1
ans2=2*N-len(set([*A,*B]))-ans1
print(ans1)
print(ans2)
C - Collision 2 문제문
xy 좌표 평면에 N 사람이 있습니다.사람 i는 $(X i, Y i) 달러에 있습니다.사람마다 다른 곳에 있다.
L, R 길이 N이 있는 문자열 S.
사람 i는 $S입니다.i=R달러면 오른쪽, $S그럼 왼쪽으로 같이 같은 속도로 갑시다.여기, 오른쪽은 x축의 정방향, 왼쪽은 x축의 음방향이다.
예를 들어 $(X 1, Y 1) = (2, 3), (X 2, Y 2) = (1, 1), (X 3, Y 3) = (4, 1), S = RML 달러일 경우 다음 그림과 같이 이동합니다.
반대 방향으로 가는 사람이 같은 곳에 오는 것을 충돌이라고 한다.모두가 계속 걸을 때 충돌이 일어날까요?
구속
$2\leq N\leq 2\times 10^5$
$0\leq x_i\leq 10^9$
$0\leq y_i\leq 10^9 $
$i\neqj달러(X i, Y i)\neq(X j, Y j)$
$S는 L 및 R로 구성된 길이 N의 문자열입니다.
입력
입력은 다음과 같은 형식으로 표준 입력에서 제공된다.
$N$
$X_1\\Y_1$
$X_2\\Y_2$
$\vdots$
$X_N\\Y_N$
$S$
고찰하다.
Y축 정보와 좌우 어느 쪽의 이동을 연상 배열로 저장합니다.
좌우 이동 정보는 집합 형식으로 저장되며 첫 번째 조건의 판정은 $O(1)달러가 됩니다.
조사가 좌우 이동 조건을 충족시켰을 때 두 번째 조건을 충족시켰다.
첫 번째 조건의 판정에 사용된 연상 배열 키의 값이 x 좌표와 좌우 어느 방향으로 이동하는지 $O(1)$로 판정에 필요한 값을 꺼낼 수 있습니다.
이 조사로 두 번째 조건이 충족되는지
샘플 코드
c.py
N=int(input())
XY=[list(map(int,input().split())) for _ in range(N)]
S=input()
DICT=dict()
SET=set()
for i in range(N):
if XY[i][1] in SET:
DICT[XY[i][1]][0].add(S[i])
DICT[XY[i][1]][1].append([XY[i][0],S[i]])
else:
SET.add(XY[i][1])
DICT[XY[i][1]]=[set(S[i]),[[XY[i][0],S[i]]]]
ans="No"
for i in DICT:
if len(DICT[i][0])==2:
L,R=0,10**9
for j in DICT[i][1]:
if j[1]=="L":
L=max(j[0],L)
else:
R=min(j[0],R)
if R<L:
ans="Yes"
print(ans)
D - Moves on Binary Tree 문제문
정수리 ${2^ {10} ^ {100}에서 1달러까지의 완전 이분수, 정수리에는 $1,2,\dots, {2^ {10} ^ {100}} ^ {100}에서 1달러까지의 번호가 붙어 있습니다.
정점 1은 뿌리이고 $1\leqi\leq{2^{10}^{100]-1달러이며 정점 i는 정점 2i를 왼쪽 아들로 하고 정점 2i+1을 오른쪽 아들로 합니다.
다카하시 군은 처음에 정점 X에서 N회 이동을 했다.이동은 문자열 S로 표시되며 i번째 이동은 다음과 같습니다.
구속
$1\leq N\leq 10^6$
$\leq X\leq 10^{18}$
N, X는 정수
S는 길이 N이며 U, L, R로만 구성됩니다.
높은 다리가 뿌리 위에 있을 때는 부모님께 가고 싶지 않다
다카하시 군은 잎사귀에 있을 때 아이에게 가고 싶지 않을 것이다
고교군 N차 이동 후 정점의 번호는 10^{18}달러 이하
입력
입력은 다음과 같은 형식으로 표준 입력에서 제공된다.
N
S
고찰하다.
여러 배의 정수를 계산하는 것은 매우 느리고 비현실적이다.
거기서 속도를 내려면
나무이기 때문에 아이가 이동한 뒤 부모에게 이동하면 원래 자리로 돌아갈 생각을 하기 쉽다.
먼저 목적지를 계산해 같은 정점으로 이동하지 않고 가장 짧은 속도로 답안에 도달한다.
현재 위치는 $x$입니다. 완전히 이분수이기 때문에 부모에게 이동하는 것은 $\left\lflowor\rac{2}\right\rflowor$입니다. 왼쪽으로 이동하는 아이는 $2\times×달러이고 오른쪽으로 이동하는 아이는 $2\timesx+1입니다.
부모에게 옮길 때 뿌리가 1이면 대답을 받을 수 있다.
샘플 코드
d.py
from collections import deque
n,x=map(int,input().split())
s=list(input())
move=deque()
move.append(s[0])
for i in range(1,n):
if s[i]=="U" and len(move)!=0 and move[-1]!="U":
move.pop()
else:
move.append(s[i])
for i in move:
if i=="U":
x=max(1,x//2)
elif i=="R":
x=x*2+1
else:
x*=2
print(x)
Reference
이 문제에 관하여(AtCoder Beginner Contest 243A-D4 전체 보도), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://qiita.com/kani_kani_kani/items/9e5aadaa381dad6e0570텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)