[UVA] 857 - Quantiser
Problem F
Quantiser
MIDI (Musical Instrument Digital Interface) is a standard for transmitting musical performance data between devices. With MIDI, each event of a performance (e.g., pressing or releasing a key of a piano) is encoded in a message. A typical MIDI message essentially consists of a code and a note, and says that a given key (corresponding to a given note) was pressed (the code NoteOn) or released (NoteOff code).
If we register all the events of a performance and associate a convenient time stamp with them, we will be able to reproduce the performance later with precision. We may also make many other things, like editing the data or producing a score in standard, human readable, music notation. This last application will be our focus: we want to prepare performance data stored in a file so that the production of a score becomes easy.
Figure 1 presents an example of a performance (4 notes, 8 events) and the corresponding data, in the form <code, note, time-stamp>. The time stamp is represented by the triple <measure:beat:tick>. To make things simpler, we will consider that a measure is a positive integer and has always 4 beats (numbered 1 to 4) and each beat has 480 ticks (numbered 0 to 479).
 |
NoteOn, 35, 23:1:0 NoteOn, 52, 23:1:0 NoteOn, 43, 23:2:0 NoteOff, 52, 23:3:0 NoteOff, 35, 23:4:0 NoteOn, 35, 24:1:0 NoteOff, 43, 24:1:0 NoteOff, 35, 24:2:0 |
Figure 1
This performance may be easily converted to standard music notation, as all the events occur at the exact beginning of a beat (tick 0). The same would happen if they occurred in points corresponding to subdivisions of the beat that match certain musical rhythm symbols. To simplify, we will consider divisions of the beats in 2, 4 and 8 parts as corresponding to legal musical notation; thus, if the events occur in ticks like 60, 240 or 420, the production of the score will be possible.
The events in Figure 1, however, could hardly be produced by an human. Humans can’t be so precise: their performances have subtle "imprecisions" in timing and in other parameters. These imprecisions make a direct production of a score virtually impossible. Figure 2 represents a possible human performance.
|
NoteOn, 35, 23:1:006 NoteOn, 52, 23:1:017 NoteOn, 43, 23:2:010 NoteOff, 52, 23:3:015 NoteOff, 35, 23:3:252 NoteOn, 35, 23:4:473 NoteOn, 33, 23:4:478 NoteOff, 43, 24:1:011 NoteOff, 33, 24:1:012 NoteOff, 35, 24:2:003 |
Figure 2
We may see that the times where the events occur are close to "correct" points. For instance, the fourth event occurs close to 23:3:000, the fifth close to 23:3:240 and the sixth close to 24:1:000. To produce a readable score from this data, we may change the time stamps to make them fit the closest "correct" points: this process is called Quantisation.
The short note 33 near the beginning of measure 24 (in italic) represents a special case: after quantisation, its duration becomes zero. We will filter notes in these conditions.
Problem
Make a program that, given a performance consisting of a sequence of no more than 2.000 events, produces a new sequence after quantising the data. Notes whose duration becomes zero after quantisation must be filtered out. If a time stamp is equally close to two different correct points, quantise it to the upper point (for example, "23 1 30" becomes "23 1 60"). The program should be able to process several performances each time it runs.
Input
The input file represents several performances. Input for each performance consists of a sequence of lines, as follows:
First line: n
Next n lines (up to 2.000): code note m b t
The messages of a performance are ordered by increasing times.
Successive values on a line are separated by one blank. The integer -1 follows the data of the last performance.
Output
Output should give, for each given performance, the following output:
First line: n
Next n lines: code note m b t
The messages of each performance must be ordered by increasing times.
The integer -1 must follow the data of the last performance.
Sample Input
10
1 35 23 1 6
1 52 23 1 17
1 43 23 2 10
0 52 23 3 15
0 35 23 3 252
1 35 23 4 473
1 33 23 4 478
0 43 24 1 11
0 33 24 1 12
0 35 24 2 3
10
1 42 14 1 55
1 38 14 1 126
0 42 14 1 177
1 42 14 1 230
1 51 14 1 241
0 42 14 1 248
1 42 14 1 352
0 38 14 1 356
0 51 14 1 472
0 42 14 2 244
-1
Sample Output
8
1 35 23 1 0
1 52 23 1 0
1 43 23 2 0
0 52 23 3 0
0 35 23 3 240
1 35 24 1 0
0 43 24 1 0
0 35 24 2 0
8
1 42 14 1 60
1 38 14 1 120
0 42 14 1 180
1 51 14 1 240
1 42 14 1 360
0 38 14 1 360
0 51 14 2 0
0 42 14 2 240
-1
Amílcar Cardoso, MIUP'2002
題目描述：
一個音訊的訊息(不用重新排序)，他給定時間單位進行量化，
時間單位為秒，每秒中間又分 4 拍，每一拍中間又分 480 個刻度。
量化按照每 60 刻度當作一個畫分界線，將每個不同的音符起落時間進行量化，
量化標準找最靠近分界線，如果相同則找最上方的。
如果某段聲音量化之後不存在則刪除。
特別要注意拍是從 1, 2, 3, 4, 轉換要特別注意而不是 0 1 2 3
題目解法：
分別進行量化後，O(N*N) 檢查對應的 OFF 時間，進行刪除。
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
struct E {//event
int code, note, m, b, t;
bool operator<(const E &A) const {
if(m != A.m) return m < A.m;
if(b != A.b) return b < A.b;
if(t != A.t) return t < A.t;
if(note != A.note)
return note < A.note;
return code < A.code;
}
};
bool cmp(E a, E b) {
if(a.note != b.note)
return a.note < b.note;
if(a.m != b.m) return a.m < b.m;
if(a.b != b.b) return a.b < b.b;
if(a.t != b.t) return a.t < b.t;
return a.code < b.code;
}
int main() {
int n;
int i, j, k;
E D[2005];
while(scanf("%d", &n) == 1 && n >= 0) {
for(i = 0; i < n; i++)
scanf("%d %d %d %d %d", &D[i].code, &D[i].note, &D[i].m, &D[i].b, &D[i].t);
for(i = 0; i < n; i++) {
int v = D[i].t + (D[i].b-1)*480 + D[i].m*4*480;
int m, b, t, q;
q = (v+30)/60*60;
t = q%480, b = (q/480)%4, m = q/480/4;
D[i].m = m;
D[i].b = b+1;
D[i].t = t;
//printf("%d %d %d %d %d\n", D[i].code, D[i].note, D[i].m, D[i].b, D[i].t);
}
int ban[2005] = {};
for(i = 0; i < n; i++) {
if(D[i].code == 0) continue;
for(j = i+1; j < n; j++) {
if(D[j].code == 1) continue;
if(D[j].note == D[i].note) {
if(D[j].m == D[i].m && D[j].b == D[i].b && D[j].t == D[i].t)
ban[i] = ban[j] = 1;
break;
}
}
}
int ret = 0;
for(i = 0; i < n; i++)
ret += ban[i] == 0;
printf("%d\n", ret);
for(i = 0; i < n; i++) {
if(ban[i] == 0)
printf("%d %d %d %d %d\n", D[i].code, D[i].note, D[i].m, D[i].b, D[i].t);
}
}
puts("-1");
return 0;
}
/*
4
1 0 0 0 0
0 0 0 0 58
1 0 0 0 62
0 0 0 0 118
*/