# Solving Programming Problems in CF

In this article, we’ll take a look at how I solved FranceIOI / others basic programming problems, using CF, and how you can get into competitive programming too !

## Give these problems a go in you favorite language, and then you can check on my CF solutions !

# Library Problem

## Form (translated):

### Form

A library owns

`nbBooks`

books, indexed from 0 to`nbBooks - 1`

. Every day, a few clients ask to borrow a book for a certain duration.

Your program should first read two integers on the first line: nbBooks <= 100 and nbDays. For every day, the program will read a line containing a nbClients, and for each client, read 2 other integers, corresponding to the index of the book, and the duration. It will then output a 0 or a 1 for each request, telling if the book is available (line separated).

### Machine

- 2s on a 1GHz machine
- 8000ko memory

### Example IO

Input:

1 | 2 4 |

Output:

1 | 1 |

## Solving it

First, we need to understand the form. It just asks us to accept or decline requests from clients, and keep track of whether or not books are available.

We then need a data structure for our books, since they’re indexed like an array, it seems obvious to use one. All we have left to do is to think about what data we need to store about the book. We could use the date it’s been last borrowed, and have some maths, but, when we think about it, we can just have them on a cooldown. A book can then be a single Int, 0 from the start, which will be set to a positive int when borrowed, representing the duration. Each day, it decreases by 1, and checking if it’s available is as simple as `n <= 0`

.

## Coding it

First, we need a way to get input, as we saw earlier, we only have to input ints, simple values, or double, separated by commas. Outputting will be quite simple as well.

1 | single_input :: IO ->> Int |

Now we need to manage books. We setup 3 interactions, borrowing (changing 1 value), updating the books every day, and checking if a book os available.

1 | borrow :: [Int], Int, Int ->> [Int] |

Now, we just need to deal with the ugly loops, in a `do`

block. Nothing that we haven’t setup yet, it’s just a matter of solving the exact form with its wierd inputs.

1 | do: |

## Final Code

# Dart Target

## Form (translated):

### Form

At a bar, you meet dart champions, who practise on square targets.

1 | aaaaaaa |

Given the side length

`n`

, print a similar target

### Machine

- 1s on a 1GHz machine
- 8000ko memory

### Example IO

Input:

1 | 5 |

Output:

1 | aaaaaaaaa |

## Solving it

This one kinda messed with my brain at first, but in the end, it wasn’t that hard.

First, we need a way of arranging letters, so that we can use them more simply. We’ll never need more than `n`

letters. Then, we need a good way of associating each tile with a letter. I quickly thought of distance, but as you can see above, it’s not exactly it, as the diagonals aren’t further than the straight lines. I then figured it was the `max`

of the horizontal & vertical distance.

Once we have that distance, which will be an integer, since we’re taking the max of two integers, we can associate each distance with a letter. Since the highest letter is distance 0, I reversed our original letter list, adnd simply took `letters[dst]`

for every tile.

## Coding it

First, setup the letter stuff.

1 | -- don't import stuff in minimal code comps, it's cheating ;] |

Then, a simple helper function, which finds the right side length, using the letter count. (every letter is represented twice, except the middle letter, which appears only once)

1 | tiles_for_letters :: Int ->> Int |

Next is the big fish, we need to get the letter at each index. I thought a 1-d representation would be convinient, so Ihad to compute the `(x, y)`

each time. We can use all the concepts said before to create that big function, which predicts the right letter at any point.

1 | letter_at_index :: Int, String, Int, Int ->> Int |

Finally, we can think about displaying stuff !

Since the output format is a line per row, we can print them one at a time

1 | display_line :: Int, [String], Int ->> IO |

Now, it’s just a matter of using the functions we defined, and applying that to the inputs

1 | do: |

## Final Code

# Measure Smoothing

## Form (translated):

### Form

You have recieved measures. Measure smoothing is the operation of setting each value in the sequence (not first nor last) to the average of the value before and after it.

You have to find how many smoothing operations are needed to get the maxmium difference between two measures below a certain threshold

Inputs are: number of measures, the threshold, then the measures

### Machine

- 2s on a 1GHz machine
- 8000ko memory

### Example IO

Input:

1 | 7 |

Output:

1 | 13 |

## Solving it

Well, this one was quite a no-brainer. All we have to figure out is a way to perform the smoothing, and a way to check if the difference is below that threshold.

All of those can be solved using simple loops, you’ll see what I mean later.

This problem is more of a coding problem than a thinking problem.

## Coding it

First, actually get the list we’ll work with:

1 | get_measures :: Num, IO ->> [Num] |

The, we can define a 1d distance function, and another to check if a difference is in bound of that threshold:

1 | dist :: Num, Num ->> Num |

With that, we can create a check function, that recursively checks every element of the array. To save on computing time, I’ll eject out as soon as we get a single `False`

. The function is initially called by `check dmax arr Nothing`

, then starts its recursive business. If we reach the last element while checking, without even having ejected out with a `False`

, we return `True`

.

1 | check :: Num, [Num], Maybe Int ->> Bool |

Now, we just need a function to smooth the measures. I opted for the same recursive option. Apart from the first and last elements for which I return the value, I recursively go through the array and add my averages.

1 | smooth_measures :: [Num], Maybe Int ->> [Num] |

Finally, we can just have our loop and count the number of checks we need !

1 | do: |

## Final Code

# Frogs

## Form (translated):

### Form

Frogs are on a race, they’re indexed from 1 to

`nbFrogs`

. Every round (from round 1 to`nbRounds`

), a frog jumps forwardntimes. You need to keep track of the frog who’s been ahead for the longest time

The inputs are the number of frogs, then the number of rounds, then integer pairs for every round: the frog’s index, and the distance it goes forwards by

### Machine

- 1s on a 1GHz machine
- 16000ko memory

### Example IO

Input:

1 | 4 |

Output:

1 | 2 |

## Solving it

Again, here, there isn’t a huge clever trick, we just need to get the data, and register what’s going on. Though, we can have a lot of fun with CF’s data types.

## Coding it

I’m bringing back the code for a double input, no need to show it here again.

Then I talked about `data`

types, we can use those to represent a frog, as we need an index (number), a current distance from the starting blocks, and the time it’s been ahead for.

We’ll also define a `data`

type for a “Leader”, which’ll help quite a lot when sorting the frogs, as we don’t want ties.

1 | data Frog = (Int nb, Int score, Int ahead) |

Then, we need a basic way of having a list of frogs. From the number of frogs we want, we can generate a list of `Mut`

able objects. Here, we map each index of a range to a new Frog object.

1 | frog_list :: Int ->> [Mut Frog] |

Last helpers we need are ways to compare our values. We’ll setup 1 general use function, `compare_two`

, that compares two elements, and returns a `Leader`

object, with al the info we need. We can then compare our Frogs on a specific property with the foldl, or `>\`

operator to find the best of a list, and know what’s their score, if they’re tied, and their idx, which is all we need to complete the task.

1 | compare_two :: String, Frog, Leader ->> Leader |

Finally, in our `do`

block, we can implement our loops & logic:

1 | do: |

## Final Code

[MORE COMING SOON]