Codeforces Round #237 (Div. 2) A~D(二)

#include 
          
           
#include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; long long i,k,n; double a,d,e,l; int main() { scanf("%lf%lf%I64d",&a,&d,&n); for(i=1;i<=n;i++) { l=d*i; k=(long long)(l/a); e=l-k*a; k=k%4; if(k==0) { printf("%.8lf %.8lf\n",e,0.); } else if(k==1) { printf("%.8lf %.8lf\n",a,e); } else if(k==2) { printf("%.8lf %.8lf\n",a-e,a); } else if(k==3) { printf("%.8lf %.8lf\n",0.,a-e); } } return 0; } 
              
             
            
           
          

Valera had an undirected connected graph without self-loops and multiple edges consisting of n vertices. The graph had an interesting property: there were at most k edges adjacent to each of its vertices. For convenience, we will assume that the graph vertices were indexed by integers from 1 to n.

One day Valera counted the shortest distances from one of the graph vertices to all other ones and wrote them out in array d. Thus, element d[i] of the array shows the shortest distance from the vertex Valera chose to vertex number i.

Then something irreparable terrible happened. Valera lost the initial graph. However, he still has the array d. Help him restore the lost graph.

The first line contains two space-separated integers n and k (1 ≤ k n ≤ 105). Number n shows the number of vertices in the original graph. Number k shows that at most k edges were adjacent to each vertex in the original graph.

The second line contains space-separated integers d[1], d[2], ..., d[n] (0 ≤ d[i] n). Number d[i] shows the shortest distance from the vertex Valera chose to the vertex number i.

If Valera made a mistake in his notes and the required graph doesn't exist, print in the first line number -1. Otherwise, in the first line print integer m (0 ≤ m ≤ 106) ― the number of edges in the found graph.

In each of the next m lines print two space-separated integers ai and bi (1 ≤ ai, bi ≤ n; ai ≠ bi), denoting the edge that connects vertices with numbers ai and bi. The graph shouldn't contain self-loops and multiple edges. If there are multiple possible answers, print any of them.

3 2
0 1 1

3
1 2
1 3
3 2

4 2
2 0 1 3

3
1 3
1 4
2 3

3 1
0 0 0

-1

#include 
          
           
#include 
           
             #include 
            
              #include 
             
               #include 
              
                using namespace std; const int maxn=110000; const int INF=0x3f3f3f3f; int n,k,d[maxn],maxd=-INF,cnt[maxn]; vector
               
                 g[maxn]; struct Edge { int to,next; }E[maxn]; int Size,Adj[maxn]; void init() { Size=0; memset(Adj,-1,sizeof(Adj)); memset(cnt,0,sizeof(cnt)); } void Add_Edge(int u,int v) { E[Size].to=v;E[Size].next=Adj[u];Adj[u]=Size++; } int main() { scanf("%d%d",&n,&k); int src=-1,D=0; for(int i=1;i<=n;i++) { scanf("%d",&d[i]); maxd=max(maxd,d[i]); if(d[i]==0) src=i; g[d[i]].push_back(i); } bool flag=true; if(g[0].size()!=1) { puts("-1"); return 0; } for(int i=1;i<=maxd;i++) { if(g[i].size()==0) { flag=false; break; } if(i==1) { if(g[i].size()>k) { flag=false; break; } } else { if((long long int )(g[i].size())>(long long int )(g[i-1].size())*(k-1)) { flag=false; break; } } } if(flag==false) { puts("-1"); return 0; } init(); ///......build...... for(int i=0;i
                
                 
 
                 
 D. Minesweeper 1D time limit per test 2 seconds memory limit per test 512 megabytes input standard input output standard output 
                 
 Game "Minesweeper 1D" is played on a line of squares, the line's height is 1 square, the line's width is n squares. Some of the squares contain bombs. If a square doesn't contain a bomb, then it contains a number from 0 to 2 ― the total number of bombs in adjacent squares.
 
                 
 For example, the correct field to play looks like that: 001*2***101*. The cells that are marked with "*" contain bombs. Note that on the correct field the numbers represent the number of bombs in adjacent cells. For example, field 2* is not correct, because cell with value 2 must have two adjacent cell