E16CN PTIT: Quy Luật

Hiển thị các bài đăng có nhãn Quy Luật. Hiển thị tất cả bài đăng

P173SUMF - ROUND 3F - Hình học lớp 6

Link Sub: http://www.spoj.com/PTIT/problems/P173SUMF/
Người Gửi: Funny

Problem:

Ngày nay có một cậu bé vì tên quá xấu nên buộc phải đổi tên thành Cơm, ngày này năm xưa – lúc Cơm đang học lớp 8, cậu được học một kiến thức mới đó là trung điểm của đoạn thẳng, hồi đó cô giáo cho Cơm 1 bài toán như sau : Cho n điểm trên mặt phẳng A[1], A[2], … A[n] với n là số lẻ. 2 điểm M[i] và M[i-1] sẽ đối xứng với nhau qua A[ (i-1) mod n] (với mọi số tự nhiên i). Hai điểm đối xứng với nhau qua điểm X khi X là trung điểm của đoạn thẳng nối 2 điểm đó. Cho M[0] và số nguyên dương j, tìm điểm M[j].
Input
- Dòng đầu tiên gồm 2 số nguyên n (1 <= n <= 10^5 – n là số lẻ), và số nguyên dương j (1<= n <= 10^18) là chỉ số điểm M[j] cần tìm.
- Dòng thứ 2 chứa 2 số nguyên là tọa độ điểm M[0].
- n dòng sau mỗi dòng gồm 1 cặp số nguyên là tọa độ của điểm A[i] ( i = 1..n) có giá trị tuyệt đối không quá 1000.

Output
- Một dòng duy nhất gồm 2 số nguyên là tọa độ của điểm M[j].

Example:

Input

Output:

14 0

Input

Output:

1995 1995

Solution:

- Bài này đúng như tiêu đề là hình học lớp 6 thôi! Đó là (M[i]_x+M[i-1]_x)/2=A[(i-1)%n]_x; (M[i]_y+M[i-1]_y)/2=A[(i-1)%n]_y;
- Nhưng nếu làm trâu thì chắc chắn sẽ quá time.
-> Mình gợi ý là nó có quy luật nhé ^^! Cứ 2*n lượt thì tọa độ nó lại trở về như ban đầu :v (Không tin thì bạn cứ thử nháp mà xem :D)
-> Vậy thì chỉ cần tính 2*n tọa độ đầu tiên là Ô Sờ Kê.

Code:

C++:

JAVA:

P175SUME - ROUND 5E - Trò chơi với queue

Thứ Sáu, tháng 12 15, 2017 Ad Comment C++ Luyện Tập PTIT SPOJ Quy Luật

Link Sub: http://www.spoj.com/PTIT/problems/P175SUME/
Người Gửi: Dương Lee

Problem:

Do những ngày hè quá nóng bức và nhàm chán nên Tide đã nghĩ ra một trò chơi khá thú vị với queue. Ban đầu trong queue có 5 số 1, 2, 3, 4, 5 với mỗi lượt chơi Tide sẽ xóa phần tử ở đầu queue và cho 2 phần tử đó xuống cuối của queue và cứ tiếp tục cho đến khi Tide cảm thấy mệt và không chơi được nữa.
Ví dụ tại lượt chơi thứ nhất trạng thái của queue là 1, 2, 3 ,4 ,5
Tại lượt chơi thứ 2 trạng thái của queue là 2, 3, 4, 5, 1, 1
Các bạn hãy giúp Tide xác định xem số đầu tiên của queue tại lượt chơi thứ N nhé.
Input
Gồm duy nhất số N (N<=10^9)

Output
Kết quả tìm được.

Example:

Input

Output:

Input

Output:

Solution:

Ở bài này chỉ cần quan tâm đến các thông số số đầu tiên là độ lặp số (Giải thích: mặc dù các dãy số theo quy luật nhưng nó chỉ xét đến các số đầu tiên của dãy nên chỉ cần biết số đầu tiên đó thuộc kiểu dãy nào là được) Kiểu dạng duyệt được nó sẽ giống như: [1 2 3 4 5] [1 1 2 2 3 3 4 4 5 5] [1 1 1 2 2 2 ... -> N=6 -> 1 -> N=1 -> 1 Cấu trúc: (data) begin: 1; end: 5; index: 1 - tương ứng đại diện dãy loại 1: 1 2 3 4 5 begin: 6; end: 15; index: 2 - tương ứng đại diện với dãy loại 2: 1 1 2 2 3 3 4 4 5 5 ... tương tự như vậy... cho đến khi end > 10^9; Sau khi cấu trúc xong và nhập N thì chỉ cần tìm xem N thuộc dãy loại nào? VD: N=8 thuộc [6,15] -> dãy loại 2 (index=2) -> stt = N-6+1 = 3 -> thuộc số thứ 3 của dãy loại 2 -> KQ: 2 (Vì mỗi số sẽ có lượng số là = index chỉ cần xét riêng từng khoảng số là tìm được)

Code:

C++:

JAVA:

P155PROF - ROUND 5F - Dãy số Fibonacci 2

Thứ Bảy, tháng 12 09, 2017 Ad Comment C++ Luyện Tập PTIT SPOJ Quy Luật

Link Sub: http://www.spoj.com/PTIT/problems/P155PROF/
Người Gửi: Dương Lee

Problem:

Bạn được cho 1 dãy số được định nghĩa như sau:

F1 = x; F2 = y; Fi = Fi-1 + Fi+1.

Cho trước x, y. Hãy tính Fn % 1000000007 (109 + 7).

Input

Dòng đầu tiên gồm 2 số x, y (|x|, |y| ≤ 109)..

Dòng thứ 2 gồm số nguyên dương n (1 ≤ n ≤ 2·109).

Output
In ra một số nguyên duy nhất là đáp án của bài toán.

Example:

Input

2 3
3

Output:

Input

0 -1
2

Output:

1000000006

Solution:

Giải thích test 2: F2 = -1, -1 % (1000000007) = 1000000006.
- Quy luật của bài này là cứ 6 số lại lặp lại F_n.
Vậy nên chỉ cần biết quy luật thì độ phức tạp chỉ còn là O(n%6); Chỉ cần chú ý thêm về nến nó là số âm thì cộng thêm 1000000007 là được.

Code:

C++:

JAVA:

BCMATHP - Lũy thừa 2

Thứ Bảy, tháng 12 09, 2017 Ad Comment C++ Luyện Tập PTIT SPOJ Quy Luật

Link Sub: http://www.spoj.com/PTIT/problems/BCMATHP/
Người Gửi: Dương Lee

Problem:

Cho 2 số nguyên A (0 <= A <= 45) and B (1 <= B <= 9)
Bạn phải xác định số nguyên E trong đoạn 1..62. Sao cho:
E là số nguyên nhỏ nhất trong khoảng mà lớn hơn A và có B là chữ số đầu tiên trong biểu diễn lũy thừa 2 mũ E. Nếu không có đáp án, in ra số 0.

Ví dụ, cho A=1 and B=6.
Ta có thể biểu diễn:
E 2^E Chữ số đầu tiên của 2^E
1 2 2

         2          4            4
         3          8            8
         4         16            1
         5         32            3
         6         64            6

Vì vậy, E=6 là đáp án chính xác.

Input
* Dòng 1: 2 số nguyên cách bởi dấu cách: A và B

Output
* Dòng 1: 1 số nguyên E thỏa mãn đề bài. Nếu không tồn tại, in ra 0.

Example:

Input

1 6

Output:

Solution:

Từ E:1->62 có quy luật:
Chữ số cuối của E là: 0 4 7 -> 2^E chữ số cuối là: 1;
Chữ số cuối của E là: 1 8 -> 2^E chữ số cuối là: 2;
Chữ số cuối của E là: 5 -> 2^E chữ số cuối là: 3;
Chữ số cuối của E là: 2 -> 2^E chữ số cuối là: 4;
Chữ số cuối của E là: 9 -> 2^E chữ số cuối là: 5;
Chữ số cuối của E là: 6 -> 2^E chữ số cuối là: 6;

Chữ số cuối của E là: 3 -> 2^E chữ số cuối là: 8;

Ngoài ra có một số TH trong [1,62] là:
46 56 -> 2^E chữ số cuối là: 7;
53 -> 2^E chữ số cuối là: 9;

Code:

C++:

https://ideone.com/IAe7nk


#include <iostream>
using namespace std;

int valueS (int a)
{
    switch (a)
    {
        case 0:
        case 4:
        case 7:
            return 1;
        case 1:
        case 8:
            return 2;
        case 5:
            return 3;
        case 2:
            return 4;
        case 9:
            return 5;
        case 6:
            return 6;
        case 3:
            return 8;
    }
}

int main ()
{
    int A, B;
    cin>>A>>B;
    int kt=0, vS;
    for (int i=A+1; i<=62; i++)
    {
        if (i==46 || i==56) vS=7;
        else if (i==53) vS==9;
        else
        {
            int cs=i%10;
            vS=valueS(cs);
        }
        if (vS==B)
        {
            kt=1;
            cout<<i;
            return 0;
        }
    }
    cout<<"0";
    return 0;
}

E16CN PTIT

P173SUMF - ROUND 3F - Hình học lớp 6

Problem:

Input

3 1 5 5 1000 1000 -1000 1000 3 100

Output:

1995 1995

Solution:

Code:

C++:

JAVA:

P175SUME - ROUND 5E - Trò chơi với queue

Problem:

Input

6

Output:

1

Solution:

Code:

C++:

JAVA:

P155PROF - ROUND 5F - Dãy số Fibonacci 2

Problem:

Input

0 -1 2

Output:

1000000006

Solution:

Code:

C++:

JAVA:

BCMATHP - Lũy thừa 2

Problem:

Solution:

Code:

C++:

JAVA:

E16CN PTIT

P173SUMF - ROUND 3F - Hình học lớp 6

Problem:

Input 3 1 5 5 1000 1000 -1000 1000 3 100 Output: 1995 1995 Solution:

Code:

C++:

JAVA:

P175SUME - ROUND 5E - Trò chơi với queue

Problem:

Input 6 Output: 1 Solution:

Code:

C++:

JAVA:

P155PROF - ROUND 5F - Dãy số Fibonacci 2

Problem:

Input 0 -1 2 Output: 1000000006

Solution:

Code:

C++:

JAVA:

BCMATHP - Lũy thừa 2

Problem:

Solution:

Code:

C++:

JAVA:

Input

3 1 5 5 1000 1000 -1000 1000 3 100

Output:

1995 1995

Solution:

Input

6

Output:

1

Solution:

Input

0 -1 2

Output:

1000000006