I have solved this problem by using an easy greedy algorithm.

MAIN: you need to use an idea of 2 pointers(of course you need to sort array) and take the rightest segment. Left part of segment need to be <= x(another pointer)

The solution below:

void solve() {
    int m;
    cin >> m;
    vector< pair<int, int> > pi;
    int a, b;
    cin >> a >> b;
    while (a || b) {
        pi.pb({a, b});
        cin >> a >> b;
    }
    sort(all(pi));
    int cnt = 0, j = 0;
    vector< pair<int, int> > ans;
    j = 0;
    int x = 0;
    for (; j < sz(pi) && x < m; j++) {
        int k = j;
        int mx = x;
        pair<int, int> par = {-INF, -INF};
        while (k < sz(pi) && pi[k].ff <= x) {
            if (mx < pi[k].ss) {
                mx = pi[k].ss;
                par = pi[k];
            }
            k++;
        }
        if (par.ff == -INF) {
            cout << "No solution\n";
            return;
        }
        x = mx;
        ans.pb(par);
        if (k > j)
            j = k - 1;
    }
    if (x < m) {
        cout << "No solution\n";
        return;
    }
    cout << sz(ans) << '\n';
    for (auto &i : ans) {
        cout << i.ff << ' ' << i.ss << '\n';
    }
}

I dont understand why difficulty is 121, i think it's easy problem

I had a hard time with this, so hopefully I will save your time. Read input like this:

int n; cin >> n;
string t;
getline(cin, t); // Necessary to process end of first line (nothing after n)
....
// Now keep getting each line with getline(cin, t)

Hints:

1. No sorting. It's useless. Quiqsort - too much memory, Bublesort - too long time.

2. We just need a number that is more than n/2. It always exists.

3. Read values step by step, remember the 'candidate' answer and counter increase or decrease it.

e.g:

3->3 cnt=0+1=1

3->3 cnt=1+1=2

2->3 cnt=2-1=1

2->3 cnt=1-1=0

3->3 cnt=0+1=1

Note 1:

e.g.

5

3

3

2

2

6

My program's answer is 6, but such a case never occurs (!).

"He knows exactly that more than half banknotes have the same value."

Note 2:

C# - "Memory limit exceeded 21"

use this:

    if (i % 1000 == 0)

       GC.Collect();

Regards

Edited by author 12.01.2022 20:54

using System;

namespace Timus
{
    class Program
    {
        static void Main()
        {
            string nums = Console.ReadLine();
            int a = Convert.ToInt32(nums.Substring(0, 1));
            int b = Convert.ToInt32(nums.Substring(2, 1));
            int c = a + b;
            Console.WriteLine(c);
        }
    }
}

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main ()
{    long long n;
    while (cin>>n)
{
    cout<<setprecision(4)<<fixed<<sqrt(n)<<endl;
}
return 0;
}

Edited by author 12.11.2017 17:07

This is my code!!!
#include<iostream>
#include<string>
using namespace std;
int main() {
 char s;
 int count = 0;
 while (cin >> s) {
    if ((s=='a')||
        (s=='d')||
        (s=='g')||
        (s=='j')||
        (s=='m')||
        (s=='p')||
        (s=='s')||
        (s=='v')||
        (s=='y')||
        (s=='.')||
        (s==' ')) {count+=1;}
    if ((s=='b')||
        (s=='e')||
        (s=='h')||
        (s=='k')||
        (s=='n')||
        (s=='q')||
        (s=='t')||
        (s=='w')||
        (s=='z')||
        (s==',')) {count+=2;}
    if ((s=='c')||
        (s=='f')||
        (s=='i')||
        (s=='l')||
        (s=='o')||
        (s=='r')||
        (s=='u')||
        (s=='x')||
        (s=='!')) {count+=3;}
 }
 cout << count;
system("pause");
 return 0;
}

Soln accepted but time is .156 how to reduce to atleast 0.078 and also how to reduce memory usuage?
import java.util.*;
import java.io.*;
public class prob1264{
public static void main(String args[])
{
    Scanner sc=new Scanner(System.in);
    PrintWriter out=new PrintWriter(System.out);
    int n=sc.nextInt();
    int m=sc.nextInt();
    int result=n*(m+1);
    out.print(result);
    out.close();
    }
}

program p_e;
const
  maxn=20000+1;
type
  tgroup=record father,members:integer;end;
  ttree=array[1..maxn]of tgroup;
  tstack=array[1..maxn]of integer;
  pnode=^tnode;
  tnode=record node:integer; next:pnode; end;
  plist=array[1..maxn]of pnode;
var
  n,k:longint;
  hands:longint;
  groups:ttree;
  ngroups:integer;
  stack:tstack;
  startstack,endstack:integer;
  list:plist;

procedure Add(x,y:integer);
var
  p:pnode;
begin
  new(p);
  p^.node:=y;
  p^.next:=list[x];
  list[x]:=p;
end;

procedure read_data;
var
  ng:integer;
  index:integer;
  i:integer;
  son,mem:integer;
begin
  readln(n,k);
  ngroups:=1;
  groups[1].father:=0;
  groups[1].members:=n;
  fillchar(list,sizeof(list),0);
  while not eof do
  begin
    read(index);
    read(ng);
    for i:=1 to ng do
    begin
      read(son,mem);
      Add(index,son);
      inc(ng);
      groups[son].father:=index;
      groups[son].members:=mem;
    end;
  end;
end;

procedure EliminateOneCouple(node:integer);
begin
  if node=0 then
    exit;
  dec(groups[node].members);
  EliminateOneCouple(groups[node].father);
end;

procedure eliminate_couples;
var
  p:pnode;
begin
  startstack:=1;
  endstack:=1;
  stack[1]:=1;
  while startstack<=endstack do
  begin
    p:=list[stack[startstack]];
    if (p=nil) and (p^.node=2) then
      EliminateOneCouple(stack[startstack])
    else
      while p<>nil do
      begin
        inc(endstack);
        stack[endstack]:=p^.node;
        p:=p^.next;
      end;
    inc(startstack);
  end;
end;

procedure get_handshackes;
var
  p:pnode;
  current_shackes:longint;
begin
  fillchar(stack,sizeof(stack),0);
  startstack:=1;
  endstack:=1;
  stack[1]:=1;
  while startstack<=endstack do
  begin
    p:=list[stack[startstack]];
    current_shackes:=1;
    if p=nil then current_shackes:=0;
    while p<>nil do
    begin
      inc(endstack);
      stack[endstack]:=p^.node;
      current_shackes:=current_shackes*groups[p^.node].members;
      p:=p^.next;
    end;
  inc(startstack);
  inc(hands,current_shackes);
  end;
end;

procedure write_hands;
begin
  writeln(hands);
end;

begin
  read_data;
  eliminate_couples;
  get_handshackes;
  write_hands;
end.

Try to reread the task. I've been adding up wrong numbers together because of the misunderstanding.

Also, try tests from "If you have WA6"

Why i get RuntimeError?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading;
using System.Diagnostics;
using System.Globalization;


namespace AlgorytmyInternetowe
{
    public class Program
    {

        public static void Main(string[] args)
        {
            //string[] tmp = Console.In.ReadToEnd().Split(new char[] { ' ' });
            string[] tmp = Console.ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
            Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
            Console.Write(int.Parse(tmp[0])-int.Parse(tmp[4])+" "+ (int.Parse(tmp[1]) - int.Parse(tmp[3])));
        }
    }
}

A could do the simple solution there I have 4 points of square and simple calculations of dist to this square. But i found this very easy and i figure out difficult formula for equations of the lines which bounding this square. I calculates dist for this lines and analyzing them.

This is initialization of square:
/*
void init(Point p1, Point p2){
    int64_t dx = p1.x-p2.x, dy = p1.y-p2.y;
    a = dx + dy; // some coof for line-equation
    b = dx - dy;
    c1 = dx*(p1.x-p1.y) + dy*(p1.x+p1.y);
    c2 = dy*(p2.x-p2.y) - dx*(p2.x+p2.y);
    dc = dx*dx + dy*dy; // delta between c-coof two parallel lines
    if (dc == 0) {
        // if square is dot
        c1 = p1.x;
        c2 = p1.y;
   }
}
*/
There i calculate dists to lines
/*
if (dc == 0){
    return std::hypot((p0.x - c1), (p0.y - c2));
} else {
    double
    d1 = (b*(p0.y) - a*(p0.x) + c1)/sqrt(2*dc), // signed dist to first line
    d2 = (b*(p0.x) + a*(p0.y) + c2)/sqrt(2*dc), // signed dist to perpendicular to first line
    d = sqrt(dc/2.0); // delta between two parallel lines (a side of square)
......
*/
"d" always is positive (if square isn't dot), bcs "(d1 - d) < d1" (dist to nearest line less than dist to farthest line)



there is some conditionals for calculate the dist to square
/*
if (d1 < 0) {
    if (d2 < 0) {
        // 1 corner   x1 = (c1*a - c2*b)/(2.0*dc), y1 = (-c1*b - c2*a)/(2.0*dc)
    } else if(d2 <= d){
        // 1 side
        return fabs(d1);
    } else {
        // 2 corner   x2 = (c1*a - c2*b)/(2.0*dc) + (b/2.0), y2 = (-c1*b - c2*a)/(2.0*dc) + (a/2.0)
    }
} else if (d1 <= d) {
    if (d2 < 0){
        // 2 side
        return fabs(d2);
    } else if(d2 <= d){
        // inside square
        return 0;
    } else {
        // 3 side
        return fabs(d2 - d);
    }
} else {
    if (d2 < 0){
        // 3 corner   x3 = (c1*a - c2*b)/(2.0*dc) - (a/2.0), y3 = (-c1*b - c2*a)/(2.0*dc) + (b/2.0)
    } else if(d2 <= d){
        // 4 side
        return fabs(d1 - d);
    } else {
        // 4 corner   x4 = (c1*a-c2*b)/(2.0*dc) + (b-a)/2.0, y4 = (p0.y + (c1*b+c2*a)/(2.0*dc) + (a+b)/2.0
    }
}
*/
after this we sorting dist with num, and print the answer

tests:
8
0 0 2 2
2 4 0 6
-8 -3 -8 -7
7 11 4 15
5 -5 9 -6
-2 -2 -2 -4
-4 6 -8 10
6 6 10 6
.....
6 2 : ans is "8 1 2 5 6 4 7 3"
0 0 : ans is "1 6 2 5 7 3 8 4"

Edited by author 26.08.2020 02:41

In the fine tradition of "digging deeper," I wanted to understand the solution to this problem more completely.   I mean, when I read the problem statement, it did not jump out at me instantly that the value of x that minimizes

 f(x) = k/n * ((x-a1)^2 + (x-a2)^2 + ... + (x-an)^2) is the artihmetic mean of a1...an

If you look at the example, you may think "Aha!  The output is the average of the input!"  But the solver must beware, test writers just love to mislead by simple example cases that do not reveal the entire subtlety of the problem.   They'll get you with one of those WA#12s if you're not careful.

So I dusted off my calculus and recalled that to calculate the min/max of a function, find the derivative of f(x) and set it to zero, and then solve for x.  So here we go...

f(x) = k * (x^2 -2(a1)x + (a1)^2 + x^2 -2(a2)x + (a2)^2 + ... + x^2 -2(an)x + (an)^2) / n
      = k (x^2 - (2/n)(a1 + a2 + ... + an)x + ((a1)^2 + (a2)^2 + ... + (an)^2)/n

so we have
f'(x) = k(2x - (2/n)(a1 + a2 + ... + an))
setting to zero and solving for x gives

x = (a1 + a2 + ... + an) / n

Voila!  Not a guess, but good solid derivation.   Oh, and we can be sure that this is minimum rather than a maximum because the function is an upward opening parabola (since we assume that k is positive).


Edited by author 04.10.2012 01:16

My Python program solved this problem using 0.7+ seconds and 64000+KB memory. However, I saw some people solved it with Python using just about 0.1 secs and 500KB mem. Can anyone give me a hint about how to reach that efficiency?

K-th zero

There can be more than one portal of same type

#include <stdio.h>

int main ()
{
    int n, m;
    scanf("%d %d", &n, &m);

    int ara[n+1]{0}, temp;
    double result{0};

    for (int i = 1; i <= m; i++) {
        scanf("%d", &temp);

        ara[temp]++;
        temp = 0;
    }

    for (int i = 1; i <= n; i++) {

        if(m == 0) {
            printf("0.00%\n");
            continue;
        }
        result = (100.0 * ara[i] / m);
        printf("%2.2lf", result);
        printf("%\n");

    }

    return 0;
}

What is test nubmer 4? Anybody know?

for (long double N = 1; N < sqrt(2*S)+3; N++) {
}