Codeforces Round #270 A. Design Tutorial: Learn from Math time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
One way to create a task is to learn from math. You can generate some random math statement or modify some theorems to get something new and build a new task from that.
For example, there is a statement called the "Goldbach's conjecture". It says: "each even number no less than four can be expressed as the sum of two primes". Let's modify it. How about a statement like that: "each integer no less than 12 can be expressed as the sum of two composite numbers." Not like the Goldbach's conjecture, I can prove this theorem.
You are given an integer n no less than 12, express it as a sum of two composite numbers.
Input
The only line contains an integer n (12?≤?n?≤?106).
Output
Output two composite integers x and y (1?
x,?y?
n) such that x?+?y?=?n. If there are multiple solutions, you can output any of them.
Sample test(s) input
12
output
4 8
input
15
output
6 9
input
23
output
8 15
input
1000000
output
500000 500000
Note
In the first example, 12 = 4 + 8 and both 4, 8 are composite numbers. You can output "6 6" or "8 4" as well.
In the second example, 15 = 6 + 9. Note that you can't output "1 14" because 1 is not a composite number.
#include
#include
#include
#include
using namespace std; bool isp[1001000]; void get_prime() { isp[1]=isp[0]=true; for(int i=2;i<=1000010;i++) { if(isp[i]==false) for(int j=i*2;j<=1000010;j+=i) isp[j]=true; } } int main() { get_prime(); int n; scanf("%d",&n); int x,y; for(int i=2;i<=n;i++) { if(isp[i]==true&&isp[n-i]==true) { printf("%d %d\n",i,n-i); return 0; } } return 0; }
B. Design Tutorial: Learn from Life time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
One way to create a task is to learn from life. You can choose some experience in real life, formalize it and then you will get a new task.
Let's think about a scene in real life: there are lots of people waiting in front of the elevator, each person wants to go to a certain floor. We can formalize it in the following way. We have n people standing on the first floor, the i-th person wants to go to the fi-th floor. Unfortunately, there is only one elevator and its capacity equal to k (that is at most k people can use it simultaneously). Initially the elevator is located on the first floor. The elevator needs |a?-?b| seconds to move from the a-th floor to the b-th floor (we don't count the time the people need to get on and off the elevator).
What is the minimal number of seconds that is needed to transport all the people to the corresponding floors and then return the elevator to the first floor?
Input
The first line contains two integers n and k (1?≤?n,?k?≤?2000) ― the number of people and the maximal capacity of the elevator.
The next line contains n integers: f1,?f2,?...,?fn (2?≤?fi?≤?2000), where fi denotes the target floor of the i-th person.
Output
Output a single integer ― the minimal time needed to achieve the goal.
Sample test(s) input
3 2
2 3 4
output
8
input
4 2
50 100 50 100
output
296
input
10 3
2 2 2 2 2 2 2 2 2 2
output
8
Note
In first sample, an optimal solution is:
- The elevator takes up person #1 and person #2.
- It goes to the 2nd floor.
- Both people go out of the elevator.
- The elevator goes back to the 1st floor.
- Then the elevator takes up person #3.
- And it goes to the 2nd floor.
- It picks up person #2.
- Then it goes to the 3rd floor.
- Person #2 goes out.
- Then it goes to the 4th floor, where person #3 goes out.
- The elevator goes back to the 1st floor.
#include
#include
#include
#include
using namespace std; int n,k; int f[2200]; int all[2200]; int main() { scanf("%d%d",&n,&k); for(int i=0;i
=1;(all[i]==0)?i--:i+=0) { if(all[i]) { if(now==0