cantor 시계 and nyoj 85 재 미 있 는 숫자

재 미 있 는 숫자
시간 제한:
3000 ms  |  메모리 제한:
65535 KB
난이도:
2
묘사 하 다.
점 수 를 아래 의 방법 에 따라 하나의 수표 로 배열 하 다.
1/1 1/2 1/3 1/4.....
2/1 2/2 2/3....
3/1 3/2 ....
4/1..... .........
우 리 는 z 자형 방법 으로 표 의 모든 번 호 를 주 었 다.특정 방법: 첫 번 째 는 1 / 1 이 고 그 다음은 1 / 2, 2 / 1, 3 / 1, 2 / 2, 1 / 3, 1 / 4, 2 / 3...프로 그래 밍 입력 항목 번호 N (1 < = N < = 100000), 출력 표 의 N 번 째 항목.
입력
첫 번 째 줄 에는 정수 m (0 < m < = 10) 가 있 는데 m 조 테스트 데이터 가 있 음 을 나타 낸다.
그 다음 에 m 줄 이 있 고 줄 마다 정수 N 이 있 습 니 다.
출력
출력 표 의 N 번 째 항목
샘플 입력
4314712345

샘플 출력
2/12/41/459/99

근원
고전 제목
업로드 자
저장 성
알고리즘 사고방식:
먼저 문제 가 어떤 규칙 에 따라 배열 되 는 지 알 아야 한다. 먼저 사선 을 누 른 다음 에 하나의 사선 이 위 에서 아래로, 다른 사선 이 아래 에서 위로 교차 하 는 것 이다.
그 다음 에 i 조 사선 을 분석 하면 i 개의 수가 있 고 앞의 i 조 사선 은 모두 S (k) = 1 + 2 + 3 + · · + k = k (k + 1) / 2 개의 수가 있다.
n 은 어느 사선 에 있 습 니까?n < = S (k) 를 최소 정수 k 로 찾 으 면 n 은 k 조 사선 의 두 번 째 또는 마지막 S (k) - n + 1 개의 요소 입 니 다.
k 조 사선 의 i 번 째 요 소 는 i / (k + 1 - i) 이 고 마지막 i 번 째 요 소 는 (k + 1 - i) / i 이다.
#include<stdio.h>
#include<math.h>
int main()
{
    int n;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int k=1;
        int s=0;
        while(1)
        {
            s+=k;
            k++;
            if(s>=n)
                break;
        }
        if(k%2==0)
            printf("%d/%d
",s-n+1,k-(s-n+1)); else printf("%d/%d
",k-(s-n+1),s-n+1); } return 0; }

좋은 웹페이지 즐겨찾기