problem 250
Problem Statement
Vasa likes to construct sequences of numbers. If you tell him a positive integer n, he will begin a new sequence by writing the integer n as its first element. He will then repeat the following steps:
- If the last number in his sequence is a prime, he terminates the sequence.
- If he already wrote n elements without finding a prime, he becomes bored and leaves.
- Otherwise, he computes the next element of the sequence as the sum of squares of digits of the last element. For example, 4001 will be followed by 4^2 + 0^2 + 0^2 + 1^2 = 17, and 17 will be followed by 1^2 + 7^2 = 50.
Find out what happens for the given int n. If Vasa eventually becomes bored and leaves, return -1. Otherwise, return the length of the generated sequence.
Definition
- ClassExploringNumbers
- MethodnumberOfSteps
- Parametersint
- Returnsint
- Method signatureint numberOfSteps(int n)
(be sure your method is public)
Limits
- Time limit (s)2.000
- Memory limit (MB)256
Notes
- A prime number is a positive integer with exactly two positive integer divisors: 1 and itself. The first few primes are 2, 3, 5, 7, 11. Note that 1 is not a prime.
Constraints
- n will be between 1 and 10^9, inclusive.
Test cases
-
- n5
-
- n57
-
- n1
-
- n6498501
-
- n989113
-
- n12366
暴力循環一下就行了。再記錄一下目前這個數在之前計算過沒有，如果計算過了那麼久傳回-1
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <map>
using namespace std;
class ExploringNumbers {
public:
int check(int x){
if(x==1)return 0;
for(int i=2;i*i<=x;i++){
if(x%i==0)return 0;
}
return 1;
}
int numberOfSteps(int n) {
map<int,int>mp;
int ans=1;
int m=n;
if(n==1)return -1;
if(check(n))return 1;
int sum;
int mark=0;
while(check(n)==0){
ans++;
sum=0;
mp[n]=1;
while(n>0){
int a=n%10;
n/=10;
sum+=a*a;
}
n=sum;
if(mp[n]||ans>m){
mark=1;break;
}
}
if(mark)return -1;
return ans;
}
}; problem 500
Problem Statement
Vasa is a shopkeeper in the small town Deronje. Currently, there are some items for sale in his store. The price of each item is a positive integer. You are given these prices in the int[] A. Each item has a price tag.
Vasa has just learned that a very rich shopper is going to visit his store. Therefore, Vasa wants to alter some of the price tags to make the items in his store more expensive.
Vasa has a collection of stickers. Each of those stickers contains a single digit between 1 and 9, inclusive. Note that he has no stickers with zeros. You are given the description of Vasa's stickers in the int[] D. For each i between 1 and 9, inclusive, Vasa has D[i-1] stickers with the digit i.
Vasa can take any sticker and use it to replace any digit on any price tag. However, there is no extra room on the price tags, so he cannot add new digits, he can only replace existing ones.
Compute and return the maximum total cost of items in Vasa's store after he applies some (possibly none, possibly all) of his stickers to the current price tags.
Definition
- ClassReplacingDigit
- MethodgetMaximumStockWorth
- Parametersvector<int> , vector<int>
- Returnsint
- Method signatureint getMaximumStockWorth(vector<int> A, vector<int> D)
(be sure your method is public)
Limits
- Time limit (s)2.000
- Memory limit (MB)256
Constraints
- A will contain between 1 and 50 elements, inclusive.
- Each element of A will be between 1 and 10^6, inclusive.
- D will contain exactly 9 elements.
- Each element of D will be between 0 and 10^3, inclusive.
Test cases
-
- A{ 100, 90 }
- D{ 0, 0, 0, 0, 2, 1, 0, 0, 0 }
Returns745
Vasa has two digit stickers with digit 5 written on them, and one digit sticker with digit 6 written on it. There are two items in the shop: one with price 100, and the other one with price 90.
Vasa can use one digit sticker with 5 to replace digit 0 of price tag 90 obtaining a new price of 95 of that item. Then, he can use the remaining stickers 5 and 6 to change the price tag of the other item from 100 to 650. In that case, the worth of his stock would be 650 + 95 = 745.
Note that the same stock worth could be obtained by applying all the three digit stickers to 100 in order to obtain a new price of 655. In that case, the price 90 of the other item would remain unchanged.
-
- A{ 9 }
- D{ 1, 1, 1, 1, 1, 1, 1, 1, 0 }
Returns9
In this example, the maximum stock worth is obtained by leaving the price tag unchanged. Note that Vasa is not required to use all stickers.
-
- A{ 123456 }
- D{ 9, 8, 7, 6, 5, 4, 3, 2, 1 }
-
- A{ 10, 970019, 1976, 10936, 68750, 756309, 37600, 559601, 6750, 76091, 640, 312, 312, 90, 8870 }
- D{ 11, 2, 8, 10, 7, 6, 3, 1, 3 }
-
- A{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
- D{ 111, 111, 111, 111, 111, 111, 111, 111, 111 }
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#define INF 2000000000
#define ll long long
using namespace std;
class ReplacingDigit {
public:
int getMaximumStockWorth(vector<int> A, vector<int> D) {
sort(A.begin(),A.end());
vector<int>v[60];
int n=A.size();
for(int i=0;i<n;i++){
while(A[i]>0){
int a=A[i]%10;
v[i].push_back(a);
A[i]/=10;
}
}
for(int i=D.size()-1;i>=0;i--){
while(D[i]>0){
int mark=0;
for(int t=7;t>=1;t--){
int ans=INF;
int id;
for(int j=0;j<n;j++){
if(v[j].size()>=t){
if(v[j][t-1]<ans){
ans=v[j][t-1];
id=j;
}
}
}
if(ans<i+1){
v[id][t-1]=i+1;
D[i]--;
mark=1;
break;
}
}
if(mark==0)break;
}
}
ll sum=0;
for(int i=0;i<n;i++){
int t=1;
for(int j=0;j<v[i].size();j++){
sum+=t*v[i][j];
t*=10;
}
}
return sum;
}
}; 理論上來說做了2題.坑爹的網絡，第二題沒有送出上..
轉載于:https://www.cnblogs.com/pk28/p/5388430.html