代写data编程、R程序设计代做

日期：2024-02-23 06:08

Problem S4: Painting Roads

Problem Description

Alanna, the mayor of Kitchener, has successfully improved the city’s road plan. However, a

travelling salesperson from the city of RedBlue complained that the roads are not colourful

enough. Alanna’s second job is to paint some of the roads.

Kitchener’s road plan can be represented as a collection of N intersections with M roads,

where the i-th road connects intersections ui and vi

. All roads are initially grey. Alanna

would like to paint some of the roads in red or blue such that the following condition is

satisfied:

? Whenever there is a grey road that connects ui and vi

, there is also a path of roads

from ui to vi such that the roads on the path alternate between red and blue, without

any of the roads on this path being grey.

To lower the city’s annual spending, Alanna would like to minimize the number of painted

roads. Can you help Alanna design a plan that meets all the requirements?

Input Specification

The first line contains two integers N and M (1 ≤ N, M ≤ 2 · 105

).

The i-th of the next M lines contains two integers ui and vi

, meaning that there exists a

road from intersection ui to intersection vi (1 ≤ ui

, vi ≤ N, ui ?= vi).

There is at most one road between any unordered pair of intersections.

The following table shows how the available 15 marks are distributed:

Marks Additional Constraints

2 There is a road connecting intersection i with intersection i + 1 for all 1 ≤ i < N

(and possibly other roads).

3 We can reach any intersection from any other intersection, and N = M.

3 No road belongs to two or more simple cycles (see Definition below).

7 None

Definition: if we denote a road between intersections u and v as u ? v, then a simple cycle

is a sequence w1 ? w2 ? . . . ? wk ? w1 where k ≥ 3 and all wi are distinct.

Output Specification

Output a string of M characters, representing the paint plan. The i-th character should be

R if the i-th road is to be painted red, B if i-th road is to be painted blue, or G (for “grey”)

if the i-th road is to be left unpainted.

La version fran?caise figure `a la suite de la version anglaise.

Remember that you must minimize the number of painted roads while satisfying the condition. If there are multiple possible such plans, output any of them.

Sample Input 1

5 7

1 2

2 4

5 2

4 5

4 3

1 3

1 4

Output for Sample Input 1

RGGRGRB

Explanation of Output for Sample Input 1

A diagram of the intersections along with a valid paint plan that minimizes the number of

painted roads is shown below. Note that the colours are shown on each road as R (red), B

(blue), or G (grey).

1 2

3 4 5

R

R B G2 G3

G5 R

All the unpainted roads satisfy the condition:

? The 2nd road, labelled G2, connects intersection 2 with intersection 4. The path

through intersections 2, 1, 4 alternates red, blue.

? The 3rd road, labelled G3, connects intersection 5 with intersection 2. The path

through intersections 5, 4, 1, 2 alternates red, blue, red.

? The 5th road, labelled G5, connects intersection 4 with intersection 3. The path

through intersections 4, 1, 3 alternates blue, red.

La version fran?caise figure `a la suite de la version anglaise.

Sample Input 2

4 2

1 2

3 4

Output for Sample Input 2

BB

Explanation of Output for Sample Input 2

Note that it is possible for Kitchener to be disconnected.

La version fran?caise figure `a la suite de la version anglaise.

Probl`eme S4 : Peindre les routes

Enonc′e du probl`eme ′

Alanna, la mairesse de Kitchener, a r′eussi `a am′eliorer le plan routier de la ville. Cependant,

un vendeur itin′erant de la ville de RougeBleu s’est plaint que les routes manquaient de

couleur. Par cons′equent, la nouvelle mission d’Alanna consiste `a peindre certaines des routes.

Le plan routier de Kitchener est compos′e de N intersections avec M routes, o`u la i

i`eme route

relie les intersections ui et vi

. Initialement, toutes les routes sont grises. Alanna aimerait

peindre certaines routes en rouge ou en bleu de mani`ere que la condition suivante soit

remplie :

— Pour toute route grise reliant ui `a vi

, il doit exister un itin′eraire de ui `a vi compos′e

de routes dont les couleurs alternent entre rouge et bleu, sans qu’aucune route de cet

itin′eraire ne soit grise.

Dans l’optique de limiter les d′epenses annuelles de la ville, Alanna souhaite minimiser le

nombre de routes `a peindre. Pouvez-vous aider Alanna `a concevoir un plan qui r′epond `a

toutes ces exigences ?

Pr′ecisions par rapport aux donn′ees d’entr′ee

La premi`ere ligne des donn′ees d’entr′ee doit contenir deux entiers N et M (1 ≤ N,

M ≤ 2 · 105

).

La i

i`eme ligne des M lignes suivantes doit contenir deux entiers ui et vi

, indiquant qu’il existe

une route reliant l’intersection ui `a l’intersection vi (1 ≤ ui

, vi ≤ N, ui ?= vi).

Il existe au maximum une route entre chaque paire non ordonn′ee d’intersections.

Le tableau ci-dessous d′etaille la r′epartition des 15 points disponibles.

Points Contraintes additionnelles

2 Il existe une route reliant l’intersection i `a l’intersection i+1 pour tout 1 ≤ i < N

(et possiblement d’autres routes).

3 Il est possible de se rendre `a n’importe quelle intersection depuis une autre et

N = M.

3 Aucune route n’appartient `a deux ou plus cycles simples (voir la d′efinition cidessous).

7 Aucune

D′efinition : soit u ? v une route qui relie les intersections u et v. Un cycle simple est une

suite w1 ? w2 ? . . . ? wk ? w1, wi ′etant tous distincts et k ≥ 3.

English version appears before the French version

Pr′ecisions par rapport aux donn′ees de sortie

Les donn′ees de sortie devraient afficher une cha??ne de M caract`eres, repr′esentant le plan de

peinture. Le i

i`eme caract`ere devrait ?etre R si la i

i`eme route doit ?etre peinte en rouge, B si la

i

i`eme route doit ?etre peinte en bleu ou G (pour ? gris ?) si la i

i`eme route ne doit pas ?etre

peinte.

Il est imp′eratif de minimiser le nombre de routes `a peindre tout en remplissant la condition

′etablie. S’il existe plusieurs plans possibles, les donn′ees de sortie peuvent en afficher un

quelconque.

Donn′es d’entr′ee d’un 1er exemple

5 7

1 2

2 4

5 2

4 5

4 3

1 3

1 4

Donn′es de sortie du 1er exemple

RGGRGRB

Justification des donn′es de sortie du 1er exemple

La figure ci-dessous illustre les intersections ainsi qu’un plan de peinture qui minimise le

nombre de routes `a peindre. Les couleurs des routes sont repr′esent′ees par les lettres R

(rouge), B (bleu) ou G (gris).

1 2

3 4 5

R

R B G2 G3

G5 R

English version appears before the French version

Toutes les routes non peintes remplissent la condition :

— La 2e

route, soit la route G2, relie l’intersection 2 `a l’intersection 4. Les couleurs du

chemin passant par les intersections 2, 1, 4 alternent de la mani`ere suivante : rouge,

bleu.

— La 3e

route, soit la route G3, relie l’intersection 5 `a l’intersection 2. Les couleurs du

chemin passant par les intersections 5, 4, 1, 2 alternent de la mani`ere suivante : rouge,

bleu, rouge.

— La 5e

route, soit la route G5, relie l’intersection 4 `a l’intersection 3. Les couleurs du

chemin passant par les intersections 4, 1, 3 alternent de la mani`ere suivante : bleu,

rouge.

Donn′es d’entr′ee d’un 2e exemple

4 2

1 2

3 4

Donn′es de sortie du 2e exemple

BB

Justification des donn′es de sortie du 2e exemple

Remarquons qu’il est possible que Kitchener soit d′econnect′e.

English version appears before the French version