PS 이야기

문제 링크 D. Happy Number 문제에 적혀 있는 함수 $f$가 있다. $f(f(f(...f(n))))$을 했을 때, 1이 되는지를 구하는 문제다.입력으로 주어지는 수는 최대 1,000,000,000인데, 큰 수가 주어진다하더라도 $f(n)$의 결과값은 작다. 때문에 이 문제는 함수 $f$를 구현하고 결과값이 1이 되는지만 확인하는 간단한 문제가 된다. #include using namespace std; int N; int main() { set vis; scanf("%d", &N); while (N > 1){ if (vis.count(N)){ puts("UNHAPPY"); return 0; } vis.insert(N); int nxt = 0; for (int v=N;v;v/=10) nxt +=..

전체 결과: IOI Statistics, IOI 2017 official scoreboard대한민국 결과: IOI Statistics역대 대한민국 결과: IOI Statistics 2017년 국제정보올림피아드에서 우리나라는 금1, 은2라는 성적을 거둬 종합 10위에 그쳤다. 2017년도 문제들은 예년이 비해 좀 어렵게 느껴진다. 그리고 한 동안 안나왔던 Output Only 문제가 Day 1에 출제되었다. Nowruz 문제는 2차원 격자판의 빈 칸에 적절히 장애물을 설치해서 빈 칸들이 서로 트리를 이루게했을 때, 리프 정점의 개수를 많게하면 점수를 더 받는 문제다. 김동현 군을 제외한 우리나라 대표학생들은 Output Only 문제에서 상당히 적은 점수를 받았다. 불행인지 다행인지 nowruz에서 조금 ..

문제: 공식 홈페이지채점: Yandex 1. prize 1부터 v까지의 수가 적힌 크기가 N인 배열이 있다. 수 1의 갯수는 항상 1개고, 1보다 큰 t에 대해 수 t의 갯수는 수 t-1의 갯수의 제곱보다 많다. ask(i)를 호출하면, i보다 왼쪽에 있으면서 작은 수, i보다 오른쪽에 있으면서 큰 수를 알려준다. 이 때, 적은 횟수로 ask(i)를 호출하여 하나 뿐인 수 1의 위치를 찾는 문제다. 우선 배열에서 가장 많이 등장하는 수, 즉, 가장 큰 수는 등장 빈도가 과반이다. 가장 큰 수가 아닌 수의 최대 갯수는 조건에 따라 472개(1개, 4개, 21개, 446개, ...)다. 첫 번째로 가장 큰 수의 개수를 구하기 위해 최대 473번의 질문을 하여, 가장 큰 수의 위치 중 하나를 찾을 수 있다. ..