SPOJ.com - Problem RGB7614

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.|

RGB7614 - Калькуляторын үйлдлүүд

Сурагчийн зохиосон калькулятор нь дараах 3 үйлдлийг гүйцэтгэх чадвартай.

1. X тоог 1-ээр нэмэгдүүлэх

2. X тоог 2-оор үржүүлэх

3. X тоог 3-аар үржүүлэх

Сурагчийн калькуляторын дээрх 3 үйлдлийн тусламжтайгаар 1-ийн тооноос өгөгдсөн тоо N-ийг гаргахдаа хамгийн цөөндөө хэдэн үйлдэл хийх вэ?

Үйлдлүүдэд дугаарынх нь тоо 1, 2, 3 тоог харгалзуулбал :

1 дэх үйлдэл буюу X тоог 1-ээр нэмэгдүүлсэн бол 1-ийн тоог, 2 дахь үйлдэл буюу X тоог 2-оор үржүүлсэн бол 2-ын тоог, 3 дахь үйлдэлд 3-ын тоог тус тус харгалзуулна гэсэн үг.

Үйлдлийн дарааллыг 1-ээс эхлэн N тоог гаргах хүртэлх үйлдлүүдийг харгалзах кодоор нь нэг мөрөнд зайгүй хэвлэнэ үү.

N тоог гаргах үйлдлийн тоо ижил тохиолдолд үйлдлүүдийн дарааллыг хойноос нь уншихад аль их байгааг нь сонгоно. Жишээг сайн анхаарна уу.

Input

Натурал тоо N. N<10⁶.

Output

Эхний мөрөнд 1-ээс өгөгдсөн N тоог гаргах хамгийн цөөн үйлдлийн тоо.

Хоёр дахь мөрөнд үйлдүүдийн дараалалд харгалзах 1.2.3 тоонууд хоорондоо хоосон зайгүйгээр хэвлэгдэнэ.

Example

Input:
44

Output:
6
331122

Тайлбар : 44 тоог 6 үйлдлийн тусламжтай гаргах 2 боломж байна. 331122, 231312 энэхүү 2 боломжоос сонгохдоо аль

дарааллыг нь хойноос уншихад их тоо байгааг нь сонгоно.
Иймд эхнийхийг нь сонгоно.

Submit solution!

Нэмсэн:	Bataa
Огноо:	2013-02-13
Хугацааны хязгаарлалт:	1s
Эх кодын хэмжээний хязгаарлалт:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Програмчлалын хэлүүд:	ADA95 ASM32 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE

hide comments

2024-02-28 10:13:42
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, s = 0,c, p=0,l;
cin >> n;
int a[n+1], b[n+1];
a[1] = 0;
for(int i = 2; i <= n; i++){
if(i % 3 != 0 && i % 2 != 0){
a[i] = a[i - 1] + 1;
}
if(i % 3 == 0 && i % 2 != 0){
a[i] = min(a[i-1],a[i/3]) + 1;
}
if(i % 3 != 0 && i % 2 == 0){
a[i] = min(a[i-1],a[i/2]) + 1;
}
if(i % 3 == 0 && i % 2 == 0){
c = min(a[i/2],a[i/3]);
a[i] = min(c,a[i-1]) + 1;
}
}
cout << a[n] << endl;
l = n;
while(l > 1){
if(l % 3 == 0 && l % 2 == 0){
if(a[l] - 1 == a[l / 3]){
b[p] = 3;
}
else{
if(a[l] - 1 == a[l / 2]){
b[p] = 2;
}
else{
b[p] = 1;
}
}
}
if(l % 3 == 0 && l % 2 != 0){
if(a[l] - 1 == a[l / 3]){
b[p] = 3;
}
else{
b[p] = 1;
}
}
if(l % 3 != 0 && l % 2 == 0){
if(a[l] - 1 == a[l / 2]){
b[p] = 2;
}
else{
b[p] = 1;
}
}
if(l % 3 != 0 && l % 2 != 0){
b[p] = 1;
}
if(b[p] == 3){
l = l / 3;
}
if(b[p] == 2){
l = l / 2;
}
if(b[p] == 1){
l--;
}
p++;
}
for(int i = p - 1; i >= 0; i--){
cout << b[i];
}
}

2023-12-16 05:53:17
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[1000000], b, d=0, n,c[1000000];
cin >> n;
a[1]=0;
for( int i = 2; i <= n; i++){
if( i % 2 == 0 && i % 3 == 0 ){
// a[i-1] a[i/2] a[i/3]
if(a[i-1]<a[i/2]){
b=a[i-1];
}
else{
b=a[i/2];
}
if(b<a[i/3]){
a[i]=b+1;
}
else{
a[i]=a[i/3]+1;
}
}
if( i % 2 != 0 && i % 3 == 0 ){
// a[i-1] a[i/3]
if(a[i-1]<a[i/3]){
a[i]=a[i-1]+1;
}
else{
a[i]=a[i/3]+1;
}
}
if( i % 2 != 0 && i % 3 != 0){
a[i] = a[i - 1]+ 1;
}
if(i%2==0 && i%3!=0){
if(a[i-1]<a[i/2]){
a[i]=a[i-1]+1;
}
else{
a[i]=a[i/2]+1;
}
}
}
cout<<a[n]<<endl;
int l=n;
while(n!=1){
if(n%2==0 && n%3==0){
if(a[n/3]<=a[n/2] && a[n/3]<=a[n-1]){
c[d]=3;
d++;
}
if(a[n/2]<=a[n-1] && a[n/2]<a[n/3]){
c[d]=2;
d++;
}
if(a[n-1]<a[n/3] && a[n-1]<a[n/2]){
c[d]=1;
d++;
}
if(c[d-1]==1){
n--;
}
if(c[d-1]==2){
n=n/2;
}
if(c[d-1]==3){
n=n/3;
}
}
else if(n%2==0 && n%3!=0){
if(a[n-1]<a[n/2]){
c[d]=1;
n--;
d++;
}
else{
c[d]=2;
n=n/2;
d++;
}
}
else if(n%2!=0 && n%3==0){
if(a[n-1]<a[n/3]){
c[d]=1;
n--;
d++;
}
else{
c[d]=3;
n=n/3;
d++;
}
}
else if(n%2!=0 && n%3!=0){
c[d]=1;
n--;
d++;
}
}
d--;
for(int i=d; i>=0; i--){
cout<<c[i];
}
return 0;
}

2023-11-26 13:02:03
#include<bits/stdc++.h>

using namespace std;
int dp[1000005];
int main()
{
//oyuka_13
int n,i,j;
cin >> n;
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;
for(int i= 4; i<= n; i++)
{
dp[i] = dp[i-1] + 1;
if(i % 2 == 0) dp[i] = min(dp[i],dp[i/2] + 1);
if(i % 3 == 0) dp[i] = min(dp[i],dp[i/3] + 1);
}
cout << dp[n];
return 0;
}

2023-11-21 07:29:16
#include <vector>
#include <iostream>
using namespace std;

int main() {
int n, i, d=0, l;
cin>>n;
l=0;
while(1!=n){
d++;
if(n%3==0){
n=n/3;
l=(l+3)*10;
}else if(n%2==0){
if((n-1)%3==0){
n--;
l=(l+1)*10;
}else{
n=n/2;
l=(l+2)*10;
}
}else {
n--;
l=(l+1)*10;
}
}
l=l/10;
cout<<d<<endl;
cout<<l;
return 0;
}
elooooooooo

2023-11-07 12:53:58
#include <iostream>
#include <string>
using namespace std;

int main() {
string a, b;
int c[1000];

cin >> a >> b;

int n = a.length();

for (int i = 0; i < n; i++) {
if (a[i] == b[i]) {
c[i] = 0;
}
else {
c[i] = 1;
}
cout << c[i];
}

return 0;
}

2023-05-29 03:05:56
i wanna kms

2022-11-20 06:17:43
i need help

2022-11-20 05:45:04
jamal2222

2022-10-25 09:21:14
chiisai dolgoon yahgeed huulaad bgambee pastaa

2022-10-25 09:19:49
ku2 iin javhaa mundag shuu

АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

RGB7614 - Калькуляторын үйлдлүүд

Input

Output

Example