trang chủ / đề bài / icpc20_reg_j

Dãy tung hứng

Đề bài

Mô tả

Dãy tung hứng là một dãy số nguyên gồm n phần tử, được định nghĩa như sau:

  • a1=1,
  • Với mọi i≥1:
    • Nếu ai≤i thì ai+1=ai+i,
    • Nếu ai>i thì ai+1=ai−i.

Sắp xếp dãy tung hứng theo thứ tự không giảm. Số thứ m là bao nhiêu?

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t: số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên n và m.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên: số thứ m của dãy tung hứng n phần tử sau khi sắp xếp.

Ràng buộc

  • 1≤t≤104.
  • 1≤m≤n≤1018.

Ví dụ

Input Output Giải thích
3
6 1
6 2
6 6
1
1
10
Với n=6, dãy tung hứng là 1,2,4,1,5,10. Sau khi sắp xếp ta được 1,1,2,4,5,10.
2
13 7
4 3
4
2
Với n=13, dãy là 1,2,4,1,5,10,4,11,3,12,2,13,1; sau khi sắp xếp là 1,1,1,2,2,3,4,4,5,10,11,12,13, số thứ 7 là 4; với n=4, dãy sắp xếp là 1,1,2,4 nên số thứ 3 là 2.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0