2017-C language group B
1. Shopping list
Xiao Ming has just found a job. The boss is very nice, but the boss's wife loves shopping. When the boss is busy, he often asks Xiao Ming to help him go shopping in the mall. Xiao Ming is very bored, but it's hard to refuse.
No, XX big promotion is coming again! The boss's wife issued a long shopping list with discounts.
Xiao Ming also has a quirk. As a last resort, he never swipes his card and gets it in cash.
Now Xiao Ming is very upset. Please help him calculate how much cash he needs to withdraw from the ATM to finish this shopping.
The ATM can only provide 100 yuan notes. Xiao Ming wants to withdraw as little cash as possible. It's enough.
Your task is to calculate how much cash Xiao Ming needs to withdraw at least.
The following is a troublesome shopping list. In order to protect privacy, the item name is hidden
-------------------- **** 180.90 88 fracture **** 10.25 65 fracture **** 56.14 9 fracture **** 104.65 9 fracture **** 100.30 88 fracture **** 297.15 50% Off **** 26.75 65 fracture **** 130.62 50% Off **** 240.28 58 fracture **** 270.62 8 fracture **** 115.87 88 fracture **** 247.34 95 fracture **** 73.21 9 fracture **** 101.00 50% Off **** 79.54 50% Off **** 278.44 7 fracture **** 199.26 50% Off **** 12.97 9 fracture **** 166.30 78 fracture **** 125.50 58 fracture **** 84.98 9 fracture **** 113.35 68 fracture **** 166.57 50% Off **** 42.56 9 fracture **** 81.90 95 fracture **** 131.78 8 fracture **** 255.89 78 fracture **** 109.17 9 fracture **** 146.69 68 fracture **** 139.33 65 fracture **** 141.16 78 fracture **** 154.74 8 fracture **** 59.42 8 fracture **** 85.44 68 fracture **** 293.70 88 fracture **** 261.79 65 fracture **** 11.30 88 fracture **** 268.27 58 fracture **** 128.29 88 fracture **** 251.03 8 fracture **** 208.39 75 fracture **** 128.88 75 fracture **** 62.06 9 fracture **** 225.87 75 fracture **** 12.89 75 fracture **** 34.28 75 fracture **** 62.16 58 fracture **** 129.12 50% Off **** 218.37 50% Off **** 289.69 8 fracture -------------------- 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152
It should be noted that 88% discount refers to 88% of the bid price, while 80% discount refers to 80%, and so on.
In particular, the half price is calculated at 50%.
Please submit the amount that Xiao Ming wants to withdraw from the ATM. The unit is yuan.
The answer is an integer, similar to 4300. The end must be 00. Don't fill in any redundant content.
Special reminder: you are not allowed to bring calculators into the site or turn on your mobile phone.
Idea:
1. Directly import the data into excel and use the summation formula in Excel to sum and conclude the problem. It is recommended to use Excel to conclude the problem, which is relatively easy to solve
2. Use code to answer, but when entering data, you should consider formatting the data, so as to better answer
answer:
5200
2. Arithmetic prime sequence
2, 3, 5, 7, 11, 13,... Are prime sequences.
Similar: 7,37,67,97127157 such an arithmetic sequence composed entirely of prime numbers is called arithmetic prime sequence.
The upper series has a tolerance of 30 and a length of 6.
In 2004, green worked with Chinese Tao Zhehuan to prove that there is a prime arithmetic sequence of arbitrary length.
This is an amazing achievement in the field of number theory!
Based on this theory, please search with confidence with the help of your computer:
What is the minimum tolerance value of an arithmetic prime sequence with a length of 10?
Note: what needs to be submitted is an integer. Do not fill in any redundant content and explanatory text.
Idea:
1. Violent enumeration method: first list all prime numbers, then list tolerance, and finally list the total number
code:
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long ll
set<int>all
bool isPrime(ll t){ // Judge whether it is prime
for(int i=2;i<t/2;i++){
if(t%i==0)
return false;
}
return true;
}
int f(ll a[],ing n){ // List all possible prime ministers, tolerances and numbers
for(int i=0;i<n;i++){
ll frist = a[i];
for(int delta = 1;delta < a[n-1]-frist;delta++){
int m = frist;
for(int j = 1;j<10;j++){
m+=delta;
if((all.find(m)==all.end())) // Judge that m is not prime
break;
if(m > a[n-1]) break;
if(j==9) // Description: 10 items have been found
return delta;
}
}
}
return -1;
}
const int N = 5000;
ll a[N];
int main(){
a[0]=2;
a[1]=3;
all.insert(2);
all.insert(3);
int index = 2;
ll t = 5;
while(index < N){
if(isPrime(t)){
a[index++] = t;
all.insert(t);
}
t++;
}
cout << f(a,N) << endl;
return 0;
}
answer:
210
3. Bearing calculation
A batch of precious metal raw materials are neatly stacked in the high-tech laboratory of Planet X.
The shape and size of each metal raw material are exactly the same, but the weight is different.
Metal materials are strictly stacked into pyramids.
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
1234567891011121314151617181920212223242526
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
The number represents the weight of the metal block (larger unit of measurement).
The X on the bottom layer represents 30 extremely high-precision electronic scales.
Assuming that the weight of each raw material falls on the two metal blocks below very accurately,
Finally, the weight of all metal blocks is strictly and accurately distributed on the bottom electronic scale.
The unit of measurement of the electronic scale is very small, so the number displayed is very large.
The staff found that the indication of the electronic scale with the smallest reading was 2086458231
Please figure out: what is the indication of the electronic scale with the largest reading?
Note: what needs to be submitted is an integer. Do not fill in any redundant content.
Idea:
For the first number, divide it by 2 from the top to the bottom, and finally judge the multiple relationship of the relative data according to a certain multiple.
code:
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll arr[30][30];
int main()
{
ll factor =1;
for(int i=0;i<30;i++)
{
factor<<=1;
}
for(int i=0;i<29;i++) // Enter data in sequence
{
for(int j=0;j<=i;j++)
{
int a;
scanf("%d",&a);
arr[i][j]=a*factor;
}
}
for(int i=0;i<29;++i)
{
for(int j=0;j<=i;++j)
{
ll temp = arr[i][j]/2;
arr[i+1][j]+=temp;
arr[i+1][j+1]+=temp;
}
}
sort(arr[29],arr[29]+30);
cout<<arr[29][29]/2;//Here is the number of digits that have been calculated, which is about 2 ^ 29th power, so it needs / 2
return 0;
}
4. Grid segmentation
6x6 square, cut into two parts along the edge of the grid.
The shape of these two parts is required to be exactly the same.
As shown in the figure: P1 png, p2. png, p3. PNG is a feasible segmentation method.
Trial calculation:
How many different segmentation methods are there, including these three segmentation methods.
Note: rotational symmetry belongs to the same segmentation method.
Please submit this integer and do not fill in any superfluous content or explanatory text.
code:
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int mp[8][8]; //Search 0 ~ 6 by vertex, a total of 7 -- a two-dimensional array of 7x7
int vis[8][8];
int mov[4][2]={1,0,-1,0,0,1,0,-1};
int ans;
void dfs(int x,int y){
if(x==0||x==6||y==0||y==6) {//Unqualified exit
ans++;
return;
}
for(int i=0;i<4;i++){
int xx=x+mov[i][0];
int yy=y+mov[i][1];
if(!vis[xx][yy]){ //Only one condition is sufficient
vis[xx][yy]=1;
vis[6-xx][6-yy]=1;
dfs(xx,yy);
vis[xx][yy]=0;
vis[6-xx][6-yy]=0;
}
}
}
int main() {
memset(mp,0,sizeof mp); // Reset defined array
memset(vis,0,sizeof vis);
vis[3][3]=1;//Be sure to remember to mark!!!
dfs(3,3);
cout<<ans/4;
return 0;
5. Take digit
There are many ways to find the k-th digit of an integer.
The following method is one.
//Find the digit length when x is expressed in decimal system
int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
//Take the k-th digit of x
int f(int x, int k){
if(len(x)-k==0) return x%10;
return f(x/10,k); // Fill in the blanks
}
int main()
{
int x = 23574;
printf("%d\n", f(x,3));
return 0;
}
Idea:
You can use the recursive method to calculate the number of digits. If the length at the beginning is equal to the number of digits, you can directly calculate the number of the remainder of 10. If not, keep the high order and remove the low order, and use the recursive method to calculate.
6. Maximum common substring
The maximum common substring length is:
Find the maximum length that can be matched in all substrings of two strings.
For example: "abcdkkk" and "baabcddabc",
The longest common substring that can be found is "abcd", so the maximum common substring length is 4.
The following program is solved by matrix method, which is a more effective solution for the case of small string size.
Please analyze the idea of this solution and complete the missing code in the underlined part.
Idea:
Using the simple list method, list the previous one of the empty position, and then deduce the result
code:
#include <stdio.h>
#include <string.h>
#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;
memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = a[i-1][j-1]+1; //Fill in the blanks
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return 0;
}
7. Date issue
Xiao Ming is sorting out a batch of historical documents. Many dates appear in these historical documents. Xiao Ming knows that these dates are from January 1, 1960 to December 31, 2059. What bothers Xiao Ming is that the formats of these dates are very different, including year / month / day, month / day / year and day / month / year. What's more troublesome is that the first two digits of the year are omitted, so that there are many possible dates corresponding to a date in the literature.
For example, 02 / 03 / 04 may be March 4, 2002, February 3, 2004 or March 2, 2004.
Given a date in the literature, can you help Xiao Ming judge which possible dates correspond to it?
input
----
A date in the format "AA/BB/CC". (0 <= A, B, C <= 9)
output
----
Output several different dates, one line for each date, in the format of "yyyy MM DD". Multiple dates are arranged from morning to night.
sample input
----
02/03/04
sample output
----
2002-03-04
2004-02-03
2004-03-02
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Idea:
According to the input of rules and regulations, it is necessary to consider whether it is a leap year to judge the three possible situations.
code:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
struct node {
int yyyy,mm,dd;
} p[100];
int a[13]= {0,31,28,31,30,31,30,31,31,30,31,30,31};
int cnt=0;
bool judge(int x) {
if(x%400==0||(x%100!=0&&x%4==0)) return true;
return false;
}
void check(int x,int y,int z,int add) {
if(judge(x)) a[2]=29;
else a[2]=28;
if(z>0&&z<=a[y])
p[cnt].yyyy=x+add,p[cnt].mm=y,p[cnt++].dd=z;
}
void deal(int x,int y,int z) {
if((x+1900>=1960)&&(y<=12&&y>0)) check(x,y,z,1900);
if((x+2000<=2059)&&(y<=12&&y>0)) check(x,y,z,2000);
}
bool cmp(node a,node b) {
if(a.yyyy!=b.yyyy) return a.yyyy<b.yyyy;
else if(a.mm!=b.mm) return a.mm<b.mm;
else if(a.dd!=b.dd) return a.dd<b.dd;
}
int main() {
int x,y,z;
scanf("%d/%d/%d",&x,&y,&z);
deal(x,y,z);
deal(z,x,y);
deal(z,y,x);
sort(p,p+cnt,cmp);
printf("%d-%02d-%02d\n",p[0].yyyy,p[0].mm,p[0].dd);
for(int i=1; i<cnt; i++){
if(p[i].yyyy==p[i-1].yyyy&&p[i].mm==p[i-1].mm&&p[i].dd==p[i-1].dd) continue;
printf("%d-%02d-%02d\n",p[i].yyyy,p[i].mm,p[i].dd);
}
return 0;
8. Make up the number of steamed stuffed buns
Xiao Ming eats breakfast at a steamed stuffed bun shop almost every morning. He found that this steamed stuffed bun shop has N kinds of steamers, of which the i steamer can just put Ai steamed stuffed buns. Each kind of steamer has many steamers, which can be regarded as infinite steamers.
Whenever a customer wants to buy X steamed stuffed buns, the uncle selling steamed stuffed buns will quickly select several cages of steamed stuffed buns, so that there are exactly X steamed stuffed buns in these cages. For example, there are three kinds of steamers, which can put 3, 4 and 5 steamed buns respectively. When customers want to buy 11 steamed stuffed buns, uncle will choose 2 cages of 3 and 1 cage of 5 (or 1 cage of 3 and 2 cages of 4).
Of course, sometimes uncle baozi can't figure out the quantity customers want to buy anyway. For example, there are three kinds of steamers, which can put 4, 5 and 6 steamed buns respectively. When customers want to buy seven steamed stuffed buns, uncle can't come up with it.
Xiao Ming wants to know how many kinds of numbers are there that uncle baozi can't figure out.
input
----
The first line contains an integer n. (1 <= N <= 100)
Each of the following N lines contains an integer AI. (1 <= Ai <= 100)
output
----
An integer represents the answer. If there are infinite numbers that cannot be summed up, output INF.
For example,
Input:
2
4
5
The program should output:
6
Another example is,
Input:
2
4
6
The program should output:
INF
Example explanation:
For example 1, the numbers that cannot be rounded up include: 1, 2, 3, 6, 7 and 11.
For example 2, none of the odd numbers can be summed up, so there are infinite numbers.
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please do not print as required.
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Idea:
Dynamic route planning,
code:
#include<cstdio>
#include<iostream>
#include<cstring>
int a[105];
int vis[100*100+5];
using namespace std;
int gcd(int a,int b) {
return b?gcd(b,a%b):a;
}
int main() {
int n,g;
scanf("%d%d",&n,&a[0]);
g=a[0];
for(int i=1; i<n; i++) {
scanf("%d",&a[i]);
g=gcd(g,a[i]);
}
if(g!=1) { //If the common factor of these numbers is not 1, there are infinite numbers that cannot be represented by these numbers
cout<<"INF\n";
return 0;
}
vis[0]=1;
for(int i=0; i<n; i++) //Traverse a[i] one by one
for(int j=0; j+a[i]<100*100+5;j++)//For any marked number, its + a[i]*k can still be expressed
if(vis[j]) vis[j+a[i]]=1;
int ans=0;
for(int i=0;i<100*100+5;i++)
if(vis[i]==0) ans++;
cout<<ans;
return 0;
}
9. Divide chocolate
On children's day, K children visited Xiao Ming's house. Xiao Ming took out his precious chocolate to entertain the children.
Xiaoming has a total of N chocolates, of which the i is a rectangle composed of Hi x Wi squares.
To be fair, Xiao Ming needs to cut K chocolates out of the N chocolates and give them to the children. The cut chocolate needs to meet:
\1. The shape is a square and the side length is an integer
\2. Same size
For example, a piece of 6x5 chocolate can cut 6 pieces of 2x2 chocolate or 2 pieces of 3x3 chocolate.
Of course, children all want to get as much chocolate as possible. Can you help little Hi calculate the maximum side length?
input
The first line contains two integers n and K. (1 <= N, K <= 100000)
Each of the following N lines contains two integers hi and wi. (1 <= Hi, Wi <= 100000)
Input to ensure that each child can get at least one 1x1 chocolate.
output
Output the maximum possible side length of the cut square chocolate.
Sample input:
2 10
6 5
5 6
Sample output:
2
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 1000ms
Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly \include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Idea:
The dichotomy method is used to solve this problem;
code:
10. Title: k-fold interval
Given a sequence with length N, A1, A2,... AN, if the sum of a continuous subsequence Ai, Ai+1,... AJ (I < = J) is a multiple of K, we call this interval [i, j] a k-fold interval.
Can you find out how many K-times intervals there are in the sequence?
input
-----
The first line contains two integers n and K. (1 <= N, K <= 100000)
Each of the following N lines contains an integer AI. (1 <= Ai <= 100000)
output
-----
Output an integer representing the number of K-times intervals.
For example,
Input:
5 2
1
2
3
4
5
The program should output:
6
Resource agreement:
Peak memory consumption (including virtual machine) < 256M
CPU consumption < 2000ms
Please output in strict accordance with the requirements, and do not print superfluous contents like "please input...".
be careful:
The main function needs to return 0;
Only ANSI C/ANSI C + + standards are used;
Do not call special functions that depend on the compilation environment or operating system.
All dependent functions must be explicitly #include in the source file
Common header files cannot be omitted through engineering settings.
When submitting programs, pay attention to selecting the desired language type and compiler type.
Idea:
The method adopted is to use an array to take the remainder of the first I and sum[i], sum[i]%k. those with the same remainder can be put together. In this section, the number with the same remainder can be subtracted to meet the conditions. cnt array can be used to record the number with the same remainder
code:
- #include
- #include
- #define Size 100005
- using namespace std;
- int n,k;
- int cnt[Size],sum[Size];
- int main() {
- int x,ans=0;
- scanf("%d%d",&n,&k);
- for(int i=1; i<=n; i++) {
- scanf("%d",&x);
- sum[i]=(sum[i-1]+x)%k; // After modulo K, the same number is subtracted to be 0, which meets the requirements
- ans+=cnt[sum[i]];
- cnt[sum[i]]++; // Judge and compare first and then accumulate
- }
- cout<<ans+cnt[0];// Add the number whose modulus k is equal to 0 - it's done!
- return 0;