## CPC '19 Contest 1 P4 - Sorting Practice

View as PDF

Points: 12 (partial)
Time limit: 2.5s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Today we will be practicing sorting! You and your friend are tasked to sort an array of length , (with elements ). To make your task more challenging, you will be blindfolded and will not be able to see this array.

You will be allowed to give directions to your friend a maximum of times. You can either ask your friend to compare elements and or swap elements and , as long as and for some integer . Your friend will provide feedback after each direction. Can you determine a sequence of directions to sort the array?

Note: it is not required to sort the array with the minimum number of directions.

#### Constraints

(you will not be directly given though)

At most directions are allowed.

#### Interaction

The first line of input contains a single integer , the size of the array.

You are then allowed to give directions to your friend.

To tell your friend to compare elements and , output C i j followed by a new line character \n. If the direction is valid, your friend will respond with 1 if , or 0 if .

To tell your friend to swap elements and , output S i j followed by a new line character \n. If the direction is valid, your friend will respond with 1.

After giving between and directions, you can tell your friend that the array is sorted by outputing A followed by a new line character \n and terminating immediately. This does not count as a direction. Your friend will not respond after this direction. If the array is indeed sorted, then you will receive a verdict of Accepted. Otherwise, you will receive a verdict of Wrong Answer.

If at any point, you give an invalid direction (eg. the conditions and for some integer are not satisfied, or if you exceed directions), your friend will respond with -1. When this happens, you should terminate your program to avoid reading from a closed input stream, and you will receive a verdict of Wrong Answer. Otherwise, the verdict may be undefined.

Please note that you may need to flush stdout before reading your friend's response. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

#### Sample Interaction

>>> denotes your output. Do not print this out.

4
>>> C 2 3
1
>>> S 1 4
1
>>> C 1 2
0
>>> S 1 2
1
>>> C 2 3
0
>>> A