2016.05.26 모임 55

모임 공지

• 활동 일시: 05월 26일 (목) 19:02
• 모임 장소: 하이퍼 커넥트 14층
• 활동 주제:
• 샌드위치 형성

장소는 이곳을 참고 하세요

A. Infinite Sequence

문제링크

등차수열의 첫항, 목표값 그리고 공차가 주어질 때, 목표값이 수열에 포함되는 지 여부

간단히 이렇게 하면 될 것 같지만,

    while (true) {
        if (begin == target) {
            return true;
        }
        begin += jump;

        if (0 < jump && target < begin) break;
        if (jump < 0 && begin < target) break;
        if (jump == 0) break;
    }
    return false;

이 방법은 꽤 오래 걸린다.
worst case 는 시작이 -10^9, 공차가 1, 목표값이 10^9 인 경우이다.

B. Restoring Painting

문제링크

n, a, b, c, d 가 주어질 때,
subsquare 2X2 의 합이 모두 같게 하면서
남은 칸을 채울 수 있는 숫자들의 총 경우의 수 구하기

(1 ≤ n ≤ 100 000, 1 ≤ a, b, c, d ≤ n)

대략 아래와 같이 해 보면,

x a y
b m c
z d w

간단한 산수에 의해서 쉽게 유도해 낼 수 있다.

y = x + b - c
z = x + a - d
w = a + y - d

x 가 정해지면 나머지도 정해진다.
모든 x 에 대해서 가능한 조합을 구하고
m 은 어떠한 값도 될 수 있으니 가능한 경우의 수를 곱하면 된다.

C. Money Transfers

문제링크

사진