Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
Nộp bài Các bài nộp Làm tốt nhất PDF Về danh sách bài

P202PROC - GƯƠNG KIA NGỰ Ở TRÊN TƯỜNG 2

Một ngày như thường lệ, Oppa hỏi Unnie rằng: có 10 vị khách, mỗi vị khách có 10 chiếc túi, mỗi chiếc túi có 3 ngăn, mỗi ngăn có 7 cái khăn. Hỏi tất cả có bao nhiêu đối tượng? Sau vài phút tính nhẩm, Unnie chốt là có 2510 đối tượng bao gồm 10 vị khách, 100 chiếc túi, 300 ngăn, 2100 cái khăn. Xời quá dễ.

Oppa thấy thế bèn hỏi với 100 đối tượng thì mỗi đối tượng có số lượng bao nhiêu, với số loại đối tượng là nhiều nhất có thể và mỗi đối tượng có số lượng nhiều hơn 1?

Unnie sau khi trả lời không được bèn quay ra dọa cắt cơm tối của Oppa. Oppa cũng không biết trả lời như thế nào nên nhờ các bạn giúp nha.

INPUT:

Dòng đầu chứa số nguyên n là số lượng đối tượng ( 1 ≤ n ≤ 10^9 )

OUTPUT:

Dòng thứ nhất là số lượng đối tượng. Dòng thứ hai là số lượng của từng đối tượng.

INPUT

OUTPUT

5

1

5

 

INPUT

OUTPUT

100

4

2 7 2 2

 

INPUT

OUTPUT

2510

9

2 2 2 2 5 2 2 2 2
Submit solution!
Được gửi lên bởi:adm
Ngày:2020-08-22
Thời gian chạy:1s
Giới hạn mã nguồn:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM64 CPP CPP14 JAVA PYTHON PYTHON3
hide comments
2020-09-02 16:31:01
code mình đây cho dễ hình dung
#include <bits/stdc++.h>
using namespace std;
vector <int > prime;
void init(){
for(int i=0;i<=999999999;i++){
prime.push_back(0);
}
}
void primeFilter(){
for(int i=2;i<=999999999;i++){
if(prime[i]==0){
int j=i+i;
while(j<=999999999){
prime[j]=1;
j+=i;
}
}
}
}

long long smallestPrime(int x){
for(int i=2;i<=x;i++){
if(x%i==0&&prime[i]==0){
return i;
}
}
}
int main(){
int maxObject=0;
int x;
cin>>x;
x++;
init();
vector <int > res;
while(x>1){
maxObject++;
int y=smallestPrime(x-1);
x=(x-1)/y;
res.push_back(y);
}
cout<<maxObject<<endl;
for(int i=0;i<res.size();i++){
cout<<res[i]<<" ";
}
return 0;
}ư
2020-09-02 16:28:16
Well , mình vô tình tìm thấy bài này và bắt tay vào làm thì bị quá thời gian . Mình hơi kém CTDL và GT nên tạm thời gọi là dựa trên giải thuật tham lam vậy ( sai thì mn đính chính giúp nhé <3)
Cách nghĩ của mình về bài này :
- giả sử có n loại đối tượng . Chúng ta gọi số đối tượng của loại đối tượng thứ j có thể chứa được bởi 1 đối tượng thứ j-1 là a[j] . Như ví dụ trong bài thì có 4 loại vật thể : Khách - Túi - Ngăn - Khăn . Trong đó ta có 10 Khách ,1 Khách có 10 túi , 1 Túi có 3 Ngăn , 1 Ngăn có 7 khăn. Vậy a[1] - a[2] - a[3] - a[4] lần lượt là : 10 - 10 -3 -7 . (mình nếu ví dụ để dễ hình dung về tổng quát cho n loại đối tượng )
- Theo cách ghi quy ước như trên : n đối tượng tương ứng với a[1] - a[2] - a[3] - a[4] - ..... - a[n] => tổng số đối tượng là : a[1] đối tượng loại 1 + a[1]*a[2] đối tượng loại 2 +a[1]*a[2]*a[3] đối tượng loại 3 + ... + a[1] * a[2] * a[3] *....* a[n] đối tượng loại n .
Tổng đối tượng = a[1] + a[1]*a[2] +a[1]*a[2]*a[3]+ ... + a[1] * a[2] *a[3] *...*a[n] ( phân tích đa thức thành nhân tử )
= a[1] * { a[2] *[ ...*(a[n] +1) +1 ] +1 }
tổng số đối tượng đã được cho trước => để số loại đối tượng lớn nhất có thể => n max => a[1] - a[2] -a[3] - .... - a[n] từng cái phải min ( có thể hiểu đơn giản là nếu số ngoài ngoặc càng bé thì trong ngoặc càng to => càng có thể có nhiều ngoặc phía trong hơn => càng nhiều loại đối tượng )
các số a[j] với j thuộc đoạn [1,n] mà mình chọn là số nguyên tố nhỏ nhất mà tích chia hết cho nó : ( bởi lẽ nếu là hợp số thì có thể tách thành tích các số nhỏ hơn => vi phạm câu trên mình đã nói )
ví dụ trên input:
5= 5*1
100 = 2*(7*(2*(2+1)+1)+1)
2510=2 *(2 *(2 *(2 *(5 *(2* ( 2*( 2 *(2+1)+1)+1 )+1 )+1) +1) +1 ) +1 )
thuật toán như sau:
nhập vào số đối tượng là x ; ( step 1)
x= x+1 (step 2)
tính số nguyên tố nhỏ nhất prime mà x-1 chia hết . nếu x==1 thì ngừng(step 3)
ghi nhớ số đó vào 1 vector và biến đếm số loại đối tượng cộng thêm 1;(step 4)
x=(x-1)/prime; (step 5)
quay lại step 3 (step 6)
in ra số loại đối tượng và mỗi loại đối tượng có thể được chứa bao nhiêu bởi loại đối tượng phía trước (step 7)
bài này mình bị TLE :( có thể là do hàm kiểm tra nguyên tố bị quá time hoặc là do thuật toán không phù hợp với bộ test .
bài này có rất ít người submit . và có thể là comment này có thể được đọc sau 5 - 10 năm gì đó . Cơ mà mình vẫn chia sẻ chút ý tưởng nho nhỏ này vậy thôi :))))


Last edit: 2020-09-02 16:34:29
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.