Educational Codeforces Round 100 (Rated for Div. 2) B. Find The Array 풀이

문제

문제로 이동

Problem - B - Codeforces

---

문제 설명

입력되는 수열을 A, 새로 생성 해야하는 수열을 B라고 두자.

 

B 수열의 조건

위와 같은 조건이 주어진다. 위의 조건을 만족하는 B를 출력해야 한다.

이게 어떤 의미인지 예시에서 알아보자.

---

예시

예시 입력 1

S : A배열의 총합

조건 : 같은 인덱스 끼리의 차이(절대값)의 합 * 2가 S보다 작거나 같아야 한다.

 

B 수열의 조건

 

B의 총 합이 A의 총 합(S)보다 작다면 성립이 된다.

하지만 문제설명에서 언급했듯이 주의해야 할 점이 있다.

---

주의해야할 점

1. B_i와 B_i+1는 서로 나눠지는 관계다. 즉, 한쪽은 약수 반대쪽은 배수가 되어야 한다.

 

이 조건을 만족하는 수는 바로 2의 제곱수이다.

---

규칙

A_i 보다 작은 2의 제곱수 B_i를 만들면 된다.

 

소스코드

tmp = 1
while tmp <= A[i]:
	tmp*=2

 

다른 풀이

대회 종료후 스트리밍을 보다가 한 유저가 알려준 방법이다.

1. 홀수 인덱스에 전부 1을 넣고 나머지는 A와 같은 수를 넣는 방법

2. 1번이 안되면 짝수 인덱스에 전부 1을 넣고 나머지는 A와 같은 수를 넣는 방법

 

1은 모든 수의 약수이다...